牛客练习赛123

哈哈，智商又被强奸了。

是个人都会做B就我TM不会。

牛客练习赛123

A

签到。按题目要求照做。

int n;
string s;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n>>s;
	for(int i=0;i<n/2+(n&1);i++) putchar(s[i]);
	return 0;
}

B

有笨蛋看到题目写着鸽巢原理不知道这题和鸽巢原理啥关系。

哈哈，紫砂了。

这题思路类似于hdu1205，

先讲hdu1205思路：

将最多的一种糖果想象成鸽巢，将剩余其他糖果总和想象成鸽子，也就转换成了$\sum_{i=1}^{n}a_{i} -max{ a_{i}}$与$max{ a_{i}}$的问题

令$S=\sum_{i=1}^{n}a_{i} -max{ a_{i}}$，$N=max{ a_{i}}$。题意相当于在鸽巢间插入鸽子把鸽巢分隔开，鸽巢间插入鸽子又可以看做把鸽子放到前一个鸽巢中。

若$S < N-1$，那么必定有两个鸽巢连续，不合题意。

若$S == N-1$，那么除了最后一个鸽巢外每个鸽巢里正好有一只鸽子。

若$S > N-1$，因为$N=max{ a_{i}}$，所以其余的任意 $a_{i}$都不大于$N$，可以分到N个鸽巢中，每个鸽巢内的鸽子必定不重样。

结论是，$S\ge N-1$时必定有解。

那么回到本题。

对于一种小球$a_{i}$，我们尽可能把其他小球消去，那么消去的最优方案其实就是上面的吃糖方案。

若$\sum_{j=1}^{n}a_{j}-a_{i}-\max_{j\ne i}{a_{j}} \ge \max_{j\ne i}{a_{j}}-1$，即存在一种吃糖方案，那么剩余小球的数量就是$(\sum_{j=1}^{n}a_{j}-a_{i}) % 2$

若$\sum_{j=1}^{n}a_{j}-a_{i}-\max_{j\ne i}{a_{j}} < \max_{j\ne i}{a_{j}}-1$，即不存在吃糖方案，那么最终剩下的小球数为$\max_{j\ne i}{a_{j}}-(\sum_{j=1}^{n}a_{j}-a_{i}-\max_{j\ne i}{a_{j}})$

比较剩余小球数与$a_{i}$大小即可。

注意特判n=1的情况。

感觉好像和鸽巢原理也没什么关系

int T,n,a[1000006];
int main(){
	R(T);
	while(T--){
		R(n);
		long long sum=0;
		int mx1=0,mx2=0;
		for(int i=1;i<=n;i++){
			R(a[i]);
			sum+=a[i];
			if(a[i]>mx2) mx2=a[i];
			if(mx2>mx1) swap(mx2,mx1);
		} 
		if(n==1){
			puts("1");
			continue;
		}
		int i,mx;
		for(i=1;i<=n;i++){
			mx=mx1;
			if(a[i]==mx1) mx=mx2;
			if((sum-a[i]-mx>=mx-1&&((sum-a[i])&1)<a[i])||(sum-a[i]-mx<mx-1&&mx-(sum-a[i]-mx)<a[i]))
				printf("1 ");
			else
				printf("0 ");
		}
		puts("");
	}
	return 0;
}

CDEFG咕。

感想：

已经成老东西了，被大一的薄纱了。

这个写一场比赛被强奸一次智商的b样子要是让初三的自己看到怕是要笑死。

有点怀疑自己到底有没有在ACM继续呆下去的必要了。

唉，理想；唉，生活。本来说好了要再奋斗一个学期现在看来自己那点热情真是p都算不上。

真该考虑要不要转型CTF了。

（转到一个完全陌生的领域大概要更困难吧）