【题解】Codeforces Round 1087 (Div. 2)

2401_88501775

387人浏览 · 2026-04-07 13:03:00

2401_88501775 · 2026-04-07 13:03:00 发布

请添加图片描述

A. Flip Flops

将 $a$ 数组从小到大排序，枚举 $a_i$ ，如果能对 $a_i$ 使用 “flip-flop” 则贪心地用上。

#include<bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
	int n,c,k;
	cin >> n >> c >> k;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
	}
	sort(a.begin()+1,a.end());
	
	for(int i = 1; i <= n; i ++){
		if(k > 0){
			if(c > a[i]){
				int mi = min(c - a[i],k);
				a[i] += mi;
				k -= mi;
			}
		}
		if(c >= a[i]) c += a[i];
		
	}
	cout << c << '\n';
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t = 1;
	cin >> t;
	while(t --){
		solve();
	}
}

B. Array

数据范围允许 $O(n^2)$ 解决。
$k$ 为无穷大或无穷小时最优，k 取无穷小时，答案为小于 $a_i$ 的所有数,反之为大于 $a_i$ 的所有数。
枚举 $a$ 数组中每一个数，统计大于 $a_i$ 和小于 $a_i$ 的数有多少即可。

#include<bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
	int n;
	cin >> n;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
	}
	vector<int> ans(n+1);
	for(int i = 1; i <= n; i ++){
		int cnt1 = 0,cnt2 = 0;
		for(int j = i + 1; j <= n; j ++){
			if(a[j] > a[i]) cnt1 ++;
			else if(a[j] < a[i]) cnt2 ++;
		}
		cout << max(cnt1,cnt2) << ' ';
	}
	cout << '\n';
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t = 1;
	cin >> t;
	while(t --){
		solve();
	}
}

C. Find the Zero

考虑构造特解后推广到通解。
对于 $n = 2$ 的情况，执行询问 $(位置 1, 位置 2)$ 、 $(位置 1, 位置 3)$ 、 $(位置 2, 位置 3)$ 。
- 如果三组均返回 $0$ , 则证明位置 $1$ 、位置 $2$ 、位置 $3$ 两两不同。因为两两不同的的充要条件就是 $012$ 三种数字都出现一次，所有位置 $4$ 一定是没被用到的数字 $0$ 。答案为位置 $4$ 。
- 否则有一组返回 $1$ , 代表有两个位置的数组相同，相同必定为两个 $0$ , 直接输出。
当 $n > 2$ 时，先执行 $n - 2$ 次询问，每次询问相邻的两个位置，形如 $(位置 1, 位置 2)$ 、 $(位置 3, 位置 4)$ 、 $(位置 5, 位置 6)$ 、 $(位置 7, 位置 8) ......$
- 有一组返回 $1$ , 代表有两个位置的数组相同，相同必定为两个 $0$ , 直接输出.
- 每组均返回 $0$ , 则每组内至少有一个非 $0$ ，那么排除了 $n - 1$ 个非 $0$ 数，最后四个数构成一个 $n = 2$ 的特解。

#include<bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
	int n;
	cin >> n;
	for(int i = 1; i <= 2*n - 4; i += 2){
		cout << "? " << i << ' ' << i + 1 << endl;
		int ret;
		cin >> ret;
		if(ret == 1){
			cout << "! " << i << endl;
			return;
		}
	}
	cout << "? " << 2*n - 3<< ' ' << 2*n - 2 << endl;
	int ret;
	cin >> ret;
	if(ret == 1){
		cout << "! " << 2*n-3 << endl;
		return;
	}
	cout << "? " << 2*n - 2 << ' ' << 2*n - 1 << endl;
	cin >> ret;
	if(ret == 1){
		cout << "! " << 2*n-2 << endl;
		return;
	}
	cout << "? " << 2*n - 3 << ' ' << 2*n - 1 << endl;
	cin >> ret;
	if(ret == 1){
		cout << "! " << 2*n-3 << endl;
		return;
	}
	cout << "! " << 2*n << endl;
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t = 1;
	cin >> t;
	while(t --){
		solve();
	}
}

D. Ghostfires

本题更推荐参照官方题解，官方题解的构造方案更简洁。

