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]<<" "; } }