[sg function] 2021 Niuke winter vacation training camp 6 h. winter messenger 2

Portal ：H- Winter messenger 2_2022 Niuke winter vacation algorithm basic training camp 6 (nowcoder.com)

Ideas

First, we review the theory of fair combination game P Point and N spot ：

• All endpoints are fail points (P-Position)
• From any winning point (N-Position) operation , There is at least one way to enter the fail point (P-Position)
• Whatever you do , You can only enter the winning point from the losing point (N-Position)

Then let's start to analyze this topic ：

1. Adopt binary enumeration , use $0$ representative $b$,$1$ representative $w$, In this way, all combinations within a certain length can be enumerated .
2. For each state , Whether enumeration can enter the mandatory state ( The initial failure state is $0$), If it can, it will be marked as winning .
3. For both operations ：
   • The first grid is white , When you can directly reverse the first lattice ： If you flip the first lattice, it will fail , Then mark the current status as winning
   • For the rest of the grid , If it can enter any previous failure state after completing the first type of flip , Then mark the current status as a must fail

Then according to the nature of the above two operations , We can write $SG$ Table function ：

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

Then for each input , It only needs to be processed into the form of binary string , Judge $SG$ The value of the can .

Accepted Code

#include <bits/stdc++.h>
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;
}