1 条题解

  • 1
    @ 2021-05-27 22:52:58

    C题题解:
    这个是结论题,Chomp游戏。
    证明方法一:反证法,设后手有策略\(S\)必胜,则先手取右上角的一块巧克力,并没有改变局面,并转变为了后手,则应用策略\(S\)必胜。

    证明方法二:先手取右上角的一块巧克力,设后手通过:第一步拿取矩形X 的方式必胜,则先手可以一开始就采取这种策略,拿取这块矩形而获得胜利。

    特别地,n=m=1先手必败

    Code:

    #include<iostream>
    using namespace std;
    int main()
    {
        int t;cin>>t;while(t--){
            int n,m;cin>>n>>m;
            if(n+m==2) cout<<"NO\n";else cout<<"YES\n";
        }
        return 0;
    }
    

    当然,这题出\(n,m\le 7\)是因为可以用Nim博弈做的,1秒大概能跑7*7的样子。不过,如果能写出Nim博弈的代码也就知道结论,可以采用上面的代码了。
    下方代码可供参考

    #include<bits/stdc++.h>
    using namespace std;
    
    int n = 7;
    int m = 7;
    int a[15][15];
    
    map<string,char> s;
    
    int count() // 数巧克力数量,判断是否游戏结束。 
    {
        int cnt = 0;
        for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cnt += a[i][j];
        return cnt; 
    }
    
    string get_str()//将局面状态压缩成string. 
    {
        string str;
        for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) str += (char)(a[i][j] + '0');
        return str;
    }
    
    bool Nim()
    {
        char c = s[get_str()];
        if(c == 'F') return false; //'F' 先手必败 
        if(c == 'W') return true; //'W' 先手必胜
        //以上是记忆化搜索,如果局面已经判断过,就不需要重复判断了。 
         
        if(count() == 1) // 进入终局 
        {
            s[get_str()] = 'F';
            return false;
        }
        
        for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) // 搜索策略 
        {
            if(i == n && j == 1) continue; //不能选有毒的巧克力 
            if(a[i][j] == 0) continue; // 如果这里没有巧克力,则这个策略是不合法的。 
            
            int pre_a[n+1][m+1];//存储状态,等待回溯 
            for(int k = 1; k <= n; k++) for(int l = 1; l <= m; l++) pre_a[k][l] = a[k][l]; 
            for(int k = 1; k <= i; k++) for(int l = j; l <= m; l++) a[k][l] = 0; //将巧克力吃掉 
            
            bool flag = Nim();
            
            for(int k = 1; k <= n; k++) for(int l = 1; l <= m; l++) a[k][l] = pre_a[k][l]; //还原局面 
            if(!flag) s[get_str()] = 'W'; //如果当前局面能走向先手必败局面,则当前局面是先手必胜局面。 
        }
        
        if(s[get_str()] == 'W') return true; 
        else return false;//如果当前局面没法走向先手必败局面,则当前局面先手必败。
    }
    
    int main()
    {
        cin>>n>>m;
        for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) a[i][j] = 1; //初始化 
        Nim(); //Nim博弈(dfs) 
        if(s[get_str()] == 'W') cout<<"YES\n";else cout<<"NO\n";
    }
    

    bonus:思考,如果一开始巧克力右上角缺了一块,答案会怎样变化?

  • 1

信息

ID
1253
难度
4
分类
博弈论 点击显示
标签
递交数
272
已通过
90
通过率
33%
被复制
4
上传者