自动搬运

查看原文

来自洛谷，原作者为

	dyc2022 「知らない世界を見せてよ」

搬运于2025-08-24 22:25:41，当前版本为作者最后更新于2025-02-06 13:55:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

确定性做法。（感谢

容易发现，当我们知道 bot 的起点，我们是很好构造一张图使得拥有 $100 \%$ 的胜率的。具体操作就是把 bot 的图贺过来，然后把点权全部变成能克 bot 的手势，然后再把边权换成 bot 出的手势。这样就稳赢了。

但问题在于我们不知道起点。

考虑在知道起点的情况只保留获胜的边。那么我们在构造出这张图后，如果在和 bot 大战的过程中发现，我们根本停不下来，那么就说明我们的这张图所认定的 bot 起点就是 bot 真正的起点，那么我们就赢了。

考虑到这一特性，我们充分发扬人类智慧，对于每一个 bot 可能的起点构造一个只保留获胜边的图，平局或失败的边连向下一层的该点。这样为什么是对的？因为总有一层能做到完胜 bot，而我们走到完胜 bot 的层后就会在这一层无限游走。而又因为切换一层等同于一次失败，我们最多在切换 $n-1$ 次后可以到达完胜 bot 的层，因此在 $10^9$ 次游戏中我们最多只会输 $99$ 次。胜率远高于 $99 \%$。

代码好写，就不放了。