题意:刚开始你只有一个字符串每次能选择一个有的字符串 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]!=-) return sg[len];
++id;
bo[getsg(len-)]=id;
for(int i=;i+i<len;i++)
bo[getsg(i-)^getsg(len-i-)]=id;
for(int i=;i<N;i++) if(bo[i]!=id) return sg[len]=i;
}
int getans(int l,int r){
int sum=;
for(int i=l+;i<=r-;i++)
if(s[i+]==s[i-]){
int len=;
while(s[i+]==s[i-]&&i<=r-) i++,len++;
sum^=sg[len];
}
return sum;
}
int main(){
memset(sg,-,sizeof(sg));
sg[]=,sg[]=;
for(int i=;i<N;i++)
if(sg[i]==-) sg[i]=getsg(i);
while(scanf("%s",s)!=EOF){
bool flag=;int len=strlen(s);
for(int i=;i<len-;i++){
if(s[i-]!=s[i+]) continue;
if(getans(,i-)^getans(i+,len-)) continue;
printf("First\n%d\n",i+);flag=;break;
}
if(!flag) puts("Second");
}
return ;
}

最新文章

  1. Android悬浮窗实现 使用WindowManager
  2. CentOS7 SSH相关
  3. 论单页Web应用和RESTful架构
  4. javascript小知识1 this的用法
  5. 无源RS232转RS485(转)
  6. WPF Effect 造成的字体模糊
  7. WPF如何得到一个在用户控件内部的元素的坐标位置
  8. 第二章 Android系统与嵌入式开发
  9. listcard记录
  10. 彻底搞清楚javascript中的require、import和export
  11. org.springframework.web.util.WebUtils.isSameOrigin(WebUtils.java:816)
  12. UltraISO 9.7.0.3476中文完美破解安装版
  13. css加载字体跨域问题
  14. 比较@Resource、@Autowired
  15. hbase优缺点
  16. maven exclusions version
  17. IEEEXtreme 10.0 - Goldbach&#39;s Second Conjecture
  18. ASP.NET Web API总结
  19. python 学习分享-进程
  20. [413D][搜索]D - Field expansion

热门文章

  1. SummerVocation_Leaning--java动态绑定(多态)
  2. Spring Boot 前世今生
  3. JS进阶篇--JS数组reduce()方法详解及高级技巧
  4. ASP.NET 自定义路由 RouteBase
  5. 使用natapp本地映射外网服务
  6. PHP面向对象编程(1)基础
  7. vncserver 启动停止方式
  8. 4 Values whose Sum is 0 POJ - 2785
  9. Codeforces Round #460 (Div. 2)-C. Seat Arrangements
  10. CodeForces 781D Axel and Marston in Bitland DP