传送门：H-寒冬信使2_2022牛客寒假算法基础集训营6 (nowcoder.com)
思路
首先回顾公平组合博弈的P点和N点：
所有终结点是必败点(P-Position)从任何必胜点(N-Position)操作，至少存在一种方法进入必败点(P-Position)无论如何操作，从必败点只能进入必胜点(N-Position)
那么我们开始分析本题目：
采用二进制枚举的方式，用 0 0 0代表 b b b， 1 1 1代表 w w w，这样可以枚举一定长度内所有的组合。对于每一个状态，枚举能否进入必败态(初始必败态为 0 0 0)，如果能则标记为必胜态。对于两种操作而言：
第一个格子为白色，可以直接反转第一个格子时：如果翻转第一个格子后是必败态，那么标记当前状态为必胜态对于其余格子而言，如果它完成第一类翻转后能够进入之前的任何一个必败态，那么标记当前状态为必败态
那么根据以上两个操作的性质，我们可以写出 S G SG SG打表函数：
int sg[N];inline void getsg(){ for(int i = 1; i < (1 << 11); i++){ if(i & 1 && !sg[i - 1]){ sg[i] = 1; continue; } for(int j = 1; j < 10; j++){ if(i >> j & 1){ for(int k = 0; k < j; k++) if(!sg[i ^ (1 << j) ^ (1 << k)]) sg[i] = 1; } } }}
然后对于每个输入，只需要处理成二进制串的形式，判断 S G SG SG的值即可。
Accepted Code
#include using namespace std;const int N = 1 << 11 + 10;int sg[N];string s;void print_bin(int n){int a = n % 2;n = n >> 1;if(n) print_bin(n);std::cout << a;}inline void getsg(){ for(int i = 1; i < (1 << 11); i++){ if(i & 1 && !sg[i - 1]){ sg[i] = 1; continue; } for(int j = 1; j < 10; j++){ if(i >> j & 1){ for(int k = 0; k < j; k++) if(!sg[i ^ (1 << j) ^ (1 << k)]) sg[i] = 1; } } }}inline void solve(){ getsg(); int n = 0; cin >> n >> s; int lastpos = 0; for(int i = 0; i < n; i++){ if(s[i] == 'w') lastpos = i; } int pos = 0; for(int i = lastpos; i >= 0; i--){ if(s[i] == 'w') pos = pos << 1 | 1; else pos = pos << 1; } //print_bin(pos); cout << (sg[pos] ? "Yes" : "No") << endl;}signed main(){ int t = 0; cin >> t; while(t--) solve(); return 0;}