---

Codeforces 1025

比赛链接

为什么我room里的都不hack别人。。那么明显的错。。

A.Doggo Recoloring

//只要能找到一个出现次数大于等于2的颜色就可以了。注意n=1特判。。

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

const int N=1e5+5;

int tm[300];

char s[N];

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

int main()

{

	int n=read(); scanf("%s",s+1);

	if(n==1) return puts("Yes"),0;

	for(int i=1; i<=n; ++i) ++tm[s[i]];

	for(int i='a'; i<='z'; ++i) if(tm[i]>1) return puts("Yes"),0;

	puts("No");

	return 0;

}

B.Weakened Common Divisor

任意一对总要有个满足的，任找一对分解质因数就可以了。

分解质因数的过程很zz。。不用筛直接枚举到sqrt(n)就行了。。

分解完后要判一次。

//61ms	2400KB

#include <cmath>

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

const int N=2e5+5;

int n,A[N],B[N],P[N],cnt;

bool not_P[N];

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

void Make_Table(int n)

{

	for(int i=2; i<=n; ++i)

	{

		if(!not_P[i]) P[++cnt]=i;

		for(int j=1; j<=cnt&&i*P[j]<=n; ++j)

		{

			not_P[i*P[j]]=1;

			if(!(i%P[j])) break;

		}

	}

}

bool Check(int x)

{

	for(int i=1; i<=n; ++i) if(A[i]%x && B[i]%x) return 0;

	return 1;

}

int main()

{

	n=read();

	for(int i=1; i<=n; ++i) A[i]=read(), B[i]=read();

	Make_Table(sqrt(std::max(A[1],B[1])));

	int now=A[1];

	for(int i=1; i<=cnt&&P[i]<=now; ++i)

		if(!(now%P[i]))

		{

			if(Check(P[i])) return printf("%d\n",P[i]),0;

			if(P[i]*P[i]!=now && now!=P[i] && Check(now/P[i])) return printf("%d\n",now/P[i]),0;

			while(!(now%P[i])) now/=P[i];

		}

	if(now!=1 && Check(now)) return printf("%d\n",now),0;

	now=B[1];

	for(int i=1; i<=cnt&&P[i]<=now; ++i)

		if(!(now%P[i]))

		{

			if(Check(P[i])) return printf("%d\n",P[i]),0;

			if(P[i]*P[i]!=now && now!=P[i] && Check(now/P[i])) return printf("%d\n",now/P[i]),0;

			while(!(now%P[i])) now/=P[i];

		}

	if(now!=1 && Check(now)) return printf("%d\n",now),0;

	puts("-1");

	return 0;

}

C.Plasticine zebra

找些串试试可以发现（串只有两种字符！真不懂我为什么拿abcd试半天），不管怎么切都相当于将串循环右移某些长度。

所以在循环表示里找最长的就可以了。注意答案对原串长度取min！

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#define gc() getchar()

const int N=2e5+5;

char s[N];

int main()

{

	scanf("%s",s+1);

	int l=strlen(s+1),res=0;

	for(int i=1; i<=l; ++i) s[i+l]=s[i];

	l<<=1;

	for(int now=1,i=2; i<=l; ++i,res=std::max(res,now))

		if(s[i]!=s[i-1]) ++now;

		else now=1;

	printf("%d\n",std::min(res,l>>1));

	return 0;

}

---

比赛结束后

D.Recovering BST(DP (bitset))

\(f[l][r][rt]\)表示\(l\sim r\)以\(rt\)为根是否可行，转移时枚举\(l,r,rt\)，再枚举左右子树的根。当存在\(f[l][rt-1][rt_{left}]==1\ \&\&\ f[rt+1][r][rt_{right}]==1\ \&\&\ rt_{left},rt_{right}均可与rt连边\) 时，\(f[l][r][rt]=1\)。

最后一层枚举总共是\(O(r-l)\)的，一共\(O(n^4)\)。

但是一个区间是否合法，我们只需要知道左右能否拼起来。我们用\(L[l][k]/R[k][r]\)表示以\(k\)为根往左/右是否能延伸到\(l/r\)。

那么区间\([l,r]\)合法 当且仅当存在k满足 \(L[l][k]==1\ \&\&\ R[k][r]==1\)。当\([l,r]\)合法后就可以根据\(k\)更新\(L[l][r+1]\)和\(R[l-1][r]\)了。

这样只需枚举区间和子树的根，复杂度\(O(n^3)\)。

可以用bitset优化。

数据感觉好水啊。。L,R更新都错了还是在51个点WA。

另外果然有更神奇的做法。。贪心么。。?

//202ms	1800KB

#include <cstdio>

#include <cctype>

#include <algorithm>

#define gc() getchar()

const int N=707;

int n,A[N];

bool ok[N][N],L[N][N],R[N][N],ans[N][N];

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

int Gcd(int a,int b){

	return b?Gcd(b,a%b):a;

}

int main()

{

	n=read();

	for(int i=1; i<=n; ++i) A[i]=read(), L[i][i]=R[i][i]=1;

	for(int i=1; i<n; ++i)

		for(int j=i+1; j<=n; ++j) ok[i][j]=(Gcd(A[i],A[j])>1);

	for(int len=0; len<n; ++len)//得先用长度为1的区间更新一次。。

		for(int l=1,r; (r=l+len)<=n; ++l)

			for(int k=l; k<=r; ++k)

				if(L[l][k] && R[k][r])

					ans[l][r]=1, L[l][r+1]|=ok[k][r+1], R[l-1][r]|=ok[l-1][k];

	puts(ans[1][n]?"Yes":"No");

	return 0;

}

bitset：

//93ms	100KB

#include <cstdio>

#include <cctype>

#include <bitset>

#include <algorithm>

#define gc() getchar()

const int N=707;

int n,A[N];

std::bitset<N> ok[N],L[N],R[N],ans[N];

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

int Gcd(int a,int b){

	return b?Gcd(b,a%b):a;

}

int main()

{

	n=read();

	for(int i=1; i<=n; ++i) A[i]=read(), L[i][i]=R[i][i]=1;

	for(int i=1; i<n; ++i)

		for(int j=i+1; j<=n; ++j) ok[i][j]=ok[j][i]=(Gcd(A[i],A[j])>1);

	for(int len=0; len<n; ++len)

		for(int l=1,r; (r=l+len)<=n; ++l)

		{

			ans[l]=L[l]&R[r];

			if((ans[l]&ok[r+1]).count()) L[l][r+1]=1;

			if((ans[l]&ok[l-1]).count()) R[r][l-1]=1;//l-1是第二维啊

		}

	puts(ans[1].count()?"Yes":"No");

	return 0;

}