Codeforces Round 897 (Div. 2)(VP-9,寒假加训)

2024-01-09 14:41:38

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

文章来源:https://blog.csdn.net/Lanthamum/article/details/135473814
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。