codeforces 812 E. Sagheer and Apple Tree（树+尼姆博弈）

题目链接：http://codeforces.com/contest/812/problem/E

题意：有一颗苹果树，这个苹果树所有叶子节点的深度要不全是奇数，要不全是偶数，并且包括根在内的所有节点上都有若干个苹果，现有两个，每个人可以吃掉某个叶子节点上的部分苹果（不能不吃），或者将某个非叶子结点上的部分苹果移向它的孩子（当然也不能不移），吃掉树上最后一个苹果的人获胜。后手可以在游戏开始之前交换任意两个不同的节点的苹果，输出交换后能使得后手胜利的交换总数。

题解：这题挺友善的所有叶子结点的深度奇偶性是一样的，首先考虑到叶子结点是奇数步的，显然不论先手怎么操作，后手总是能吃掉这些苹果比较显然不解释了。然后就是偶数步时，先手操作一次偶数步时显然偶数步就会变成奇数步，也就是说移动的这部分苹果肯定是先手吃到的。于是就转换到了裸的尼姆博弈，什么是尼姆博弈不知道的可以去百度一下。于是这题只要将所有偶数步的节点上的苹果异或一下如果结果是0那么后手胜利否则先手胜利。

然后就是怎么处理交换了，如果ans=0（ans表示异或结果）那么只要在偶数步与奇数步中交换相同的数即可，还有就是偶数步中与奇数步中分别自行交换。

如果ans！=0那么只要遍历一遍偶数步的点找奇数点中苹果数为ans^val[i]的个数即可。

#include <iostream>

#include <string>

#include <cstdio>

#include <map>

#include <vector>

using namespace std;

typedef long long ll;

const int M = 1e5 + 10;

map<int , int>num;

vector<int>vc[M];

int ans , val[M] , deep[M] , maxdeep;

void dfs(int u , int pre , int d) {

    int len = vc[u].size();

    deep[u] = d;

    maxdeep = max(maxdeep , d);

    for(int i = 0 ; i < len ; i++) {

        int v = vc[u][i];

        if(v == pre) continue;

        dfs(v , u , d + 1);

    }

}

int main() {

    int n;

    scanf("%d" , &n);

    num.clear();

    for(int i = 0 ; i <= n ; i++) vc[i].clear();

    for(int i = 1 ; i <= n ; i++) {

        int gg;

        scanf("%d" , &gg);

        val[i] = gg;

        num[gg]++;

    }

    for(int i = 1 ; i < n ; i++) {

        int gg;

        scanf("%d" , &gg);

        vc[gg].push_back(i + 1);

        vc[i + 1].push_back(gg);

    }

    maxdeep = 0;

    dfs(1 , -1 , 1);

    for(int i = 1 ; i <= n ; i++) {

        if((maxdeep % 2) == (deep[i] % 2)) {

            num[val[i]]-- , ans ^= val[i];

        }

    }//这里处理奇数偶数步用了取巧的方法。就是如果奇偶性和最大深度的奇偶性相同那么就必定是偶数点

    ll count = 0;

    if(ans == 0) {

        ll sum = 0;

        for(int i = 1 ; i <= n ; i++) {

            if((maxdeep % 2) == (deep[i] % 2)) {

                count += num[val[i]];

            }

            else sum++;

        }

        count += (sum * (sum - 1) / 2 + (n - sum) * (n - sum - 1) / 2);

    }

    else {

        for(int i = 1 ; i <= n ; i++) {

            if((maxdeep % 2) == (deep[i] % 2)) {

                count += num[(ans ^ val[i])];

            }

        }

    }

    printf("%lld\n" , count);

    return 0;

}

巴特西

codeforces 812 E. Sagheer and Apple Tree（树+尼姆博弈）

最新文章

热门文章