概述
问题描述
dingyeye喜欢和你玩石子游戏。 dingyeye有一棵n个节点的有根树,节点编号为0到n−1,根为0号节点。游戏开始时,第i个节点上有a[i]个石子。两位玩家轮流操作,每次操作玩家可以选择一个节点,并将该节点上的一些石子(个数不能为0)移动到它的父亲节点上去。如果轮到某位玩家时,该玩家没有任何合法的操作可以执行,则判负。 你在游戏中执先手,你想知道当前局面你能否必胜。
输入描述
本题有多组数据,第一行为一个非负整数T,表示数据组数。 对于每组数据,第一行一个整数n,表示节点数目。 接下来一行为n−1个整数fa[1]⋯fa[n−1],分别描述了除根节点外每个点的父亲。方便起见,保证$0leq fa[i]< i$。 接下来一行为n个非负整数a[0]⋯a[n−1],分别描述了每个点初始的石子数。保证0≤a[i]<134217728。 1≤T≤100,1≤n≤100000。 保证n>100的测试点数目不超过7个。
输出描述
对于每组数据,输出一行,若先手必胜则输出"win",否则输出"lose"(不含引号)。
输入样例
2 2 0 1000 1 4 0 1 0 2 3 3 3
输出样例
win lose
分析:其实就是个n堆的尼姆博弈。因为是一棵树,所以是分层次的,而且都是连起来的。那么先手当然希望是把1,3,5,7....奇数层的都清空,这样就可以使后手无法满足题目中"并将该节点上的一些石子移动到它的父亲节点上去",因为层与层都割断了嘛。至于为什么是奇数层,是因为把根节点当做第0层,因为根节点不能移动。
体会:思路还是很清晰的,就是不知道如何处理把奇数层给选出来,当时还用了vector把属于同一根节点的儿子都加进来,其实还是在层次的处理上还是不正确的....
AC代码:
#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;
}
最后
以上就是漂亮百褶裙为你收集整理的BestCoder#90dingyeye loves stone的全部内容,希望文章能够帮你解决BestCoder#90dingyeye loves stone所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复