AGC014 D Black and White Tree（博弈论）

题目大意：

给出一个n个结点的树，A可以把树上的结点涂成白色，B可以把树上的结点涂成黑色，A和B交题涂色，全部涂完以后，B进行这样的操作

把树上所有与黑色结点相邻的点全部涂成白色

如果这样树上还有白色，那么A赢，否则B赢

(n <= 10^5)

题解：

我是这么考虑的，A需要一直保持主动才有机会赢

保持主动的意思就是说，A如果把一个点涂成白色，那么B必须把其附近的一个点涂成黑色，否则B就会输

如何保持主动呢？其实很简单，首先把树变成以1为根节点的树

然后如果A把叶子结点的父结点涂成白色，那么B一定要把叶节点涂成黑色。

同时可以证明这样做一定会更优，因为白色结点在黑色结点的上方。

所以A保持主动总是更优的。

如何判断输赢呢？

一个简单的条件是如果一个结点涂成白色以后，它有2个叶子结点，那么就是A赢

因为B无法同时涂2个叶子结点

根据这个，就有这样的做法

就是先把所有叶子结点的父结点都涂成白色，然后这个过程中如果有一个结点被涂了两遍，那么就是A赢

如果没有，就把这些染色的结点都删去，这样又会多很多叶子结点，继续向上这么做即可

注意对根节点的处理（或许不处理也可以通过）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#define pb push_back
using namespace std;
const int maxn = 1e5 + 100;
queue<int> Q;
vector<int> G[maxn];
int f[maxn], col[maxn], in[maxn];
void dfs(int x, int fa){
    f[x] = fa;
    for(auto to : G[x]){
        if(to == fa) continue;
        dfs(to, x);
    }
}
int n, x, y;
int main()
{
    cin>>n;
    for(int i = 0; i < n-1; i++){
        cin>>x>>y;
        in[x]++; in[y]++;
        G[x].pb(y); G[y].pb(x);
    }
    dfs(1, 1);
    for(int i = 1; i <= n; i++){
        if(in[i] == 1) Q.push(i);
    }
    int label = 0;
    f[1] = 0;
    while(!Q.empty()){
        int x = Q.front(); Q.pop();
        if(col[x]) continue;
        if(col[f[x]]) label = 1;
        else{
            col[f[x]] = 1;
            in[f[f[x]]]--;
            if(in[f[f[x]]] == 0) label = 1;
            if(in[f[f[x]]] == 1 && f[f[x]] != 1) Q.push(f[f[x]]);
        }
    }
    cout<<(label ? "First" : "Second")<<endl;
    return 0;
}

CF768E Game of Stones(状压DP+博弈论)

题目大意：

给出n堆石子，A和B来取，一次可以取一堆中的若干个，本身是nim游戏的框架，不过多加了这样的一个限制：

如果其中一堆之前已经被取过k个了，那么就不能再取k个

题解：

还是把每一堆石子看成一个子游戏，最后异或起来即可

然后就是求SG函数（dp）

利用状压，把每一个数（1到60）有没有取的状态压到一个60位的2进制里

如果每个状态都计算，显然会超时

但是实际上并没有特别多的状态可以取，实际状态数大概只有60这个数的有限制的整数拆分方案个数

这样就完成状态的压缩

dp[i][s]表示已经取了s这个状态代表的数，现在还有i个石子的SG值

转移就是按照SG函数的定义，往能够达到的局面转移，过程可以利用记忆化搜索

为了节省空间，这里利用map来实现整个过程

#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
map<pair<int, long long>, int> dp;
map<pair<int, long long>, bool> visit;
int dfs(int x, long long S){
    S = S&((1LL<<x)-1);
    if(x == 0) return 0;
    if(visit[{x, S}]) return dp[{x, S}];
    vector<bool> f(63, 0);
    for(int i = x; i >= 1; i--){
        long long Si = 1<<(i-1);
        if(S&Si) continue;
        f[dfs(x-i, S|Si)] = 1;
    }
    for(int i = 0; i < 63; i++) if(!f[i]){
        visit[{x, S}] = true;
        return dp[{x, S}] = i;
    }
}

int main()
{
    int n, x;
    cin>>n;
    for(int i = 60; i >= 0; i--) dfs(i, 0);
    int SG = 0;
    for(int i = 0; i < n; i++) scanf("%d", &x), SG ^= dp[{x, 0}];
    if(SG) cout<<"NO"<<endl;
    else cout<<"YES"<<endl;

}