【CF】Codeforces Round #505 (Div. 1 + Div. 2)

终于上紫啦！

撒花！

---

刺激，一回二高就打CF，还好准备时间充裕，下了Firefox，调好Dev-C++，装了CF-Predictor。（广告预警）

强烈推荐插件 CF-Predictor ！让你实时了解预计Rating Change，从而面向Rating做题（逃

各大浏览器插件中心、Tampermonkey、搜索CF-Predictor，一分钱不要，白白带回家！

---以上是广告时间---

下面是正题：HackCodeforces Round #505题解。

---

题解

A. Doggo Recoloring

题意：给你一个字符串，每次操作你可以选择一个出现过两次或以上的字符，把它们全部变成你指定的另一个字符，你可以进行无限次操作，问你能否使得这个字符串只含一种字符。

题解：很容易发现，如果这个字符串中含有一个字符，它出现过两次或以上，那么你只需要把这几个字符变成另一种在这个字符串中出现过的字符，然后不停重复以上操作，最后得到的字符串就一定只含有一种字符了。

证明是显然的：若你能进行上述操作，那么答案一定是Yes，否则这个字符串不能进行任何操作，答案就是No（伏笔）。

所以就统计有没有一个字符出现过两次或以上。

快速码完了交上去，屏幕上显示着In queue，突然想到，n=1

咋没有撤回提交功能啊。。。。。。o(╥﹏╥)o

还是怪自己不细心，Wrong answer on pretest 4，-50pts。

证明是显然的：若你能进行上述操作，那么答案一定是Yes，否则这个字符串不能进行任何操作，答案就是No。n=1除外！！！！！一定是Yes！！！！！

Pretests passed，下一题。

 

B. Weakened Common Divisor

题意：给你n对数，让你找一个大于1的数x，满足x是每对数中其中一个的因子。

题解：一读懂题，开始瞎猜。

lc：把每对数求lcm，把求完lcm的n个数求gcd不就是答案吗。

于是大家一起疯狂码，lc：我WA了。

仔细一想，错的！

。。。。。。

一看时间：00:18:10

别卡B题啊（伏笔）。

老实（naive）的我思考了一下，能不能把这个做法改一下，20分钟后想到一种做法：把用上面的方法求得的答案取质因子。

正确性容易证明。

00:41:50  Pretests passed [pretests] 

咋花了41分钟（伏笔）才做出B啊。。。。凉透。。。。

突然一想，复杂度对吗？

然后往程序里一输入：

2
998244353 1000000007
998244353 1000000007

TLE！

求质因子极限要，然后两个大质数一乘再开根，Boom！

Pretests：

这Pretest有何用！！！

做法推翻。。。凉透。。。

lc：不对，你把第一对数的两个数都分解质因子，然后每个质因子暴力判就完了啊。

我怕是脑子抽了。

lc：00:45:53  Pretests passed [main tests]

然而我各种WA

01:10:09  Pretests passed  [main tests] 

咋01:10:09才过B啊。。。。。

一看分数：370

比A还少。。。。。

一定有人写我之前的做法的，果断锁。

 

C. Plasticine zebra

题意：给你一个01串，你可以把这个字符串从任何位置切开，两边各自翻转，拼回来。可以进行无限多次。求你经过这些操作后能得到的字符串中01相间子串的最长长度。

题解：就在码B题的时候（就是lc过了B我还在各种WA的时候）

lc（就在我正后方一米）：啊~~~~~我C过了！！！！！！！！！！！！！！

lc：就是你把这个串倍长，然后求它的最长01相间子串长度就可以了。

你也先等我过了B啊，大佬。

然后看到lc的status：

01:00:46  Pretests passed [pretests]

01:02:29  Hacked by cubercsl

同时lc：等等我C被hack了！

谢谢，我放心码B题了，大佬。

lc：哦答案要与原串长度取min。我再交。

然后等了很久，没有被hack。

应该是正解了。。。我刚好过了B，于是码完C，Pretests passed。

我：真的是正解吗，你要不要锁一下看看别人怎么写。

lc：你锁吧。

我：（狠心）反正我B锁了，那我把C也锁了吧！（切勿模仿，幸好没有伏笔）

好像真的这样做啊。

回宿舍的路上想到的粗略证明：把这个串进行操作后一定是倍长串的子串。

 

下面进入 Hackforces 讲故事时间：

看D题，暂时没有思路。

翻翻别人B题的代码，前几个看来很正经，突然看到一个，怎么这么熟悉？？？

