codeforces 305E Playing with String

刚开始你只有一个字符串
每次能选择一个有的字符串s,找到i,满足
s[i - 1] = s[i + 1],将其分裂成3 个字符串
s[1 ··  i - 1]; s[i]; s[i + 1 ·· |s|]

不能操作者负,求先手必胜的一个策略
初始字符串长度不超过5000

将每个字符都能操作的连续的一段作为一个游戏,状态即可表示成这一段的长度

code:

 #include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#define maxn 5005
using namespace std;
char ch,s[maxn];
int n,sg[maxn],l,idx,tmp;
struct DATA{
int l,r,siz;
}list[maxn];
bool ok,bo[maxn],can[maxn],flag;
void read(int &x){
for (ok=,ch=getchar();!isdigit(ch);ch=getchar()) if (ch=='-') ok=;
for (x=;isdigit(ch);x=x*+ch-'',ch=getchar());
if (ok) x=-x;
}
void calc(int k){
for (int i=,t1,t2;i<=k;i++){
t1=(i-)-,t2=k-(i+);
if (t1>&&sg[t1]==-) calc(t1);
if (t2>&&sg[t2]==-) calc(t2);
}
memset(bo,,sizeof(bo));
for (int i=,t,t1,t2;i<=k;i++){
t1=(i-)-,t2=k-(i+),t=;
if (t1>) t^=sg[t1];
if (t2>) t^=sg[t2];
bo[t]=;
}
for (int i=;;i++) if (!bo[i]){sg[k]=i;break;}
}
int main(){
scanf("%s",s+);
n=strlen(s+);
for (int i=;i<n;i++) if (s[i-]==s[i+]) can[i]=;
for (int i=;i<n;i++){
if (can[i]&&!l) l=i;
if (!can[i]&&l) list[++idx]=(DATA){l,i-,i--l+},l=;
}
if (l) list[++idx]=(DATA){l,n-,n--l+};
memset(sg,-,sizeof(sg));
for (int i=;i<=idx;i++){
if (sg[list[i].siz]==-) calc(list[i].siz);
tmp^=sg[list[i].siz];
}
if (tmp){
puts("First");
for (int i=,t;i<=idx;i++){
t=sg[list[i].siz];
for (int j=list[i].l,t1,t2,t3;j<=list[i].r;j++){
t1=(j-)-list[i].l,t2=list[i].r-(j+),t3=;
if (t1>) t3^=sg[t1];
if (t2>) t3^=sg[t2];
if (!(tmp^t^t3)){printf("%d\n",j),flag=;break;}
}
if (flag) break;
}
}
else puts("Second");
return ;
}
上一篇:POJ 2438 (哈密顿回路)


下一篇:[UWP小白日记-6]页面跳转过度动画