Codeforces Round 889 (Div. 2)（视频讲解A——D）

Codeforces Round 889 (Div. 2)（视频讲解A——D）

A Dalton the Teacher

#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 + 1);int ans = 0;for(int i = 1; i <= n; i ++){cin >> a[i];if(a[i] == i)ans ++;}cout << (ans + 1) / 2 << endl;
}	signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();
}

B Longest Divisors Interval

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

C2 Dual (hard Version)

#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 add_1(vector<int>&a, vector<pii>&ans)
{for(int i = 0; i < a.size() - 1; i ++){a[i + 1] += a[i];ans.push_back({i + 1, i});}cout << ans.size() << endl;for(auto [a, b] : ans)cout << a + 1 << " " << b + 1 << endl;return;
}void add_2(vector<int>&a, vector<pii>&ans)
{for(int i = a.size() - 1; i >= 1; i --){a[i - 1] += a[i];ans.push_back({i - 1, i});}cout << ans.size() << endl;for(auto [a, b]: ans)cout << a + 1 << " " << b + 1 << endl;return;
}void solve()
{int n;cin >> n;vector<int>a(n);int p_max = 0, p_min = 0;int cnt_1 = 0, cnt_2 = 0;vector<pii>ans;for(int i = 0; i < n; i ++){cin >> a[i];if(a[p_max] < a[i])p_max = i;if(a[p_min] > a[i])p_min = i;if(a[i] < 0)cnt_2 ++;if(a[i] > 0)cnt_1 ++;}if(a[p_min] >= 0){add_1(a, ans);return;}if(a[p_max] <= 0){add_2(a, ans);return;}if(abs(a[p_max]) >= abs(a[p_min])){if(cnt_2 <= 12){for(int i = 0; i < n; i ++){if(a[i] < 0){a[i] += a[p_max];ans.push_back({i, p_max});}}add_1(a, ans);}else{for(int i = 0; i < 5; i ++){if(abs(a[p_min]) >= abs(a[p_max]))break;ans.push_back({p_min, p_min});a[p_min] += a[p_min];}for(int i = 0; i < n; i ++){if(a[i] > 0){a[i] += a[p_min];ans.push_back({i, p_min});}}add_2(a, ans);}}else{if(cnt_1 <= 12){for(int i = 0; i < n; i ++){if(a[i] > 0){a[i] += a[p_min];ans.push_back({i, p_min});}}add_2(a, ans);}else{for(int i = 0; i < 5; i ++){if(abs(a[p_max]) >= abs(a[p_min]))break;	a[p_max] += a[p_max];ans.push_back({p_max, p_max});}for(int i = 0; i < n; i ++){if(a[i] < 0){a[i] += a[p_max];ans.push_back({i, p_max});}}add_1(a, ans);}}}signed main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t--)solve();
}

D Earn or Unlock

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