1 条题解
-
1Takagi-san (njnu19200437) LV 10 MOD @ 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