2021牛客寒假算法基础集训营2 J.牛牛想要成为hacker

题目描述

在算法竞赛中”hack”一般指用一组测试数据触发程序的缺陷，从而导致本来通过题目的 AC 代码无法通过该测试数据。
一般情况见得比较多的是用 hack 数据导致别人 WA 掉，当然也有一些会导致原本的 AC 代码 TLE 和 MLE。
牛牛在一些简单的练习题时遇到了这样一个问题。
给定一个大小为 $n$ 的数组 $a(1 \leq a_i \leq 10^9)$，然后请你判断数组元素是否能够从中选出三个组成一个三角形。

牛牛发现AC通过的代码中有这样一种暴力逻辑，该逻辑的伪代码如下。

FOR i = 1 ... n
    FOR j = i + 1 ... n
        FOR k = j + 1 ... n
            IF isTriangle(a[i],a[j],a[k])
                print("yes")
                EXIT
            END IF
        END FOR
    END FOR
END FOR
print("no")
EXIT

其实就是三重循环枚举数组的三个元素，检查是否为三角形。这段代码很取巧的地方在于它存在一种“短路”逻辑，一旦发现存在三角形就立刻终止程序。

这样在随机数据下其实很容易发现三角形，所以如果数据纯随机，显然这就是一段 AC 代码。

牛牛当然知道这个代码很明显就存在缺陷，如果数据构造的好的话应该可以卡 TLE，但是牛牛发现，他并不会构造出能够 hack 这个暴力算法的数据，所以他请你来帮他。

我们以这段程序调用 isTriangle 的次数作为时间复杂度的计算依据，请你构造数据 hack 这段暴力程序，使它 TLE 掉。

输入描述:

第一行输入一个正整数 $n(3 \leq n \leq 10^5)$ 表示需要你构造的数组大小。

输出描述:

输出 $n$ 个正整数，正整数的范围在 $[1,10^9]$ 之间，要求该暴力程序在运行过程中调用 isTriangle 函数的次数不得少于 $min(C_n^3,n^2\left \lfloor log_2n \right \rfloor)$

示例1

输入

输出

2 2 2

示例2

输入

输出

1	1 2 4 8 16 32 64 128 256 512

思维~

其实没必要深究用啥序列，因为不论等比数列抑或是斐波那契数列最多不过几十项就爆 int 了，所以这题的关键在于构造，我们要卡一个 $n^2log(n)$，则这个数列迭代的最大项数 $a$ 必须满足 $2^{a-1}\geq n$，根据这一点我们可以选定一个等比数列(怕麻烦就直接选斐波那契数列😂)，那么怎么构造呢，我们可以把数列的后 $a-1$ 项提到前面，后面全放第一项，这样第一重循环选择前 $a-1$ 个数时，后面两重循环无论怎么选都无法构成三角形，此时循环次数就是 $O((a-1)n^2)$，而上面又满足 $2^{a-1}\geq n$，所以此时符合题意，AC 代码如下：

#include <bits/stdc++.h>

using namespace std;
int n, s = 2;

int main() {
    cin >> n;
    for (int i = 1; i <= 29; i++) {
        cout << s << " ";
        s *= 2;
    }
    for (int i = 29; i <= n; i++)
        cout << 1 << ' ';
    return 0;
}