[数据结构与算法]寒冬信使2

Link
博弈论，sg函数
没看懂题解，，暴力打了个表，一开始还把操作2给漏了。
看题解的意思是每次操作都会让 $x$ 减少，做了几道题目感觉就是如果有多种操作，那就找这几种操作的共同点，来写转移方程。

代码

int sg[1050];
int mex(vector<int> v) // v可以是vector、set等容器
{
    unordered_set<int> S;
    for (auto e : v)
        S.insert(e);
    for (int i = 0;; ++i)
        if (S.find(i) == S.end())
            return i;
}
int cal(int x) {
    if(sg[x] != -1) return sg[x];
    int t = x;
    vector<int> v;
    if(t & 1) {
        v.pb(cal(t - 1));
    }
    for(int i = 0; i < 10; i++) {
        if(!(t >> i)) break;
        if((t >> i) & 1) {
            int p = x ^ (1<<i);
            for(int j = i - 1; j >= 0; j--) {
                int q = p ^ (1<<j);
                v.pb(cal(q));
            }
        }
    }
    int a = mex(v);
    return sg[x] = a;
}
void solve() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int a = 0;
    for(int i = 0; i < n; i++) {
        if(s[i] == 'w')
            a = a + (1<<i);
    }
    if(sg[a]) cout << "Yes\n";
    else cout << "No\n";
}
signed main() {
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(sg, -1, sizeof(sg));
    sg[0] = 0;
    for(int i = 1; i <= 1030; i++)
        cal(i);
    int T; cin >> T; while(T--)
        solve();
	return 0;
}