枚举每一个连续的K的第一个位置,如果是先手胜利,那么前[1 , i-1 ]和[ i+k , n ]区间要么全是0,要么全是1
如果能够平局,那么肯定是[1,i-1],以及[ i+k , n]中有两种情况
有一个区间全为0,并且另外有个区间内部最左边的1和最右边的1距离是大于K
有一个区间全为1,并且另外有一个区间内部最左边的0和最右边的0的距离是大于K
或者两个区间均有1或者均有0
如何后手胜利,那么肯定没有平局出现,也就意味着
有一个区间全为0,并且另外有个区间内部最左边的1和最右边的1距离是大于K
有一个区间全为1,并且另外有一个区间内部最左边的0和最右边的0的距离是大于K
由于不带修改,我们可以很简单维护i位置
左边第一次出现1的位置,左边第一次出现0的位置
右边第一次出现1的位置,右边第一次出现0的位置
然后o(n)判断即可,这也算是比较优秀的做法了吧。。。
#include<iostream>
#include<string.h>
#include<algorithm>
#include<stdio.h>
using namespace std;
const int maxx = 2e5+;
int l1[maxx];
int l0[maxx];
int r1[maxx];
int r0[maxx];
char s[maxx];
int main(){
int n,k;
while(~scanf("%d%d",&n,&k)){
scanf("%s",s+);
for (int i=;i<=n;i++){
if (s[i]==''){
l1[i]=i;
l0[i]=l0[i-];
}else {
l0[i]=i;
l1[i]=l1[i-];
}
}
r0[n+]=n+;
r1[n+]=n+;
for (int i=n;i>=;i--){
if (s[i]==''){
r1[i]=i;
r0[i]=r0[i+];
}else {
r0[i]=i;
r1[i]=r1[i+];
}
}
int flag=;
for (int i=;i<=n-k+;i++){
int ll=;
int lr=i-;
int rl=i+k;
int rr=n;
if(l1[i-]== && r1[i+k]==n+){
flag=min(flag,);
}
if(l0[i-]== && r0[i+k]==n+){
flag=min(flag,);
}
if (l1[i-]== && l0[n]-r0[i+k]+<=k){
flag=min(flag,);
}
if (l0[i-]== && l1[n]-r1[i+k]+<=k){
flag=min(flag,);
}
if (r0[n+k]== && l1[i-]-r1[]+<=k){
flag=min(flag,);
}
if (r1[n+k]== && l0[i-]-r0[]+<=k){
flag=min(flag,);
}
if (r1[n+k]== && l0[i-]-r0[]+>k){
flag=min(flag,);
}
if (r0[n+k]== && l1[i-]-r1[]+>k){
flag=min(flag,);
}
if (l1[i-]== && l0[n]-r0[i+k]+>k){
flag=min(flag,);
}
if (l0[i-]== && l1[n]-r1[i+k]+>k){
flag=min(flag,);
}
if (l1[i-]!= && r1[i+k]!=n+){
flag=min(flag,);
}
if (l0[i-]!= && r0[i+k]!=n+){
flag=min(flag,);
}
}
if (flag==){
printf("tokitsukaze\n");
}else if (flag==){
printf("once again\n");
}else {
printf("quailty\n");
}
}
return ;
}