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

Description

在算法竞赛中"hack"一般指用一组测试数据触发程序的缺陷，从而导致本来通过题目的AC代码无法通过该测试数据。
一般情况见得比较多的是用hack数据导致别人WA掉，当然也有一些会导致原本的AC代码TLE和MLE。

牛牛在一些简单的练习题时遇到了这样一个问题。
给定一个大小为n的数组 ，然后请你判断数组元素是否能够从中选出三个组成一个三角形。

牛牛发现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掉。

Solution

part.1 fibnoacci数列
这里应该很多人都能想到是利用fibnoacci数列进行构造,但是不知道怎么处理.
我们可以联想到fibnoacci数的性质 .
这样我们在构造fibnoacci数列的时候,使该数列形成一个非递增的数列,因为 ,这样对于 的情况,都可以保证得到 ,这样就可以确保后面两个循环跑满.
而符合数据范围的fibnoacci数有42个,这样构造使得运行次数大约为 ,而 ,可知满足题意.

part.2 等比数列
以2为公比的等比数列也是满足题意的.
与fibnoacci数列类似,以2为公比的等比数列满足
所以思路也就变得跟上面一样了,同样满足 并且 时,都能保证 .
符合数据范围的数有 个,这种构造的运行次数大约为 ,同样满足 的需求.

Code

part.1 fibnoacci数列

#include <bits/stdc++.h>
#define endl '\n'
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define endl '\n'
#define inf 0x3f3f3f3f
using namespace std;
struct _IO
{
    _IO()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
    }
} _io;

inline int read()
{
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

const ll mod = 1e9 + 7;
const ll maxn = 1e5 + 7;

ll ans[maxn];

void init(){
    for(int i=43;i<maxn;i++){
        ans[i]=1;
    }
    for(int i=42;i>=1;i--){
        ans[i]=ans[i+1]+ans[i+2];
    }
}

int main()
{
    init();
    ll n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
}

part.2 等比数列

#include <bits/stdc++.h>
#define endl '\n'
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define endl '\n'
#define inf 0x3f3f3f3f
using namespace std;
struct _IO
{
    _IO()
    {
        ios::sync_with_stdio(0);
        cin.tie(0);
    }
} _io;

inline int read()
{
    int s = 0, w = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
        s = s * 10 + ch - '0', ch = getchar();
    return s * w;
}

const ll mod = 1e9 + 7;
const ll maxn = 1e5 + 7;

ll ans[maxn];

void init(){
    for(int i=30;i<maxn;i++){
        ans[i]=1;
    }
    for(int i=29;i>=1;i--){
        ans[i]=ans[i+1]*2;
    }
}

int main()
{
    init();
    ll n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
}