牛牛想要成为hacker 三角形 思维 构造

本题很容易想到用斐波那契数列构建，但是fib很快就会超过1e9，数据项并不够。

所以：

• 不可能找不到三角形，只能推迟，但无法阻止
• 时间复杂度提示

>>> from math import log2
>>> log2(100000)
16.609640474436812

比赛的时候我想到了这里，但当时以为就是要让i循环走到16之后即可，所构建的数据也让i循环走到了21。但其实这是不够的：因为对于每个i循环，k并没有走次。

所以为了让次数尽可能多，必须降序构建。

最优的构造应当是降序的fib序列。

fib = [1, 1]
while fib[-1]+fib[-2] < 1e9:
    fib.append(fib[-1]+fib[-2])
fib.reverse()
n = int(input())
sz = len(fib)
for i in range(n):
    print(fib[i] if i < sz else 1, end=' ')

这也是一种比较有趣的写法

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld ", (x))
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
int main() {
    int n;
    scanf("%d", &n);
    int x = 1 << 29;
    for(int i = 1;i <= n;i++){
        printf("%d ", x);
        if(x > 1) x >>= 1;
    }
    return 0;
}