POJ 2425(HDOJ 1524)【基础】
题目大意:
有 N 个点,这些点之间有一些单向边,每一次从一个点到另一个点之间的移动
只能通过单向边进行。图上没有环。给出若干个起始位置,两人轮流移动,无
法移动者输。问先手有无必胜策略。
输入:
有若干组测试数据。
每一组测试数据第一行有一个整数 N(1<=N<=1000),接下来有 N 行,每一行
第一个整数 K 表示第 i 个点有 K 条出边,接下来有 K 个整数,每一个整数表示
第 i 个点可以走到哪些点。然后有若干行查询,每一行查询占一行,第一个整
数 K 表示有多少个起始位置,接下来有 K 个整数表示起始位置是哪些点。所有
的点从 0 开始编号。
输出:
每一条查询输出一行,如果先手必胜则输出“WIN”,否则输出“LOSE”。测试
数据组间不需要分行。
题解:
还是基本的 SG 函数,其实和 POJ 2960 类似,只不过不需要减到 0,而是出边
为 0 的点就是终结的必败态。
POJ 2599【基础】
题目大意:
有一棵无向树,有 N 个节点(1<=N<=1000),从 1 开始编号。一开始在点 K,
两个人轮流移动,不能移动到已经走过的点上,谁无法移动谁算输。问先手是
否必胜,如果是的话第一步要移动到哪个点上。
输入:
第一行有两个整数 N 和 K。接下来有 N 行,每一行有两个整数,表示一条无向
边。
评论0