2021.11.3 CCPC桂林 打铜总结

1.比赛体验

感觉主办方从一开始就非常欢乐，然后各种聊天也非常友善。血亏没去线下。（我与疫情不共戴天！！！）

感觉这次体验还不错，就是志愿者配环境非常辛苦（辛苦各位志愿者了！！！）

题目质量我感觉还行，反正我们队也只开了几个题，至少从开了的题看是这样（菜）。系统质量也挺好，做题和打印都蛮舒服的。以后可以保持~

人生第一块XCPC牌子。虽然没打银很遗憾吧，不过也算可以接受了。

2.比赛过程

1.热身赛

搞了三个澳门原题。做过，但没补。

随便写了写跑路了

过程略。

2.正赛

前一天睡的很早，然而没有屌用。半夜被吵醒了（虽然说EDG冠军大家都高兴吧，但是半夜大喊大叫是不是还是不太好）。

比赛开始精力倒还行。

但是看到了这个东西：

这就很难受了！！！！

作为一个熬夜躲被窝里看了LGD所有比赛的人，我裂开来 为什么不BAN猛犸！！！

然后怒WA一发签到。（三年ACM一场空，不开long long 见祖宗）

在很快的签完两个题A,I以后，开始分开看题。

很快锁定一个比较签的题G，看了一眼二分答案裸题。

赶紧跑上去敲 ,写了两分钟觉得假了换CRB上去写D，于是第40分钟光速WA了一发

换我来写G，于是跌跌撞撞的连WA两发以后，终于73分钟（+2）过了G

然后Julytree跑来说H是她最近猛练一段时间的AC自动机套一个什么东西，非常自信的上去写。我也不会AC自动机，就让她先写着。

然后光速T掉。

期间CRB还过来WA了一发D。

然后H调到大概130分钟（-4）的时候，发现全场只有我们队交过4发H，我一想这不是必然假了么，赶紧劝队友换题。

这时候我已经看了一个小时E了，然而还是不会。（过了一会发现题读假了，果然读题不规范，队友两行泪）

（一个插曲：隔壁队的第六版牛津字典没有 无环的 那个词，他们懵了一整场。幸亏我们是第七版。）

终于在第156分钟赛程过半的时候，CRB调过了D（+2），正式进入铜牌区。

然后陷入一段时间的挂机。

去年昆明打铁历历在目。于是我秃然想到，答案会不会至多只有2。

想了想好像还真没有反例。那不就是判个费用最小环吗？

于是直接一发dij上去，果然 AC（214分钟）。当时还有一个半小时，CRB又喂来一个B的思路，讨论下觉得可行，就上了。

于是一顿WA。最后也没有调出来。由于我们前期失误挺多的，罚时有点大，遂告别银牌。

赛后看题解，发现思路一毛一样（哭哭！），唉！

3.赛时通过题目

A.A Hero Named Magnus

签到题，LGD不浪稳赢

I.PTSD

签到题

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int T;ll n;
ll ans;
int a[1000500];
char x;
int main(){
	cin>>T;
	while(T--){
		ans=0;
		scanf("%lld",&n);
		for(int i=1;i<=n;i++){
			x=getchar();
			while(x!='0'&&x!='1')x=getchar();
			a[i]=x-'0';
		}
		int sum0=0;
		for(int i=n;i>=1;i--){
			if(sum0&&a[i]){
				sum0--;
				ans+=i;
			}
			else sum0++;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

G.Occupy the Cities

二分答案，对于每个答案，判断每个点向左占领能不能满足，如果向左恰好是答案，那标记下，下一个点向左跑的时候就要多跑一个点。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 1000005
int T;int n;
char s[N];
int a[N];
int ans;
int pos[N];
int b[N],cnt;
int check(int x){
	if(pos[1]-1>x) return 0;
	if(pos[1]-1==x) b[1]=1;
	for(int i=2;i<=cnt;i++){
		int now=pos[i]-pos[i-1]-1;
		
		if(now==0) continue;
		if(b[i-1]) now++;
		//cout<<now<<endl;
		if(now/2+now%2>x){
			return 0;
		}
		if(now/2==x){
			if(now%2==0) b[i]=1;
		}
	}
	if(b[cnt]){
		if(n-pos[cnt]+1>x) return 0;
	}
	else{
		if(n-pos[cnt]>x) return 0;
	}
	return 1;
}
int main(){
	cin>>T;
	while(T--){
		scanf("%d",&n);
		scanf("%s",s+1);cnt=0;
		for(int i=1;i<=n;i++){
			a[i]=s[i]-'0';
			if(a[i]) pos[++cnt]=i;
			b[i]=0;
		}
		int l=1,r=n;ans=0;
		if(cnt!=n) while(l<=r){
			int mid=(l+r)>>1;
			for(int i=1;i<=cnt;i++) b[i]=0;
			if(check(mid)){
				ans=mid;
				r=mid-1;
			}
			else l=mid+1;
		}
		
		printf("%d\n",ans);
	}
}
/*
1
7
0100101
*/

D.Assumption is All You Need

构造，队友写的，我不擅长。
大概思路是从后往前枚举，能换则换，对于每个要换过来的数，从前往后在跑一遍，看看有没有交换可以得到更优解的，复杂度o(n^2)

E.Buy and Delete

图论，考虑所有点都买不起，就是0，买不起环，就是1，买的起环，就是2.所以答案是：对每个点跑dijstra，假如有环回到了起点，就判断下能不能买的起。复杂度o（nmlogn）

4.总结

罚时很重要！！！
不要随便开没人过的题~
还是有点可惜了。可能是唯一一站在役的CCPC？打铜多少有点遗憾~
沈阳加油！希望能拿一块银~
祝CCPC越办越好。