我是靠谱客的博主 漂亮百褶裙,最近开发中收集的这篇文章主要介绍BestCoder#90dingyeye loves stone,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

问题描述
dingyeye喜欢和你玩石子游戏。
dingyeye有一棵nn个节点的有根树,节点编号为00n-1n1,根为00号节点。游戏开始时,第ii个节点上有a[i]a[i]个石子。两位玩家轮流操作,每次操作玩家可以选择一个节点,并将该节点上的一些石子(个数不能为00)移动到它的父亲节点上去。如果轮到某位玩家时,该玩家没有任何合法的操作可以执行,则判负。
你在游戏中执先手,你想知道当前局面你能否必胜。
输入描述
本题有多组数据,第一行为一个非负整数TT,表示数据组数。
对于每组数据,第一行一个整数nn,表示节点数目。
接下来一行为n-1n1个整数fa[1]cdots fa[n-1]fa[1]fa[n1],分别描述了除根节点外每个点的父亲。方便起见,保证$0leq fa[i]< i$。
接下来一行为nn个非负整数a[0]cdots a[n-1]a[0]a[n1],分别描述了每个点初始的石子数。保证0leq a[i]<1342177280a[i]<1342177281leq Tleq 1001T1001leq nleq 1000001n100000。
保证n>100n>100的测试点数目不超过77个。
输出描述
对于每组数据,输出一行,若先手必胜则输出"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所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(52)

评论列表共有 0 条评论

立即
投稿
返回
顶部