3 月 8 日 Codeforces Round #545
比赛链接:https://codeforces.com/contest/1138

E – Museums Tour

思路:

首先考虑将每一个 museum 按天数分为 $d$ 个点,然后对应的向相邻的连边。接着就很自然的想到用 tarjan 缩点,然后考虑如何统计答案。有一个性质就是如果一个 museum 对应不同天的点之间有边,那么这些点一定是在同一个强联通分量里面的,因此你缩点后直接找一个包含 museum 数最多的链就是对的。

代码链接

F – Cooperative Game

思路:
如果你知道 pollard-rho 中的 floyd 判环的话,这题的思路就应该不难想到。如果你直接模拟这个过程:让一个人每次走一步另一个人每次走两步,就能够在 $2*(t+c)$ 次交互内让两个人在环上相遇。那么问题就在于如何不知道终点位置的情况下让所有人走到终点。这里有个非常巧妙的性质就是在相遇点走 $t$ 步后一定能到达终点,如果我们设两个人分别走了 $t+x$,$2t+2x$ 步后相遇,那么 $t+x$ 一定是环长的倍数,如果再走 $t$ 步就意味着在环上总共走了 $t+x$ 步(一开始在链上走了 $t$ 步),那么就一定走到了终点。因此只要让一些人留在起点,两个人在环上相遇后所有一起走若干步,如果大家全部相遇,就意味着已经到终点了。

代码链接

发表评论

邮箱地址不会被公开。 必填项已用*标注