Codeforces Round 662 赛后解题报告

梦幻开局到1400+的悲惨故事

A. Rainbow Dash, Fluttershy and Chess Coloring

这个题很简单，我们可以画几张图，发现每一次我们染色的最佳方法就是每次往里面多填一圈，并把上一圈给填满。

比如上图就很好地说明了这个过程，大家可以用画一下 \(n=4,n=5,n=6,n=7\)，就能验证这个命题了，所以一个 \(n\times n\) 的矩阵有 \(\lfloor\frac{n}{2}\rfloor+1\) 圈，所以直接输出即可。

//Don‘t act like a loser.
//You can only use the code for studying or finding mistakes
//Or,you‘ll be punished by Sakyamuni!!!
//#pragma GCC optimize("Ofast","-funroll-loops","-fdelete-null-pointer-checks")
//#pragma GCC target("ssse3","sse3","sse2","sse","avx2","avx")
#include<bits/stdc++.h>
#define int long long
using namespace std;

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch<‘0‘||ch>‘9‘) {
		if(ch==‘-‘)
			f=-1;
		ch=getchar();
	}
	while(ch>=‘0‘&&ch<=‘9‘) {
		x=x*10+ch-‘0‘;
		ch=getchar();
	}
	return f*x;
}

int n;

signed main() {
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	
	int t=read();
	while(t--) {
		n=read();
		
		cout<<n/2+1<<endl;
	}

	//fclose(stdin);
	//fclose(stdout);
	return 0;
}

B. Applejack and Storages

我们思考一下这个题给我们的信息。我们要用已有木棒拼出一个正方形和一个长方形。因为长方形的范围比正方形广，所以我们有一个贪心策略就是先判断是否有正方形再判断剩下的是否有长方形。

我们做的就是要统计有多少组木棒可以拼出正方形，我们记为 \(four\)（重复的木棒不能出现在两组中）。我们再来统计把所有 \(4\) 个木棒长度相等的组剔除后，有多少组是两个木棒程度相等的，记为 \(two\)。注意，由于我们的贪心策略，我们优先考虑 \(four\)。所以两组相等的二元组就会被我们合并成为一个四元组。

最后只要满足 \(four>0\) 且 \(two>1\)，或者 \(four>1\)，即拼出两个正方形，我们就输出 YES。否则 NO。

//Don‘t act like a loser.
//You can only use the code for studying or finding mistakes
//Or,you‘ll be punished by Sakyamuni!!!
#include<bits/stdc++.h>
#define int long long
using namespace std;

int read() {
	char ch=getchar();
	int f=1,x=0;
	while(ch<‘0‘||ch>‘9‘) {
		if(ch==‘-‘)
			f=-1;
		ch=getchar();
	}
	while(ch>=‘0‘&&ch<=‘9‘) {
		x=x*10+ch-‘0‘;
		ch=getchar();
	}
	return f*x;
}

const int maxn=1e5+10; 

int n,cnt[maxn],m,four,two;
char ch;

signed main() {
	n=read();
	for(int i=1;i<=n;i++) {
		int x=read();
		cnt[x]++;
		if(cnt[x]%4==0) {//先4后2
			four++;
			two--;
		}
		if(cnt[x]%4==2) {
			two++;
		}
	}
	m=read();
	
	for(int i=1;i<=m;i++) {
		cin>>ch;
		int x=read();
		if(ch==‘+‘) {
			cnt[x]++;
			if(cnt[x]%4==0) {//先4后2
				four++;
				two--;
			}
			if(cnt[x]%4==2) {
				two++;
			}
		}
		else {
			if(cnt[x]%4==0) {//先4后2
				four--;
				two++;
			}
			if(cnt[x]%4==2) {
				two--;
			}
			cnt[x]--;
		}
		
		if(four>0&&two>1) {
			printf("Yes\n");
		}
		else if(four>1) {
			printf("YES\n");
		}
		else {
			printf("NO\n");
		}
	}
	return 0;
}

Keep updating qwq

Codeforces Round 662 赛后解题报告

原文：https://www.cnblogs.com/huayucaiji/p/CF1393.html