codeforces 1191E Tokitsukaze and Duel

叁歲伎倆 2021-09-29 13:54 274阅读 0赞

## Tokitsukaze and Duel ##

找出第一个和最后一个1，第一个和最后一个0  
sjf胜利的条件很简单，zero2 - zero1 < k || one2- one1 < k  
难点在qls的回合判断  
现在设计一个数组a，元素为zero2 ， zero1 ， one2， one1，并排序

*  已知已经进行到qls的回合，qls不可能输，顶多once again（这里隐含了sjf的胜利条件不满足）

qls胜利，条件为a2-a0 <= k and a3-a1 <= k

*  已经判断了第一回合，则a1和a2不可能同是0或1，即a0和a3为0和1（因为zero2 - zero1 >= k && one2- one1 >= k)
 *  无论sjf选择哪一段，必包括a1和a2
 *  假设sjf把那一段变成1，qls可以把边缘的0到中间一段变成1，同理假设sjf把那一段变成0，qls可以把边缘的1到中间一段变成0
 *  重点在于无论如何，当满足条件时，sjf无论如何操作都覆盖到了中间的0和1

假设不满足这个条件，则sjf必定可以选择一段不覆盖中间的0和1，qls只能选择once again  
具体要理解清楚可能需要自己举一些例子，或者严格证明一下

#include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define all(x) (x).begin(),(x).end()
    #define fi first
    #define se second
    #define SZ(x) ((int)(x).size())
    typedef vector<int> VI;
    typedef long long ll;
    typedef pair<int,int> PII;
    const ll mod=1000000007;
    ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
    ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
    
    int n,k;
    string str;
    int one1,one2;
    int zero1,zero2;
    
    int a[10];
    int main(int argc, char const *argv[])
    { 
    	cin >> n >> k;
    	cin >> str;
    
    	rep(i,0,n)
    	{ 
    		if(str[i] == '0')
    		{ 
    			if(zero1 == 0)
    			{ 
    				zero1 = i + 1;
    			}
    				zero2 = i + 1;
    		}
    		if(str[i] == '1')
    		{ 
    			if(one1 == 0)
    			{ 
    				one1 = i + 1;
    			}
    				one2 = i + 1;
    		}
    	}
    	if(zero2 - zero1 < k || one2 - one1 < k)
    	{ 
    		cout << "tokitsukaze" << endl;
    		return 0;
    	}
    	a[0] = zero1;
    	a[1] = zero2;
    	a[2] = one1;
    	a[3] = one2;
    	sort(a,a+4);
    	if(a[3] - a[1] <= k && a[2] - a[0] <= k)
    	{ 
    		cout << "quailty" << endl;
    		return 0;
    	}
    	cout << "once again" << endl;
    	return 0;
    }