Codeforces Round 887 (Div. 2)

Codeforces Round 887 (Div. 2)

 

A. Desorting

题意：

​ 一个长度为n的序列，可以执行任意次操作，将[1, i] 的数字全部加一，且[i+1, n] 的数字全部减一，问最少执行多少次操作可以让该序列非sorted（sorted 即非严格递增）

Idea：

​ 若已经非sorted则不用操作，否则找到最小的 delt = a[i] - a[i-1] ，答案为 $(delt+2)/2$

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int n, m;

void solve(){
    cin >> n;
    vector<int>a(n);
    for(auto &e : a) cin >> e;

    if(!is_sorted(a.begin(), a.end())){
        cout << "0\n";
        return;
    }

    int mn = LLONG_MAX;
    for(int i = 1;i < n;i++){
        mn = min(mn, a[i] - a[i-1]);
    }

    cout << (mn + 2) / 2 << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;
    while(t--)solve();

    return 0;
}
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

 

B. Fibonaccharsis

题意：

​ 有两个整数n，k。问有多少个长k的类斐波那契数列f，且$f_k=n$

Idea：

​ 设所求数列的前两个数为x，y，则$f_3,f_4,f_5,f_6....$ 分别等于 $x+y,x+2y,2x+3y,3x+5y,..$ ，x，y的系数为斐波那契数列，不过y的系数是从斐波那契数列的第二个1开始。于是$f_k=k_{1}x+k_{2}y$，可求出$k_1，k_2$后枚举合法的$x，y$对数，即为答案。还有当$k_2$大于n的时候没有合法解，斐波那契数列大概第30位就大于2e5了，所以k大于30时可以直接输出0

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int n, k;

int ferbo(int n){
	return (sqrt(5)/5)*(pow((1+sqrt(5))/2,n)-pow((1-sqrt(5))/2,n));
}

void solve(){
    cin >> n >> k;
    if(k >= 50){
        cout << "0\n";
        return;
    }
    int f1 = ferbo(k - 2);
    int f2 = ferbo(k - 1);


    int dx = n / (f1 + f2);

    int ans = 0;
    for(int i = 0;i <= dx;i++){
        if((n - f1*i) % f2 == 0) ans++;
    }

    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    cin >> t;
    while(t--)solve();

    return 0;
}
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
37
38
39
40
41

 

C. Ntarsis’ Set

题意：

​ 有一个无限大的从一开始逐次加一的数组s，给出一个长n的数组a，执行k次操作：每次删除此时s中第$a_1,a_2,a_3...a_n$小的数，问最后s中最小的数时多少

Idea：

​ 首先如果$a_1!=1$最后最小值就是1。

​ 每次删除的第一个数就是上一次删除后出现的最小值（第一次删除除外），所以我们可以找每次要删除的第一个数就可以找到最后剩余的最小值是多少。

​ 若一直进行操作：

• a = { 1 , 5 , 10 } a=\{1,5,10\} a={1,5,10} 时，每次删除的第一个数分别是 $1、2、3、4、6、8、11、\mathrm{14...}$ 因为$a_2=5$，所以在[1,4]区间的数都会被作为第一个数被删除，即被作为最小值。[5，9]区间中因为$a_2$在此区间删除过数，所以删除的第一个数在此区间每次递增加2，同理在[10，$+\infty$]区间每次递增加3.

​ 利用上述规律求出第k+1 次被删除的第一个数即可

code：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int n, k, a[N];

void solve(){
    cin >> n >> k;
    for(int i = 1;i <= n;i++) cin >> a[i];

    if(a[1] != 1){
        cout << 1 << '\n';
        return;
    }

    int ans = 1;
    int cur = 1;
    while(k--){
        ans += cur;
        while(cur + 1 <= n && ans >= a[cur + 1]){
            cur++;
            ans++;
        }
    }

    cout << ans << '\n';

}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin >> t;
    while(t--) solve();

    return 0;
}
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
37
38
39
40

​