Codeforces 305 E Playing with String
1238 ワード
転送ゲート:http://codeforces.com/problemset/problem/305/E
考え方:まず、各文字のサブストリングが独立したゲームとして見られます。最後の答えはすべての独立したゲームのSG値の違いと得ることができます。
コード:
考え方:まず、各文字のサブストリングが独立したゲームとして見られます。最後の答えはすべての独立したゲームのSG値の違いと得ることができます。
コード:
#include<cstdio>
#include<cstring>
#include<algorithm>
const int n=5010;
using namespace std;
int sg[n];char s[n];bool bo[n];
int getsg(int len){
if (sg[len]!=-1) return sg[len];
memset(bo,0,sizeof(bo));
bo[getsg(len-2)]=1;
for (int i=1;i+i<len;i++) bo[getsg(i-1)^getsg(len-i-2)]=1;
for (int i=0;i<n;i++) if (!bo[i]) 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];
printf("%d
",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);
for (int i=0;i<=10;i++) { printf("%d",sg[i]); }
while (scanf("%s",s)!=EOF){
bool sec=1;
for (int i=1,len=strlen(s);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
%d
",i+1),sec=0;break;
}
if (sec) puts("Second");
}
return 0;
}