BestCoder#90dingyeye loves stone

143 阅读 0 评论 95 点赞

我是靠谱客的博主漂亮百褶裙，这篇文章主要介绍BestCoder#90dingyeye loves stone，现在分享给大家，希望可以做个参考。

问题描述

复制代码

1
2
3
dingyeye喜欢和你玩石子游戏。
dingyeye有一棵 $n$ 个节点的有根树，节点编号为 $0$ 到 $n - 1$ ，根为 $0$ 号节点。游戏开始时，第 $i$ 个节点上有 $a [i]$ 个石子。两位玩家轮流操作，每次操作玩家可以选择一个节点，并将该节点上的一些石子（个数不能为 $0$ ）移动到它的父亲节点上去。如果轮到某位玩家时，该玩家没有任何合法的操作可以执行，则判负。
你在游戏中执先手，你想知道当前局面你能否必胜。

输入描述

复制代码

1
2
3
4
5
6
本题有多组数据，第一行为一个非负整数 $T$ ，表示数据组数。
对于每组数据，第一行一个整数 $n$ ，表示节点数目。
接下来一行为 $n - 1$ 个整数 $f a [1] \dots f a [n - 1]$ ，分别描述了除根节点外每个点的父亲。方便起见，保证$0leq fa[i]< i$。
接下来一行为 $n$ 个非负整数 $a [0] \dots a [n - 1]$ ，分别描述了每个点初始的石子数。保证 $0 \leq a [i] < 134217728$ 。
 $1 \leq T \leq 100$ ， $1 \leq n \leq 100000$ 。
保证 $n > 100$ 的测试点数目不超过 $7$ 个。

输出描述

复制代码

1
对于每组数据，输出一行，若先手必胜则输出"win"，否则输出"lose"（不含引号）。

输入样例

复制代码

输出样例

复制代码

1
2
win
lose

分析：其实就是个n堆的尼姆博弈。因为是一棵树，所以是分层次的，而且都是连起来的。那么先手当然希望是把1,3,5,7....奇数层的都清空，这样就可以使后手无法满足题目中"并将该节点上的一些石子移动到它的父亲节点上去"，因为层与层都割断了嘛。至于为什么是奇数层，是因为把根节点当做第0层，因为根节点不能移动。

体会：思路还是很清晰的，就是不知道如何处理把奇数层给选出来，当时还用了vector把属于同一根节点的儿子都加进来，其实还是在层次的处理上还是不正确的....

AC代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
#define N 200050
using namespace std;
int n,fa[N],dep[N];
void solve() {
scanf("%d",&n);
for (int i=1;i<=n-1;i++) {
scanf("%d",&fa[i]);
dep[i] = dep[ fa[i] ] + 1;
}
int ans = 0;
for (int i=0;i<=n-1;i++) {
int v; scanf("%d",&v);
if (dep[i]&1) ans ^= v;
}
if (!ans) puts("lose"); else puts("win");
}
int main()
{
int T = 0; scanf("%d",&T);
while (T--) solve();
return 0;
}