1 solutions

  • 0
    @ 2024-10-16 15:38:55

    这道题是一个博弈游戏,题目大致意思就是给一个字符串,然后两人轮流操作,每次操作可以选择一个连续且相同的字符串,字符串长度不能超过k,然后将此段字符串翻转。如果谁操作后字符串全为0或1时,那么他将获胜。 这个博弈有三种结果:1、Alice获胜;2、Bob获胜;3、平局。

    先来判断Alice获胜的情况,Alice是先手,当他首先执行一次操作后,如果他没有获胜的话,那么Bob只需在重复一次Alice的操作,那么Alice将无法获胜。这时我们就得出了Alice的获胜情况,即:如果Alice能一次操作直接获胜,那么他必胜,否则将不会获胜。

    再来判断Bob获胜的情况,Bob是后手,当Alice第一次操作后没有获胜,到Bob开始。此时Bob就会遇到和Alice同样的处境,即:如果当前不能直接获胜,那么将无法获胜。因为第三步Alice重复Bob的操作,那么Bob将无法获胜。

    那么最后平局的情况就显而易见了,当前两步无法确定出胜负的话,那么必定是平局。

    #include<iostream>
    #include<algorithm>
    #include<cstdlib>
    #include<cstring>
    #include<cctype>
    // #include<cmath>
    #include<vector>
    #include<stack>
    #include<queue>
    #include<map>
    #include<set>
    
    using namespace std;
    
    #define IOS ios::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    #define ll long long
    #define ull unsigned long long 
    #define endl '\n'
    
    typedef pair<char, int> pir;
    const int mod = 0x7f7f7f7f;
    const int N = 100010;
    
    int x0, x1, y0, y1;
    bool flag;
    
    int main(void){
        IOS
    	
    	int n, k; cin >> n >> k;
    	string s; cin >> s;
    	
    	 if(s[0] == '0') {
    	 	flag = false; x0 ++ ;
    	 } else {
    	 	flag = true; x1 ++ ;
    	 }
    	 
    	 for(int i = 1; i < s.size(); i ++ ) {		//计算连续相同子字符串的长度及个数
    	 	if(s[i] == '0' && !flag) {
    	 		x0 ++ ;
    	 		if(x0 > k) {
    	 			x0 -= k; y0 ++ ;
    			 }
    		 } else if(s[i] == '0' && flag) {
    		 	y1 ++ ;
    		 	x1 = 0;
    		 	x0 ++ ;
    		 	flag = false;
    		 } else if(s[i] == '1' && flag) {
    		 	x1 ++ ;
    		 	if(x1 > k) {						//若长度大于k,它就相当于2个及以上的字符串,不能当作一个,因为无法一次翻转
    		 		x1 -= k; y1 ++ ;
    			 }
    		 } else if(s[i] == '1' && !flag) {
    		 	flag = true;
    		 	y0 ++ ;
    		 	x0 = 0;
    		 	x1 ++ ;
    		 }
    	 }
    	 if(x0) y0 ++ ;
    	 if(x1) y1 ++ ;
    	 
    	 if(y0 == 0 || y1 == 0) {
    	 	if(n > k) cout << "Bob" << endl;
    	 	else cout << "Alice" << endl;
    	 } else if(y0 == 1 || y1 == 1) {
    	 	cout << "Alice" << endl;
    	 } else if(s == "0101" || s == "1010" || s == "1100" || s == "0110" || s == "0011" || s == "1001") {
    	 	cout << "Bob" << endl;
    	 } else {
    	 	cout << ":(" << endl;
    	 }
    	
        return 0;
    }
    
    
    
    
    • 1

    Information

    ID
    6980
    Time
    1000ms
    Memory
    256MiB
    Difficulty
    9
    Tags
    (None)
    # Submissions
    34
    Accepted
    2
    Uploaded By