首页 > 代码库 > Playing with String(codeforces 305E)
Playing with String(codeforces 305E)
题意:刚开始你只有一个字符串每次能选择一个有的字符串 s,找到 i,满足s[i - 1] = s[i + 1],将其分裂成 3 个字符串s[1 · · · i - 1]; s[i]; s[i + 1 · · · len]不能操作者负,求先手必胜的一个策略
初始字符串长度不超过 5000
/* 一个很暴力的转移方法设SG[i][j],每次枚举断点,但是这样是O(n^3)的。 其实我们可以发现,只有一段连续的符合s[i-1]=s[i+1]的字符串才能有贡献,所以可以设SG[len]来进行转移。 */ #include<cstdio> #include<cstring> #define N 5010 using namespace std; int sg[N],bo[N],id;char s[N]; int getsg(int len){ if(sg[len]!=-1) return sg[len]; ++id; bo[getsg(len-2)]=id; for(int i=1;i+i<len;i++) bo[getsg(i-1)^getsg(len-i-2)]=id; for(int i=0;i<N;i++) if(bo[i]!=id) return sg[len]=i; } int getans(int l,int r){ int sum=0; for(int i=l+1;i<=r-1;i++) if(s[i+1]==s[i-1]){ int len=0; while(s[i+1]==s[i-1]&&i<=r-1) i++,len++; sum^=sg[len]; } return sum; } int main(){ memset(sg,-1,sizeof(sg)); sg[0]=0,sg[1]=1; for(int i=2;i<N;i++) if(sg[i]==-1) sg[i]=getsg(i); while(scanf("%s",s)!=EOF){ bool flag=0;int len=strlen(s); for(int i=1;i<len-1;i++){ if(s[i-1]!=s[i+1]) continue; if(getans(0,i-1)^getans(i+1,len-1)) continue; printf("First\n%d\n",i+1);flag=1;break; } if(!flag) puts("Second"); } return 0; }
Playing with String(codeforces 305E)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。