视频讲解Codeforces Round 887 (Div. 2)（A–C）

A. Desorting

1、板书

2、代码

#include<bits/stdc++.h>
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 10;void solve()
{int n;cin >> n;vector<int>a(n);for(int i = 0; i < n; i ++)cin >> a[i];int ans = INF;for(int i = 0; i < n - 1; i ++){ans = min(ans, a[i + 1] - a[i]);}if(ans < 0){cout << 0 << endl;return;}cout << ans / 2 + 1 << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();
}

B. Fibonaccharsis

1、板书

2、代码

#include<bits/stdc++.h>
#define int long long 
#define endl '\n'
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 10;void solve()
{int n,k;cin >> n >> k;if(k > 30){cout << 0 << endl;return;}int ans = 0;for(int i = n / 2; i <= n; i ++){int flag = true;vector<int>a(k);a[k - 1] = n, a[k - 2] = i;for(int j = k - 3; j >= 0; j --){a[j] = a[j + 2] - a[j + 1]; }for(int j = 0; j < k - 1; j ++){if(a[j] < 0 || a[j] > a[j + 1]){flag = false;break;}}if(flag)ans ++;}cout << ans << endl;}// void test()
// {
// 	int a1 = 0, a2 = 1;
// 	int a3 = 0;
// 	int cnt = 2;
// 	for(int i = 0; a3 < 2e5; i ++)
// 	{
// 		a3 = a1 + a2;
// 		cnt ++;
// 		a1 = a2, a2 = a3;
// 	}
// 	cout << cnt << endl;
// }signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();}

C. Ntarsis’ Set

1、板书

2、代码

#include<bits/stdc++.h>
#define endl '\n'
#define int long long 
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 1e5 + 10;
int n, k;bool check(int mid, vector<int>&a)
{for(int i = 0; i < k; i ++){int p = upper_bound(a.begin(), a.end(), mid) - a.begin();mid -= p;if(mid <= 0)return false;}return true;
}void solve()
{cin >> n >> k;vector<int>a(n);for(int i = 0; i < n; i ++)cin >> a[i];int l = 1, r = 1e18;while(l < r){int mid = l + r >> 1;if(check(mid, a))r = mid;elsel = mid + 1;}cout << l << endl;
}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();
}