[SG函数] 2021牛客寒假集训营6 H.寒冬信使2

传送门：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的值即可。

#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;
}