9516.支配游戏

Time Limit: 3s Memory Limit: 512MB

两个玩家在一张无向图上进行博弈,任意两个节点之间最多一条边相连。这张图由若干个互不相交的连通块组成,每个连通块要么是一条简单路径,要么是一个简单环

在游戏中,两个玩家轮流行动。在每一轮中,当前玩家必须选择一个顶点 $ u $,该顶点需能支配至少一个未被支配的顶点,注意,该顶点并不要求是未被支配的。一个顶点 $ u $ 能够支配它自己以及所有与它相邻的顶点。

当某个顶点被选中后,它以及所有被其支配的顶点都会被标记为已支配

若某位玩家在其回合无法进行操作(即没有可以支配未被支配顶点的顶点可选),则该玩家输掉游戏。

请判断,在双方都采取最优策略的前提下,先手玩家是否必胜

Input Format(From the terminal/stdin)

第一行包含一个整数 $ t $($1 \le t \leq 10^4$),表示测试数据的组数。

每组测试数据的第一行包含一个整数 $ n $($1 \leq n \leq 100$),表示该图中连通块的数量。

接下来的 $ n $ 行,每行描述一个连通块,包含两个整数:

  • $ \text{num} $($2 \le \text{num} \le 10^{18}$):该连通块中的顶点数量;
  • $ \text{is_path} \in {0, 1} $:表示该连通块的类型。

若 $\text{is_path} = 1$,该连通块是一条由 $\text{num}$ 个点组成的简单路径。

若 $\text{is_path} = 0$,该连通块是一个由 $\text{num}$ 个点组成的简单环,其中 $ \text{num} \geq 3 $。

Output Format(To the terminal/stdout)

对于每组测试数据,若先手玩家有必胜策略,则输出一行 $\texttt{Yes}$,否则输出一行 $\texttt{No}$。

Sample Input

Copy
4
3
3 0
4 0
3 0
3
4 1
4 1
3 0
3
2 1
3 0
4 0
3
3 0
3 1
3 0 \n
 \n
 · \n
 · \n
 · \n
 \n
 · \n
 · \n
 · \n
 \n
 · \n
 · \n
 · \n
 \n
 · \n
 · \n
 · \n

Sample Output

Copy
No
Yes
No
Yes  \n
   \n
  \n
   \n
Source: 2025“钉耙编程”中国大学生算法设计暑期联赛(5), HDU, 8032

Submit

请先 登录

© 2025 FAQs