https://codeforc.es/contest/1191/problem/E
参考自：http://www.mamicode.com/info-detail-2726030.html
和官方题解。
首先这种组合游戏，必定存在一种不败策略。一种很直观的理解就是，假如没有办法一开始就胜利，那么就优先考虑和局的。
假如有连续k个一样的，那么先手可以进行一次无效翻转变成后手，所以这种情况先手必然至少和局。这样的话一次翻转之后就必然有连续k个一样的，后手也必定有了至少和局的机会，他也进行一次无效翻转。所以先手要赢的话，只能够在第一步直接赢，否则后手拥有了不败策略之后先手就不可能会有机会赢。
这种情况就判断除了某个k连续区间之外其他的是否全0或者全1，可以用前缀和O(n)预处理然后O(n)判断。
否则，一开始没有连续k个一样的，先手不可以进行一次无效的翻转。这种时候后手能赢的必要条件是在先手翻转了之后，后手第二步可以直接赢，否则后手虽然拥有了不败策略，但第三步开始先手也有了不败策略，会导致和局。那什么情况下可以获胜呢？是先手无论选择翻转哪一段，都会把情况转变为上面的情况。所以有一种优化是，后手能赢的必要条件是2*k>=n。因为先手一开始可以选择翻0或者翻1，后手必定要在下一次把全部翻成0或者全部翻成1才能获胜，否则先手一开始会捣乱，把一段连续k个的区间翻转到比如数字c，后手最佳策略必定是贪心在这个区间的两侧第一个非c开始再翻k个相同数字，即使这样也会有至少1个不一样，那么后手就失去了第二步赢的机会了。
所以就要判断无论翻转哪k个到c，剩下的非c必定集中存在于k区间的左侧或者右侧，且他们连续于k个位置，这样才能导致后手必胜。怎么判断呢？枚举先手翻转位置的起点，然后判断“集中于同侧？”，然后判断“连续于k个位置？”。“集中于同侧”这个好办，就选最左侧和最右侧的0和1记录下来O(1)验证是不是被包含在k区间里面。“连续于k个位置”就要找到k区间的向左或向右的最近的第一个非c位置x，然后看最左或者最右的非c（假如存在）是不是在[x-k+1,x]位置或者[x,x+k-1]内，这样是用尺取O(n)判断。
写起来好多bug，很多地方复制粘贴之后没改过了，可能是老了吧。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
char s[100005];
int sum[2][100005];
inline int range_sum(int i, int l, int r) {
return sum[i][r] - sum[i][l - 1];
}
bool judge_f() {
for(int cp = 1; cp + k - 1 <= n; cp++) {
if(range_sum(0, 1, cp - 1) + range_sum(0, cp + k, n) + k == n) {
return true;
} else if(range_sum(1, 1, cp - 1) + range_sum(1, cp + k, n) + k == n) {
return true;
}
}
return false;
}
int lm0, lm1, rm0, rm1;
int ln0, ln1, rn0, rn1;
void init() {
//先手不能赢，那肯定至少有一个0和一个1
for(int i = 1;; i++) {
if(s[i] == '0') {
lm0 = i;
break;
}
}
for(int i = 1;; i++) {
if(s[i] == '1') {
lm1 = i;
break;
}
}
for(int i = n;; i--) {
if(s[i] == '0') {
rm0 = i;
break;
}
}
for(int i = n;; i--) {
if(s[i] == '1') {
rm1 = i;
break;
}
}
}
bool judge_s() {
init();
//判断先手翻转成0
rn1 = k + 1;
ln1 = -1;//一开始左边就是没有最近的1
while(s[rn1] != '1')
rn1++;//肯定有至少一个不能覆盖的1，否则judge_f
for(int cp = 1; cp + k - 1 <= n; cp++) {
if(lm1 < cp && rm1 > cp + k - 1) {
return false;//两侧都有1
} else {
if(lm1 < cp) {
//左侧有1，而右侧没有
//找左侧最近的1的下标，用尺取可以，每次cp移动的时候更新最近的1
//左边不可能是-1啊
if(lm1 < ln1 - k + 1)
return false;
} else {
//右侧有1，因为两边都没有的话在judge_f判断过了
//找右侧最近的1的下标，用尺取也可以，每次cp移动的时候更新最近的1
//右边也不可能是-1啊
if(rm1 > rn1 + k - 1)
return false;
}
}
if(s[cp] == '1') {
ln1 = cp;
}
if(rn1 == cp + k) {
//rnl会被新区间覆盖掉
rn1++;
if(rn1 > n)
rn1 = -1;
}
while(rn1 != -1 && s[rn1] != '1') {
rn1++;
if(rn1 > n) {
rn1 = -1;
break;
//找不到右侧最近的1
}
}
//查找下一个最近的，没有的话就是-1
}
//
//
//判断先手翻转成1
rn0 = k + 1;
ln0 = -1;
while(s[rn0] != '0') {
rn0++;
//肯定有至少一个不能覆盖的0，否则judge_f
}
//一开始左边就是没有最近的0
for(int cp = 1; cp + k - 1 <= n; cp++) {
if(lm0 < cp && rm0 > cp + k - 1) {
//两侧都有0
return false;
} else {
if(lm0 < cp) {
//左侧有0，而右侧没有
//找左侧最近的0的下标，用尺取可以，每次cp移动的时候更新最近的0
//左边不可能是-1啊
if(lm0 < ln0 - k + 1)
return false;
} else {
//右侧有0，因为两边都没有的话在judge_f判断过了
//找右侧最近的0的下标，用尺取也可以，每次cp移动的时候更新最近的0
//右边也不可能是-1啊
if(rm0 > rn0 + k - 1)
return false;
}
}
if(s[cp] == '0') {
ln0 = cp;
}
if(rn0 == cp + k) {
//rn0会被新区间覆盖掉
rn0++;
if(rn0 > n)
rn0 = -1;
}
while(rn0 != -1 && s[rn0] != '0') {
rn0++;
if(rn0 > n) {
rn0 = -1;
break;
//找不到右侧最近的0
}
}
//查找下一个最近的，没有的话就是-1
}
return true;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
//freopen("Yinku.out", "w", stdout);
#endif // Yinku
while(~scanf("%d%d%s", &n, &k, s + 1)) {
sum[0][0] = 0, sum[1][0] = 0;
for(int i = 1; i <= n; i++) {
sum[0][i] = sum[0][i - 1] + (s[i] == '0');
sum[1][i] = sum[1][i - 1] + (s[i] == '1');
}
if(judge_f()) {
puts("tokitsukaze");
} else if(judge_s()) {
puts("quailty");
} else {
puts("once again");
}
}
}
有一些多余的操作，去掉之后就是：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
char s[100005];
int sum[100005];
inline int range_sum(int l, int r) {
return sum[r] - sum[l - 1];
}
bool judge_f() {
for(int cp = 1; cp + k - 1 <= n; cp++) {
int tmp = range_sum(1, cp - 1) + range_sum(cp + k, n);
if(tmp == 0 || tmp + k == n)
return true;
}
return false;
}
int lm0, lm1, rm0, rm1;
int ln0, ln1, rn0, rn1;
void init() {
//先手不能赢，那肯定至少有一个0和一个1
lm0 = -1, lm1 = -1, rm0 = 1, rm1 = 1;
for(int i = 1;i<=n; i++) {
if(s[i] == '0') {
lm0 = (lm0 == -1) ? i : lm0;
rm0 = i;
} else {
lm1 = (lm1 == -1) ? i : lm1;
rm1 = i;
}
}
}
bool judge_s() {
init();
//判断先手翻转成0
rn1 = k + 1;
while(s[rn1] != '1')
rn1++;//肯定有至少一个不能覆盖的1，否则judge_f
for(int cp = 1; cp + k - 1 <= n; cp++) {
if(lm1 < cp && rm1 > cp + k - 1)
return false;//两侧都有1
else {
if(lm1 < cp && lm1 < ln1 - k + 1)
return false;
else if(rm1 > rn1 + k - 1)
return false;
}
if(s[cp] == '1')
ln1 = cp;
if(rn1 == cp + k)
rn1++;
while(rn1 <= rm1 && s[rn1] != '1')
rn1++;
}
//判断先手翻转成1
rn0 = k + 1;
while(s[rn0] != '0')
rn0++;
for(int cp = 1; cp + k - 1 <= n; cp++) {
if(lm0 < cp && rm0 > cp + k - 1)
return false;//两侧都有0
else {
if(lm0 < cp && lm0 < ln0 - k + 1)
return false;
else if(rm0 > rn0 + k - 1)
return false;
}
if(s[cp] == '0')
ln0 = cp;
if(rn0 == cp + k)
rn0++;
while(rn0 <= rm0 && s[rn0] != '0')
rn0++;
}
return true;
}
int main() {
#ifdef Yinku
freopen("Yinku.in", "r", stdin);
//freopen("Yinku.out", "w", stdout);
#endif // Yinku
while(~scanf("%d%d%s", &n, &k, s + 1)) {
sum[0] = 0;
for(int i = 1; i <= n; i++) {
sum[i] = sum[i - 1] + s[i]-'0';
}
if(judge_f()) {
puts("tokitsukaze");
} else if(judge_s()) {
puts("quailty");
} else {
puts("once again");
}
}
}