题目分析:

一开始没想到SG函数,其它想到了就开始敲,后来发现不对才发现了需要SG函数。

把每个字母单独提出来,可以发现有用的区间只有两个字母之间的区间和一个位置到另一个字母的不跨越另一个相同字母的位置。

对于这些区间,用区间DP处理出来答案,合并答案的时候用SG函数。

代码:

 #include<bits/stdc++.h>
using namespace std; const int maxn= ; int n,q;
char str[maxn];
int pre[][maxn],suf[][maxn];
int arr[][maxn],ar[][maxn];
int Pf[][maxn],Sf[][maxn]; int solve(int,int,int); int hd(int k,int l,int r,int dep){
if(ar[k][l]) return Sf[k][l];
else {
ar[k][l]=,Sf[k][l] = solve(l,r,dep+);
return Sf[k][l];
}
}
int pd(int k,int r,int l,int dep){
if(arr[k][r]) return Pf[k][r];
else{
arr[k][r] = ,Pf[k][r] = solve(l,r,dep+);
return Pf[k][r];
}
} int app[maxn][];
int solve(int l,int r,int dep){
if(l > r) return ;
if(l == r) return ;
for(int k=;k<=;k++) app[dep][k] = ;
for(int k=;k<;k++){
int pv = suf[k][l],sv = pre[k][r];
if(pv > r || sv < l || pv == - || sv == -) continue;
int ans = Pf[k][sv]^Pf[k][pv];
if(pre[k][r] != r) ans ^= pd(k,r,sv+,dep);
if(suf[k][l] != l) ans ^= hd(k,l,pv-,dep);
app[dep][ans] = ;
}
for(int i=;i<=;i++) if(app[dep][i] == ) return i;
} void init(){
for(int i=;i<n;i++){
if(i->=&&pre[str[i]-'a'][i-]!=-){
int k = str[i]-'a';
if(pre[k][i-]+>i-) Pf[k][i]=Pf[k][pre[k][i-]];
else Pf[k][i]=Pf[k][pre[k][i-]]^Pf[k][i-];
arr[k][i] = ;
}
for(int k=;k<;k++){
if(pre[k][i] == -) continue;
if(arr[k][i]) continue;
if(pre[k][i] != i) Pf[k][i] = solve(pre[k][i]+,i,);
arr[k][i] = ;
}
}
for(int i=n-;i>=;i--){
if(i+<n&&suf[str[i]-'a'][i+]!=-){
int k = str[i]-'a';
if(i+ > suf[k][i+]-) Sf[k][i]=Sf[k][suf[k][i+]];
else Sf[k][i]=Sf[k][suf[k][i+]]^Sf[k][i+];
ar[k][i] = ;
}
for(int k=;k<;k++){
if(suf[k][i] == -) continue;
if(ar[k][i]) continue;
if(suf[k][i] != i) Sf[k][i] = solve(i,suf[k][i]-,);
ar[k][i] = ;
}
}
} void read(){
scanf("%s",str);
scanf("%d",&q);
n = strlen(str);
for(int k=;k<;k++){for(int i=;i<n;i++) pre[k][i] = suf[k][i] = -;}
for(int i=;i<n;i++)pre[str[i]-'a'][i] = i,suf[str[i]-'a'][i] = i;
for(int k=;k<;k++){
for(int i=;i<n;i++) if(pre[k][i]==-) pre[k][i] = pre[k][i-];
for(int i=n-;i>=;i--) if(suf[k][i]==-) suf[k][i] = suf[k][i+];
}
} void work(){
for(int i=;i<=q;i++){
int l,r; scanf("%d%d",&l,&r);
int flag = solve(l-,r-,);
if(flag) puts("Alice");
else puts("Bob");
}
} int main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
read();
init();
work();
return ;
}

最新文章

  1. linux系统维护时的一些小技巧,包括系统挂载新磁盘的方法!可收藏!
  2. C语言printf()输出格式大全
  3. IIS7.5中神秘的ApplicationPoolIdentity
  4. cpu中断
  5. 在Eclipse中自定义类似syso的快捷代码模板
  6. QT报错Error processing
  7. iOS textFiled 在storyBoard中的使用
  8. 当插入数据失败时,防止mysql自增长字段的自增长的方法
  9. caffe的db_lmdb.hpp文件
  10. C语言中strcpy(char *strDest, const char *strScr)字符串复制库函数的理解与分析
  11. bat定时执行,清除PHP缓存
  12. 11、四大组件之二-Service高级(二)Native Service
  13. 在Mac下如何开Wifi
  14. spring 自定义schema
  15. UIPickView之自定义生日键盘和城市键盘
  16. 【 D3.js 进阶系列 — 1.1 】 其它表格文件的读取
  17. OS X background process
  18. 题解 P4753 【River Jumping】
  19. Windows10系统无法更新
  20. SQL Server循环

热门文章

  1. MRO C3算法 super的运用
  2. poj 1486 纸张与数字匹配(二分图+割边处理)
  3. git更新提交代码常用命令
  4. 有界算子p129
  5. 自己实现数据结构系列三---Stack
  6. 牛客OI周赛8-普及组
  7. 虚拟机Ubuntu图形界面进入命令行快捷键
  8. 【翻译】asp.net core中使用FluentValidation来进行模型验证
  9. js 判断一个字符在字符串中出现的次数
  10. python之路--小数据池,再谈编码,is和 == 的区别