for(ll i=2;i*i<=ans;++i)
{
    if(ans%i==0)
    {
        cout<<i;
        return 0;
    }
}
cout<<ans;

这不就是我之前的做法吗！

点下hack it!，输入那组数据：

2
998244353 1000000007
998244353 1000000007

来不及犹豫了！ 按下Hack按钮

In queue...

心跳加速中...

状态up！八分钟后

这时候有个人来hack我的B题，然而他并没有成功。我一看他的代码结尾，熟悉的for循环！

这个Room的B题貌似就没有用那种做法的了，于是看看Locked的C题。原本没抱太多希望，因为我们Room早有人把C题锁了，让我联想到lc房的那位大佬，一看到有人没取min就光速hack掉，于是我便以为我们Room锁了C的人也把没取min的hack了。

然而事实是这样的：

这个人答案没取min！

这个人代码好丑，但是答案没取min！

这个人答案也没取min！

然而这时候，CF-Predictor告诉我，我还是会掉Rating的（伏笔）！

那死也要把D题暴力打出来，FST就FST！

 

D. Recovering BST

题意：给你n个数，让你判断，是否用这些数组成一棵二叉搜索树，使得每条边上的两个数的gcd不为1。

题解：不会啊。我只会打暴力，正解是的dp啊。

场上写了个的暴搜，过了Pretest。

还把System test过了！！！

也许复杂度是对的

好吧其实原因可能是用了bitset压位，常数极小。

 

---

 

代码

A

#include <bits/stdc++.h>
using namespace std;

int cnt[30];

int main()
{
	int n;
	string s;
	cin >> n >> s;
	for(int i=0;i<s.length();++i)++cnt[s[i]-'a'];
	for(int i=0;i<26;++i)if(cnt[i]>=2){puts("Yes");return 0;}
	if(n==1)puts("Yes");
	else puts("No");
}

 B

#include <bits/stdc++.h>
using namespace std;

int s[10000001],isp[10000001];
bool flag[10000001];

int main()
{
	int n,a,b;
	scanf("%d",&n);
	scanf("%d%d",&a,&b);
	if(n==1){if(a==1)printf("%d\n",b==1?-1:b);else printf("%d\n",a);return 0;}
	for(register int i=2;i<=45000;++i)
	{
		bool check=true;
		for(register int j=2;j<=sqrt(i);++j)
			if(i%j==0)
			{
				check=false;
				break;
			}
		isp[i]=check;
	}
	for(int i=2;i<=sqrt(a);++i)
	{
		if(a%i==0 && isp[i])s[++s[0]]=i;
		while(a%i==0)a/=i;
	}
	if(a>1)
		s[++s[0]]=a;
	for(int i=2;i<=sqrt(b);++i)
	{
		if(b%i==0 && isp[i])s[++s[0]]=i;
		while(b%i==0)b/=i;
	}
	if(b>1)
		s[++s[0]]=b;
	memset(flag,true,sizeof(flag));
	for(int i=2;i<=n;++i)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		for(int j=1;j<=s[0];++j)
		{
			if(a%s[j]!=0 && b%s[j]!=0)flag[j]=false;
		}
	}
	int ans=-1;
	for(int i=1;i<=s[0];++i)if(flag[i])ans=s[i];
	printf("%d\n",ans);
}

C

#include <bits/stdc++.h>
using namespace std;

int main()
{
	string s;
	cin >> s;
	string t=s;
	s+=t;
	int ans=1,now=1;
	for(int i=1;i<s.length();++i)
	{
		if(s[i]==s[i-1])now=1;
		else ++now;
		ans=max(ans,now);
	}
	cout << min((int)t.length(),ans);
}

 D

#include<bits/stdc++.h>
using namespace std;

int n,a[701];
bitset<701> vis2[701][701],ans[701][701];
bool ok[701][701];

int check(int l,int r,int root)
{
	if(r<l)return true;
	if(l==r)return ok[l][root];
	if(vis2[l][r][root])return ans[l][r][root];
	for(int i=l;i<=r;++i)
		if(ok[i][root] && check(l,i-1,i) && check(i+1,r,i))
		{
			vis2[l][r][root]=1;
			ans[l][r][root]=1;
			return true;
		}
	vis2[l][r][root]=2;
	return false;
}

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf("%d",a+i);
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
			ok[i][j]=__gcd(a[i],a[j])!=1;
		ok[0][i]=true;
		ok[i][0]=true;
	}
	if(check(1,n,0))puts("Yes");else puts("No");
}

比赛结束后大半部分的人都FST了，其实不做D也能涨的。

下一场Codeforces，Div.1见！