首页 > 代码库 > Codeforces Round #417 (Div. 2) E. Sagheer and Apple Tree(树上Nim)

Codeforces Round #417 (Div. 2) E. Sagheer and Apple Tree(树上Nim)

2024-10-19 10:53:02   211人阅读

题目链接：Codeforces Round #417 (Div. 2) E. Sagheer and Apple Tree

题意：

给你一棵树，每个节点有a[i]个苹果，有两个人要在这个树上玩游戏。

两个人轮流操作，谁不能操作谁就输了。

这个树有一个特性：叶子到根的距离的奇偶性相同。

每次操作可以选一个节点i，和一个数x,x小于当前节点i的苹果数。

对于节点i，如果是叶子节点，就将这x个苹果吃掉。

如果是非叶子节点，就将这x个苹果移向节点i的任意儿子节点。

现在第二个操作的人要交换两个节点的苹果，使其能赢，

问有多少种交换方式，必须交换。

题解：

仔细分析一下，可以得到是否能赢只与节点深度的奇偶性与叶子节点相同的节点有关。

我们把这些节点放入一个集合S.

所以先将这些节点进行异或一下，得出一个val。如果val等于0，那么当前局势就能赢。

现在来考虑交换节点的苹果。

显然我们要将这个val变成0,所以对S中所有的数都进行枚举一下，然后找不在这个集合中，并且交换后能使val变成0的数。

如果val最开始就为0，那么还要加上S中可以互相交换的个数。和S外可以互相交换的个数。

复杂度O(n)。

技术分享 
 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=(a);i<=(b);++i)
 3 using namespace std;
 4 typedef long long ll;
 5 const int N=1e5+7;
 6 
 7 vector<int>g[N];
 8 int cnt[1<<24],cnt2[1<<24],n;
 9 int a[N],x,is,val,have[N],ed;
10 
11 void dfs(int x=1,int d=0,int fa=0)
12 {
13     if(g[x].size()==0){is=(d&1);}
14     for(auto &it:g[x])if(it!=fa)dfs(it,d+1,x);
15 }
16 
17 void dfs2(int x=1,int d=0,int fa=0)
18 {
19     if((d&1)==is)have[++ed]=a[x];
20     for(auto &it:g[x])if(it!=fa)dfs2(it,d+1,x);
21 }
22 
23 int main()
24 {
25     scanf("%d",&n);
26     F(i,1,n)scanf("%d",a+i),cnt[a[i]]++;
27     F(i,2,n)
28     {
29         scanf("%d",&x);
30         g[x].push_back(i);
31     }
32     dfs(),dfs2();
33     F(i,1,ed)val^=have[i],cnt2[have[i]]++;
34     ll ans=0;
35     F(i,1,ed)
36     {
37         int tmp=val^have[i];
38         ans+=cnt[tmp]-cnt2[tmp];
39     }
40     if(!val)
41     {
42         ans+=1ll*ed*(ed-1)/2;
43         ans+=1ll*(n-ed)*(n-ed-1)/2;
44     }
45     printf("%lld\n",ans);
46     return 0;
47 }
View Code

 

Codeforces Round #417 (Div. 2) E. Sagheer and Apple Tree(树上Nim)


联系
我们