首页 > 试题广场 >

黑黑白白

[编程题]黑黑白白

艮为山，动静得宜，适可而止；兑为泽，刚内柔外，上下相和。
艮卦：兼山，艮；君子以思不出其位。财帛常打心头走，可惜眼前难到手，不如意时且忍耐，逢着闲事休开口。
兑卦：丽泽，兑；君子以朋友讲习。这个卦象真可取，觉着做事不费力，休要错过这机关，事事觉得随心意。

有一个棋子放在一颗有根树的根上。你和算卦先生轮流把这个棋子向所在点的其中一个儿子移动（只能移动到儿子）。不能再移动就算失败（即棋子所在节点没有儿子）。

算卦先生来问你，如果你先手，你是否有必胜策略？

第一行一个数 ，表示有  组数据。
接下去每组数据的第一行有两个数  ，表示树有  个节点，其中  为根节点编号（从  开始编号）。 
接下去  行每行两个数字  ，表示点  和  之间有一条边。

每组数据输出一行， 表示先手有必胜策略， 表示没有。

示例1

输入

Dui
Gen

算法知识视频讲解

白色L号谢谢

发表于 2020-07-07 15:01:39

比较明显的SG函数。设d[x]表示先手轮到x点时的取胜情况。当子状态有必败状态时，该状态为必胜状态。当子状态全部为必胜状态，该状态为必败状态。 #include <bits/stdc++.h> #include <unordered_map> using namespace 展开全文

小琢卷不动

发表于 2021-11-23 14:47:47

感觉和上一题考察点有一些重复，都是最基础的博弈论。解决这题我们需要知道下面的两点：如果我走了一步，对方处于“必败”境地，那么我就处于“必胜”境地。如果我的所有下一步状态都是“必败”态，那么我就会输，只要有一个“必胜”的我走那一条路就可以。所以既然它就是个树形结构，直接遍历这棵树，把所有孩展开全文

博弈论

难度：

0条回答 0收藏 13浏览

查看代码

黑黑白白

扫一扫，把题目装进口袋