CF1605D题解

· · 题解

题目大意：

E 和 S 在玩博弈游戏， E 先手 S 后手。

给一个 n 个节点的树，节点的值包含 [1,n] 中的每一个值。

E 先随便选择一个点，占领它（点 u ）， S 只能选择与这个点相邻的，没有被占领的点（点 v ）且这两个点满足 u⊕v≤\min(u,v)

现在把树给 E 了， E 想要重新排列节点的值（树的形状不变，只是调换结点的值）来达到这个目的： 最大化第一轮能够选择的点的数量，在选了这个点之后，E 必赢。 赢：对手无路可走，你就算赢 ## 思路： E 和 S 交替进行，怎么感觉有点像二分图呢，我就是用的二分图来做的，但这个题仅仅用二分图还不够，还需要发现异或操作的一个性质，从而进行构造。 为了让对手无路可走，要么是~~真正意义上的~~无路可走（你把叶节点占领了），要么是对手无法满足 $ u⊕v≤ \min(u,v)

后者就是解题的关键

先不必管第一种，这个题是构造，只要你能构造出来最大情况，有些东西是不必考虑的。

现在让我们看看神奇的异或操作

当两个数（u,v）的二进制最高位数相等时，它俩的异或结果一定比 \min(u,v) 小

因为最高位在异或之后变成了 0

相反，如果两个数的二进制最高位不相等，异或结果永远比最小的那个大，因为最高位的二进制位被保留。

我们就可以把 [1,n] 的整数按照最高位进行划分了。

（1） ; （2,3） ; （4,5,6,7） ; （8,9,10,11,12,13,14,15） ; ……

不同的划分块之间不通（不满足约束条件）

树我们用bfs把它变成二分图，任意一边的节点数量小于等于 n/2 ，我们可以用划分块来填充二分图的两边，而划分块的大小刚好是2的整数次方，岂不美哉。

举个例子：假设 n=7 ,二分图左边大小是 3 ，右边大小是 4 ，我们先填充 3 这边

3 的二进制是 11 ，所以我们选择第一个划分块和第二个划分块（划分块的大小和二进制权重是相对应的，所以划分块里面的元素刚刚好被用完）来填充二分图的左边，剩下的自然就填充到右边。

此时你会发现，你无论选择哪个点，对手死路一条。

上代码：

#include<bits/stdc++.h>
using namespace std;
int t,n;
vector<int>edge[200005];
bool vis[200005];
int ans[200005];
vector<int>Left,Right;//二部图
void bfs(int i,int depth)//奇数在左边，偶数在右边
{
    vis[i]=1;
    if(depth&1) Left.push_back(i);
    else Right.push_back(i);
    for(int j=0; j<(int)edge[i].size(); j++)
    {
        if(!vis[ edge[i][j] ])
        {
            bfs(edge[i][j],depth+1);
        }
    }
}
int main()
{
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i=1; i<=n; i++) edge[i].clear();
        Left.clear();
        Right.clear();
        memset(vis,0,n+2);
        for(int i=1; i<n; i++)
        {
            int u,v;
            cin >> u >> v;
            edge[u].push_back(v);
            edge[v].push_back(u);
        }
        bfs(1,1);
        memset(vis,0,n+2);
        int s=Left.size();
        int S=Right.size();
        int base=1;
        if(s<S)
        {
            while(s)
            {
                if(s&1)
                {
                    for(int i= (1 << (base-1)); i<= (1 << base) -1; i++)
                    {
                        ans[Left.back()]=i;
                        Left.pop_back();
                        vis[i]=1;
                    }
                }
                base ++;
                s >>= 1;
            }
            for(int i=1; i<=n; i++)
            {
                if(!vis[i])
                {
                    ans[Right.back()]=i;
                    Right.pop_back();
                }
            }
        }
        else
        {
            while(S)
            {
                if(S&1)
                {
                    for(int i= (1 << (base-1)); i<= (1 << base) -1; i++)
                    {
                        ans[Right.back()]=i;
                        Right.pop_back();
                        vis[i]=1;
                    }
                }
                base ++;
                S >>= 1;
            }
            for(int i=1; i<=n; i++)
            {
                if(!vis[i])
                {
                    ans[Left.back()]=i;
                    Left.pop_back();
                }
            }
        }
        for(int i=1; i<=n; i++) cout << ans[i] << " " ;
        cout << endl;
    }
    return 0;
}