官方题解
另一种解法：
- 不妨用 $cnt_0,cnt_1,cnt_2$ 分别代表数量最多，数量第二多，数量最少的颜色个数， $012$ 代表对应颜色。
- 当 $cnt_0 > cnt_1 + cnt_2$ ，最优解为放一个 $0$ 颜色，再放一个非 $0$ 颜色,得到形如， $01010102020$ 的序列, 剩下的 $0$ 用不完，否则一定能把颜色用尽。
- 对于 $cnt_0 = cnt_1 = cnt_2$ 的情况，可以用序列 012120、120201、201012三种序列首尾相接的方法，构造合法解（实际上3种里选2种就可以了）。
- 对于 $cnt_0 > cnt_1$ 的情况，转化为 $cnt_0 = cnt_1 = cnt_2$ 即可，方法为每轮消耗一个 $cnt_0$ ，再消耗当下剩余第二多的元素。最后一定能得到 $cnt_0 = cnt_1 = cnt_2$ 或者 $cnt_0 = 1 + cnt_1 = 1 + cnt_2$ 的结果。对于后者，在末尾手动放一个 $0$ 。

#include<bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
	vector<pair<int,char>> tmp(3);
	cin >> tmp[0].first >> tmp[1].first >> tmp[2].first;
	tmp[0].second = 'R',tmp[1].second = 'G',tmp[2].second = 'B';
	sort(tmp.begin(),tmp.end(),greater<>());
	vector<pair<int,int>> cnt = {{tmp[0].first,0},{tmp[1].first,1},{tmp[2].first,2}};
	if(cnt[0].first >= cnt[1].first + cnt[2].first){
		vector<int> ans2;
		while(1){
			sort(cnt.begin()+1,cnt.end(),greater<>());
			if(cnt[1].first == 0){
				break;
			}
			ans2.push_back(cnt[0].second);
			ans2.push_back(cnt[1].second);
			cnt[0].first --;
			cnt[1].first --;
		}
		if(cnt[0].first){
			ans2.push_back(0);
			cnt[0].first --;
		}
		for(int i : ans2){
			cout << tmp[i].second;
		}
		cout << '\n';
		return;
	}
	vector<int> ans1,ans2;
	while(1){
		sort(cnt.begin()+1,cnt.end(),greater<>());
		if(cnt[0].first == cnt[2].first || (cnt[0].first == cnt[1].first + 1 && cnt[0].first == cnt[2].first + 1)){
			break;
		}
		ans2.push_back(cnt[0].second);
		ans2.push_back(cnt[1].second);
		cnt[0].first --;
		cnt[1].first --;
	}
	
	if((cnt[0].first == cnt[1].first + 1 && cnt[0].first == cnt[2].first + 1)){
		ans2.push_back(0);
		cnt[0].first --;
	}
	
	int k = cnt[0].first;	
	int base = 1;
	while(1){
		if(k >= 1){
			ans1.push_back(base);
			ans1.push_back((base+2)%3);
			ans1.push_back((base+1)%3);
			k --;
		}else break;
		if(k >= 1){
			ans1.push_back((base+2)%3);
			ans1.push_back((base+1)%3);
			ans1.push_back(base);
			base = (base+1)%3;
			k --;
		}else break;
	}
	reverse(ans1.begin(),ans1.end());
	for(int i : ans1){
		cout << tmp[i].second;
	}
	for(int i : ans2){
		cout << tmp[i].second;
	}
	cout << '\n';
}

/*
012120 201012 120201
*/
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t = 1;
	cin >> t;
	while(t --){
		solve();
	}
}

E. A Trivial String Problem

本题是一个和相同前后缀相关的题目。
观察发现，对于一个字符串，每次截取其尾部最短的合法部分，是最优的。
一个字符串的最长合法部分，可以由KMP算法（【模板】KMP）的第一步求得。
而最短的合法部分，可以通过记忆化搜索的方法解决。每轮递归到当前部分的最长合法部分，使得其合法部分变“短”，直到其最长合法部分不存在。
再对每一个询问DP即可。

#include<bits/stdc++.h>
#define int long long

using namespace std;

