【2021牛客寒假第二场】J题 牛牛想要成为hacker 构造

传送门：https://ac.nowcoder.com/acm/contest/9982/J

题意

给一个n，构造一个数组，问三层循环中（能不能构造一个三角形） 执行次数次数能不能超过$min(C_n^3,n^2log_2n)。$

思路

三角形成立条件：最短的两条边>最长边，所以相等的话是可以的。

想到2个数相加等于第三个数，这是什么？这是斐波那契数。

而1e9的斐波那契数有45个，所以n=1e5的时候，45*n*n的执行次数是可以的。

注意，最前面的1和1是不能要的，这一点好好想想，所以代码就很简单了。

Code(3MS)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
##include "bits/stdc++.h"
using namespace std;

typedef long long ll;

const int N = 1e5 + 10;
const ll MAX = 1e9;
ll f[N];

void solve() {
    int n; cin >> n;
//    cout << log2(N) << endl;
    f[0] = 1; f[1] = 2;
    bool flag = 0;
    for(int i = 2;i <= n; i++) {
        if(flag) {
            f[i] = 1;
        }
        else {
            f[i] = f[i - 1] + f[i - 2];
            if(f[i] > MAX)  {
                flag = 1;
                f[i] = 1;
            }
        }
    }

//    cout << min(1ll * n * n * (int)log2(n), 1ll * n * (n - 1) * (n - 2) / 6) << endl;
//    cout << ans << endl;
    for(int i = 1;i <= n; i++) cout << f[i] << " ";
    cout << endl;
}

signed main() {
    solve();
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/02/03/2021-nowcoder-hanjia-2-j/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！