传送门：>Here<
从来没打过\(CF\)（由于太晚了）…… 不知道开学了以后有没有机会能够熬夜打几场，毕竟到现在为止都是\(unrated\)好尴尬啊~
今天早上打了几题前几天的比赛题……
A. \(Doggo \ Recoloring\)
此题应当是签到题，但我还是傻了很久。很容易发现只要有任意一种狗的颜色超过\(1\)，那么这种狗就是可以变色的。那么它永远只需要变为任意一个与他相邻的狗的颜色，数量不会减少反而增多。因此可以不停变下去。于是我们只需要统计一下是否有一种颜色是大于等于两个的
代码就不贴了
B. \(Weakened \ Common \ Divisor\)
题意为给出\(N\)个整数对，要求找出任意一个数，能够被任意一对中的其中一个数整除。称为\(WCD\)
我的想法是先预处理出第一对的两个数的所有因子，然后遍历所有处理出来的因子，遍历后面的每一对——如果当前因子合法就输出。最后留下来的因子里随便取一个即可。\(T\)了第\(45\)个点……
事实上慢就慢在我们不能够处理因子，而是应当处理素因子。因为如果一个非素数\(x\)能够作为\(WCD\)，那么\(x\)的所有素因子肯定都可以满足。
/*By DennyQi 2018*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <cmath>
#define r read()
using namespace std;
typedef long long ll;
const int MAXN = 10010;
const int MAXM = 20010;
const int INF = 1061109567;
inline int Max(const int a, const int b){ return (a > b) ? a : b; }
inline int Min(const int a, const int b){ return (a < b) ? a : b; }
inline int read(){
int x = 0; int w = 1; register char c = getchar();
for(; c ^ '-' && (c < '0' || c > '9'); c = getchar());
if(c == '-') w = -1, c = getchar();
for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w;
}
int N,lim,t1;
ll f[200010],a[200010],b[200010];
inline void Fenjie(ll a){
for(ll i = 2; i * i <= a; ++i){
if(a % i == 0){
f[++t1] = i;
while(a % i == 0){
a /= i;
}
}
}
if(a > 1){
f[++t1] = a;
}
}
int main(){
N = r;
for(int i = 1; i <= N; ++i){
a[i] = r, b[i] =r ;
}
Fenjie(a[1]);
Fenjie(b[1]);
bool flg = 0;
for(int i = 1; i <= t1; ++i){
flg = 0;
for(int j = 2; j <= N; ++j){
if((a[j]%f[i] != 0) && (b[j]%f[i] != 0)){
flg = 1;
break;
}
}
if(!flg){
printf("%lld", f[i]);
return 0;
}
}
printf("-1");
return 0;
}
C. \(Plasticine \ zebra\)
给出一个字符串，每个字符不是\(b\)就是\(w\)。每一次操作可以选择一个断点，然后让断点两边的全部翻转。无论操作几次。定义一个斑马串，其相邻元素不重复、问最大的斑马串是多长？也就是要通过若干次操作找到最长的\(bwbwbw..\)或\(wbwbwb...\)
找到一个断点然后两边都翻转实际上是可以等价的。例如一个字符串\(abcdefgh\)，在\(c\)后面断了，那么就变为\(abc \ | \ defgh\)，翻转后得到\(cbahgfed\)。我们发现其等价于\(abc\)放到\(defgh\)后面，然后整个翻转。而如果我们找到了一个斑马串，其翻过来依然是斑马串。因此我们只需要把字符串本身复制一遍接在后面，然后在这个两倍的字符串中找到最长的斑马串。（长度不能超过\(N\)）。
为什么这样就好了呢？依然距离，将\(abcdefg\)复制一遍得到\(abcdefgabcdefg\)。任取一段长度为\(N\)的连续的子序列，其头尾相当于断点。因此这就相当于枚举了断点了
/*By DennyQi 2018*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#define r read()
using namespace std;
typedef long long ll;
const int MAXN = 10010;
const int MAXM = 20010;
const int INF = 1061109567;
inline int Max(const int a, const int b){ return (a > b) ? a : b; }
inline int Min(const int a, const int b){ return (a < b) ? a : b; }
inline int read(){
int x = 0; int w = 1; register char c = getchar();
for(; c ^ '-' && (c < '0' || c > '9'); c = getchar());
if(c == '-') w = -1, c = getchar();
for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w;
}
int N,ans;
char s[200010];
int f[200010];
int main(){
scanf("%s", s);
N = strlen(s);
for(int i = N; i < 2 * N; ++i) s[i] = s[i-N];
for(int i = 0; i < 2 * N; ++i){
if(i - 1 >= 0){
if(s[i] != s[i-1]){
f[i] = f[i-1] + 1;
}
else{
f[i] = 1;
}
}
else{
f[i] = 1;
}
if(f[i] <= N){
ans = Max(ans, f[i]);
}
}
printf("%d", ans);
return 0;
}
另外的几道题暂时还没做，有时间再更吧……