void solve(){
	int n,q;
	cin >> n >> q;
	string ss;
	cin >> ss;
	ss = "#" + ss;
	while(q --){
		int l,r;
		cin >> l >> r;
		
		string s = ss.substr(l,r-l+1);
	//	cout << s << endl;
		int m = s.size();
		s = "#" + s;
		vector<int> ne(m+1);
		for(int i = 2,j = 0; i <= m; i ++){
			while(j && s[i] != s[j+1]) j = ne[j];
			if(s[i] == s[j+1]) j ++;
			ne[i] = j;
		}
		
		vector<int> border(m+1,-1);
		auto find = [&](auto &&self,int u) -> int{
			if(border[u] != -1) return border[u];
			else{
				if(ne[u]) border[u] = self(self,ne[u]);
				else border[u] = u;
				return border[u];
			}
		};
		
		for(int i = 1; i <= m; i ++){
			border[i] = find(find,i);
		}
		
		vector<int> dp(m+1);
		int sum = 0; 
		for(int i = 1; i <= m; i ++){
			dp[i] = 1;
			if(border[i]) dp[i] = max(dp[i],dp[i-border[i]] + 1);
			sum += dp[i];
		}
		cout << sum << '\n';
	}
	
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t = 1;
	cin >> t;
	while(t --){
		solve();
	}
}

算法模板 KMP

struct KMP{
	string p;
	int m;
	vector<int> ne;
	KMP(string p) : p(p){
		m = p.size() - 1;
		ne.resize(m+1,0);
		for(int i = 2,j = 0; i <= m; i ++){
			while(j && p[i] != p[j+1]) j = ne[j];
			if(p[i] == p[j+1]) j ++;
			ne[i] = j;
		}
	}
	
	vector<int> work(string s){
		int n = s.size() + 1;
		vector<int> st(n+1);
		for(int i = 1,j = 0; i <= n; i ++){
			while(j && s[i] != p[j+1]) j = ne[j];
			if(s[i] == p[j+1]) j ++;
			if(j == m){
				st[i - m + 1] = 1;
				j = ne[j];
			}
		}
		return st;
	}
	
};

F. Dynamic Values And Maximum Sum

第一次操作后，所有值都聚集到子叶节点。而子叶节点的值不会再转移，所以从第二次操作开始，只用从大到小取子叶节点的值。
枚举第一次操作的位置，使用换根dp解决。
第二次操作需要维护前k大的和，使用平衡树、对顶堆都可以，本题解使用对顶堆。

#include<bits/stdc++.h>
#define int long long

using namespace std;

typedef pair<int,int> PII;

struct Twoheaps{
	int k;
	multiset<int> top, bot; // top: 最大的k个
	long long s = 0;       
	
	Twoheaps(int k) : k(k) {}
	
	void push(int x){

		if(top.size() < k){
			top.insert(x);
			s += x;
			return;
		}
		
		if(x > *top.begin()){
			int y = *top.begin();
			top.erase(top.begin());
			s -= y;
			bot.insert(y);
			
			top.insert(x);
			s += x;
		}else{
			bot.insert(x);
		}
	}
	
	void erase(int x){
		auto it = top.find(x);
		if(it != top.end()){
			top.erase(it);
			s -= x;
			if(!bot.empty()){
				auto it2 = prev(bot.end());
				top.insert(*it2);
				s += *it2;
				bot.erase(it2);
			}
		}else{
			auto it = bot.find(x);
			if(it != bot.end()) bot.erase(it);
		}
	}
	
	int getkth(){
		return *top.begin();
	}
	
	long long sum(){
		return s;
	}
};

struct depest{
	int dep,id,p;
};

