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();
}