https://codeforces.com/contest/1025
A - Doggo Recoloring
题意：有n块色块，每次可以把一种至少两块的同颜色的换成另一种颜色，求是否可以使得全部变成同颜色。
题解：小心n==1的情况。
int n;
char s[200005];
int cnt[256];
void test_case() {
scanf("%d%s", &n, s + 1);
if(n == 1) {
puts("Yes");
return;
}
for(int i = 1; i <= n; ++i)
cnt[s[i]]++;
bool suc = 0;
for(int i = 0; i < 256; ++i) {
if(cnt[i] >= 2) {
suc = 1;
break;
}
}
puts(suc ? "Yes" : "No");
}
B - Weakened Common Divisor
题意：有n对数，每对数是(a,b)，找一个数x，使得x对每一对数，都满足x是a的因数或者x是b的因数。
题解：枚举第一对数的因数，不超过30多种，然后暴力判断。
int n;
int fac[105], ftop;
const int MAXN = 1e6;
int p[MAXN + 5], ptop;
bool np[MAXN + 5];
void get_fac() {
int a, b;
scanf("%d%d", &a, &b);
ftop = 0;
for(int i = 1; i <= ptop; ++i) {
if(a % p[i] == 0) {
fac[++ftop] = p[i];
while(a % p[i] == 0)
a /= p[i];
}
}
if(a > 1)
fac[++ftop] = a;
for(int i = 1; i <= ptop; ++i) {
if(b % p[i] == 0) {
fac[++ftop] = p[i];
while(b % p[i] == 0)
b /= p[i];
}
}
if(b > 1)
fac[++ftop] = b;
sort(fac + 1, fac + 1 + ftop);
ftop = unique(fac + 1, fac + 1 + ftop) - (fac + 1);
}
int a[200005], b[200005];
void test_case() {
int C = 2e9;
for(ll i = 2; i * i <= C; ++i) {
if(np[i])
continue;
else {
p[++ptop] = i;
for(int j = i + i; j <= MAXN; j += i)
np[j] = 1;
}
}
scanf("%d", &n);
get_fac();
for(int i = 2; i <= n; ++i)
scanf("%d%d", &a[i], &b[i]);
for(int i = 1; i <= ftop; ++i) {
int p = fac[i];
int suc = 1;
for(int j = 2; j <= n; ++j) {
if(a[j] % p != 0 && b[j] % p != 0) {
suc = 0;
break;
}
}
if(suc) {
printf("%d
", p);
return;
}
}
puts("-1");
}
取y=a*b/gcd(a,b)，然后取y的gcd，这样是错的，例如：
1
4 6
暴力分解每个数，然后求公因数的交集，这样会T。
应该写一个分解整数的小型模板，免得重复搞。
C - Plasticine zebra
题意：给一个bw序列，可以进行多次操作，每次选择一个位置剪断，然后把两边反向，求最长的bw相间的长度。
题解：一开始还在考虑dp（同时考虑头部和尾部），但是这很明显是会因为前面的决策改变后面的bw的排列的。正解是把这个序列看成一个环，然后每次操作相当于只是在环上面剪断一个口，至于方向是无所谓的。所以得到一个算法就是要找这个环上面的最长的bw相间的长度。暴力的做法就是n^2的，当然可以仿照之前处理环形的一概做法，延长两倍变成链，然后就可以双指针转移。
首先先验证整个环长度不是bw间隔，那么在一个周期内一定会被切断，这时每次转移只需要考虑右边端点的连续性，不再需要从左边端点断开。
char s[200005];
void test_case() {
scanf("%s",s+1);
int n=strlen(s+1);
if(n==1){
puts("1");
return;
}
bool suc=(n%2==0);
for(int i=2;suc&&i<=n;++i){
if(s[i]==s[i-1]){
suc=0;
break;
}
}
if(suc){
printf("%d
",n);
return;
}
for(int i=1;i<=n;++i)
s[i+n]=s[i];
int maxlen=1;
int curlen=1;
for(int i=2;i<=2*n;++i){
if(s[i]==s[i-1])
curlen=1;
else{
++curlen;
maxlen=max(maxlen,curlen);
}
}
printf("%d
",maxlen);
}
D - Recovering BST
题意：给一个严格升序序列，问是否可以还原成BST，要求每条边的两端的点的权值不互质。
题解：有个很简单的dp解法：设dp[l][r][m]表示区间[l,r]以m为根节点是否可行，那么转移的时候要枚举状态n^3，然后对于一个状态要枚举两边子树的根，总复杂度n^4，太大了。官方题解：设dpl[l][r]表示区间[l,r]作为l-1的右子树是否可行，dpr[l][r]表示区间[l,r]作为r+1的左子树是否可行。
这样子处理，最后只需要枚举m，然后确定dpl[m+1][n]为1且dpr[1][m-1]为1，即可；转移的时候dpl[l][r]首先要找出[l,r]中的一个m，m与l-1的gcd不为1，再仿照上例转移。