void solve(){
	int n,k;
	cin >> n >> k;
	vector<int> a(n+1);
	for(int i = 1; i <= n; i ++){
		cin >> a[i];
	}
	
	vector<vector<int>> v(n+1);
	
	for(int i = 1; i <= n - 1; i ++){
		int x,y;
		cin >> x >> y;
		v[x].push_back(y),v[y].push_back(x);
	}
	
	if(k == 1){
		cout << *max_element(a.begin()+1, a.end()) << '\n';
		return;
	}
	
	vector<depest> mi(n+1);	
	auto dfs1 = [&](auto &&self,int u,int p) -> void{
		
		mi[u] = {0,u,-1};
		for(int i : v[u]){
			if(i != p){
				self(self,i,u);
				auto tmp = mi[i];
				tmp.dep ++;
				if(tmp.dep > mi[u].dep || (tmp.dep == mi[u].dep && tmp.id < mi[u].id)){
					mi[u] = {tmp.dep,tmp.id,i};
				}
			}
		}	
	};
	
	dfs1(dfs1,1,-1);
	vector<int> sum(n+1);
	for(int i = 1; i <= n; i ++){
		sum[mi[i].id] += a[i];
	}
	Twoheaps heap(k-1);
	for(int i = 1; i <= n; i ++){
		heap.push(sum[i]);
	}
	
	int ans = 0;
	auto dfs2 = [&](auto &&self,int u,int p) -> void{
	
		bool flag1 = false,flag2 = false;
		depest res1,res2;
		if(u != 1 && mi[p].p == u){
			flag1 = true;
			res1 = mi[p];
			//delete
			heap.erase(sum[mi[p].id]);
			sum[mi[p].id] -= a[p];
			heap.push(sum[mi[p].id]);
			
			mi[p] = {0,p,-1};
			for(int i : v[p]){
				if(i != u){
					auto tmp = mi[i];
					tmp.dep ++;
					if(tmp.dep > mi[p].dep || (tmp.dep == mi[p].dep && tmp.id < mi[p].id)){
						mi[p] = {tmp.dep,tmp.id,i};
					}
				}
			}
			
			heap.erase(sum[mi[p].id]);
			sum[mi[p].id] += a[p];
			heap.push(sum[mi[p].id]);
		}
		
		heap.erase(sum[mi[u].id]);
		sum[mi[u].id] -= a[u];
		heap.push(sum[mi[u].id]);
		
	//cout << u << ' ' << a[u] + heap.sum() << endl;
		ans = max(ans,a[u] + heap.sum());
		
		if(p != -1 && (mi[u].dep < mi[p].dep + 1 || (mi[u].dep == mi[p].dep + 1 && mi[p].id < mi[u].id))){
			flag2 = true;
			res2 = mi[u];
			mi[u] = {mi[p].dep + 1,mi[p].id,p};
		}
		
		heap.erase(sum[mi[u].id]);
		sum[mi[u].id] += a[u];
		heap.push(sum[mi[u].id]);
		
	
		for(int i : v[u]){
			if(i != p){
				self(self,i,u);
			}
		}	
		
		if(flag1){
			heap.erase(sum[mi[p].id]);
			sum[mi[p].id] -= a[p];
			heap.push(sum[mi[p].id]);
			
			mi[p] = res1;
			
			heap.erase(sum[mi[p].id]);
			sum[mi[p].id] += a[p];
			heap.push(sum[mi[p].id]);
		}
		
		if(flag2){
			heap.erase(sum[mi[u].id]);
			sum[mi[u].id] -= a[u];
			heap.push(sum[mi[u].id]);
			
			mi[u] = res2;
			
			heap.erase(sum[mi[u].id]);
			sum[mi[u].id] += a[u];
			heap.push(sum[mi[u].id]);
		}
		
	};
	dfs2(dfs2,1,-1);
	cout << ans << '\n';
}

signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int t = 1;
	cin >> t;
	while(t --){
		solve();
	}
}

算法模板 - 对顶堆

struct Twoheaps{
	int k;
	multiset<int> top, bot; // top: 最大的k个
	long long s = 0;       
	
	Twoheaps(int k) : k(k) {}
	
	void push(int x){

		if(top.size() < k){
			top.insert(x);
			s += x;
			return;
		}
		
		if(x > *top.begin()){
			int y = *top.begin();
			top.erase(top.begin());
			s -= y;
			bot.insert(y);
			
			top.insert(x);
			s += x;
		}else{
			bot.insert(x);
		}
	}
	
	void erase(int x){
		auto it = top.find(x);
		if(it != top.end()){
			top.erase(it);
			s -= x;
			if(!bot.empty()){
				auto it2 = prev(bot.end());
				top.insert(*it2);
				s += *it2;
				bot.erase(it2);
			}
		}else{
			auto it = bot.find(x);
			if(it != bot.end()) bot.erase(it);
		}
	}
	
	int getkth(){
		return *top.begin();
	}
	
	long long sum(){
		return s;
	}
};