Codeforces Round 897 (Div. 2)（VP-9，寒假加训）

VP时间

A.贪心

A大B就小，B小A就大

排序

wa4发

5.ac

B.

计算贡献

中间贡献1

左右两边贡献

如果相等贡献2

如果不相等贡献1

1.ac

C.贪心

Alice放入小的，才能得到大的

Bob拿走的肯定是小的，Alice得放回来

Bob拿0，Alice放回去

无限循环

我们只要考虑第一次操作即可

第一次放mex即可

cout<<endl 自动刷新缓冲区

1.Idleness limit exceeded on test?1

2.ac

题解

A.

这个很贪得想会

// Problem: A. green_gold_dog, array and permutation
// Contest: Codeforces - Codeforces Round 897 (Div. 2)
// URL: https://codeforces.com/contest/1867/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　??〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//	　　＞―r￣￣`ｰ―＿
#include <iostream>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N =4e4+ 9;
int ans[N];
struct node{
	int num,index;
}a[N];
bool cmp(node a,node b){
	return a.num<b.num;
}
void solve() {
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].num;
		a[i].index=i;
	}
	sort(a+1,a+1+n,cmp);
	for(int i=1;i<=n;i++){
		ans[a[i].index]=n-i+1;
	}
	for(int i=1;i<=n;i++){
		cout<<ans[i]<<" ";
	}
	cout<<'\n';
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> q;
	while (q--) {
		solve();
	}

	return 0;
}

B.

求回文串

从中间入手往两边延伸

如果两边一样记录一下goodbi++(好的一对)

如果两边不一样记录一下badbi++(坏的一对）

如果要构造成回文串

至少要变badbi次，至多就是badbi+goodbi*2(闲的没事干把好的一起变)

奇数还要考虑中间那个数字，至多badbi+goodbi*2+1(中间那个数字也可以变)

让这些位置都被赋值1，其他是0

// Problem: B. XOR Palindromes
// Contest: Codeforces - Codeforces Round 897 (Div. 2)
// URL: https://codeforces.com/contest/1867/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)
#include<iostream>
using namespace std;
const int N=1e5+9;
int ans[N];
struct {
	void start(){
		int n;
		cin>>n;
		string s;
		cin>>s;
		int badbi=0,goodbi=0;
		for(int i=0;i<=n;i++){
			ans[i]=0;
		}
		s=" "+s;
		for(int i=1;i*2<=n;i++){
			if(s[i]==s[n-i+1]){
				goodbi++;
			}else{
				badbi++;
			}
		}
		for(int i=0;i<=goodbi;i++){
			ans[badbi+i*2]=1;
			if(n&1){
				ans[badbi+i*2+1]=1;
			}
		}
		for(int i=0;i<=n;i++){
			cout<<ans[i];
		}
		cout<<'\n';
	}
}Genshin;
int main(){
	int q;
	cin>>q;
	while(q--){
		Genshin.start();
	}
	return 0;
}

C.

互动题

Idleness limit exceeded on test?1 这种错误要<<endl刷新缓冲区

// Problem: C. Salyg1n and the MEX Game
// Contest: Codeforces - Codeforces Round 897 (Div. 2)
// URL: https://codeforces.com/contest/1867/problem/C
// Memory Limit: 256 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//へ　　　　　／|
//　　/＼7　　　 ∠＿/
//　 /　│　　 ／　／
//　│　Z ＿,＜　／　　 /`ヽ
//　│　　　　　ヽ　　 /　　〉
//　 Y　　　　　`　 /　　/
//　ｲ●　､　●　　??〈　　/
//　()　 へ　　　　|　＼〈
//　　>ｰ ､_　 ィ　 │ ／／
//　 / へ　　 /　ﾉ＜| ＼＼
//　 ヽ_ﾉ　　(_／　 │／／
//	　　7　　　　　　　|／
//	　　＞―r￣￣`ｰ―＿
#include <iostream>
#include <cstring>
#include <iomanip>
#include <ctime>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#define eps 1e-5
#define INF 1e9
using namespace std;
typedef long long ll;
const int N = 2e6 + 9;
int a[N];
void solve() {
	int n;
	int y;
	cin>>n;
	set<int>st;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		st.insert(a[i]);
	}
	int mex=0;
	for(int i=0;i<=n;i++){
		if(!st.count(i)){
			mex=i;
			break;
		}
	}
	cout<<mex<<endl;
	cout.flush();
	while(1){
		int y;
		cin>>y;
		if(y==-1){
			return;
		}
		cout<<y<<endl;
	}
	cout.flush();
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int q;
	cin >> q;
	while (q--) {
		solve();
	}
	cout.flush();
	return 0;
}