博弈论
博弈论
Tokitsukaze and Duel CodeForces - 1190C
简单分析： 每个人取区间长度必相等
先手要么一步赢，要么走某一步取得最大优势
后手要么一步赢，要么搬回先手优势，陷入僵局
所以直接考虑一步、两步赢、无限。三种可能。
详细题解： 先手必赢条件：
1.不用翻转就可以赢2.翻转长度 k >= n ，那么只要翻转一次就可以赢
3.k < n ,但是只要一次翻转就可以赢后手赢的条件：那就是先手第一次无论怎么翻转都不能赢，但是到了后手无论何种情况下都能赢
1.k！=1。因为如果先手赢不了，那他就相当于不动序列，留给后手，后手也赢不了
2.2*k>=n，因为后手一出手必须赢，不然先手就可以抵消后手对于序列的影响而导致平局。
3.2*k>=n的时候，那必定会存在一个区间k内的字符一定是相同的，考虑到先手（聪明绝顶，肯定不希望后手赢），那么我们只要让先手无论如何都会输就好了
首尾肯定是不会选的，毕竟先手聪明绝顶。
那么先手肯定会选择中间的k个连续字符，那么我们就枚举中间k个连续字符区间的左右的剩余区间（例如左边的是a区间，右边的是b区间。）我们判的是否a区间为都为0或者1，以及b。 因为先手决定聪明，所以他会尽量不让后手赢，所以就要枚举区间，判定没有一个情况下a和b不是合法的。并且区间a和区间b也必须是不同的
注意：判断后手赢得条件时，如果暴力判断（n2）会超时，因此用到里“窗体移动”的方法（这个是我在网上看到的，应该是这个叫法），区间k不断向右移动，同时保证左区间a和右区间b也满足条件
要满足条件的话，去加入区间的元素，只要和它的上一位元素（或是下一位元素）比较就可以知道时候满足条件，这样的复杂度就降到了O（n），还有就是注意边界情况的处理。就是左区间或者右区间有且仅有1一个元素的时候，这个时候区间中没有东西可以进行比较，要满足的是区间a和区间b也必须是不同的。#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
#define ll long long
char s[N];
int n,k,cnt1,cnt0;
bool check()
{
if(k>=n||cnt0==0||cnt1==0)return 1;//不用改就赢或者动一下就赢
int l0=0,r0=0,l1=0,r1=0;
for(int i=1;i<=n;i++)
{
if(!l0&&s[i]=='0')l0=i;
if(!l1&&s[i]=='1')l1=i;
if(l0&&l1)break;
}
for(int i=n;i>=1;i--)
{
if(!r0&&s[i]=='0')r0=i;
if(!r1&&s[i]=='1')r1=i;
if(r0&&r1)break;
}
if(k>=min(r0-l0+1,r1-l1+1))return 1;//动连续的一段区间，保证剩下的一段是相同的
return 0;
}
bool chekc()
{
if(k==1||2*k<n)return 0;//先手赢不了，那他就相当于不动序列，留给后手，后手也赢不了
int len=n-k;
for(int i=3;i<len;i++)//[i,i+k-1]是被先手改过的
if(s[i-2]!=s[i-1]||s[i+k]!=s[i+k+1])return 0;//左右区间是否相同？只要任意两个连续的不同即可
if(s[1]==s[k+2]||s[n]==s[n-k-1])return 0;//循环里没写的情况
if(s[1]==s[n])return 0;//上面没退出去，说明左右区间各自相同，这里要保证两者不同
return 1;
}
int main()
{
scanf("%d%d%s",&n,&k,s+1);
for(int i=1;i<=n;i++)if(s[i]=='0')cnt0++;else cnt1++;
if(check()){printf("tokitsukaze");return 0;}
if(chekc()){printf("quailty");return 0;}
printf("once again");
}
GH游戏 公平删边游戏
超现实数/不平等博弈问题
只能放一些链接玩儿
surreal number应对不平等博弈
上一篇的原文
Surreal Number模板 + hdu 6597 题解
surreal number（不平衡博弈的一类解决方法）
集训队论文