CF1137D

· · 题解

一道经典面试题到 Codeforces 上咋就成 *2400 了（

Floyd 判圈法，又叫双指针，快慢指针等 .

大概就是给一个和题目一样的 \rho 形图，然后在起点处放两个指针 p_1,p_2 .

每次 p_1 走一步，p_2 走两步，则 p_1,p_2 总会相遇 .

这非常平凡，就是环形跑道相遇问题呗 .

设链长为 t，环长为 c，则走的步数 step 满足

t+step\equiv 2\cdot step+3t\pmod c

即 step+2t\equiv 0\pmod c，从而 step\equiv c-2t\pmod c

根据定义再走 c-2t 步就到环和链的交点了，也就是再走 step 步就好了 .

也就引出那个经典的方法找到环和链的交点：

  1. 三个指针 p_1,p_2,p_3 都初始化在链的头部 .
  2. 每次 p_1 走 1 步，p_2 走 2 步，直到它们相遇 .
  3. 相遇后，p_1,p_2,p_3 均每次走一步，相遇点即为环链交点 .

然而我们有 10 个点，不就随便做了 .

我们在第 2 步之后将所有点一起动，要不然会超次数 .

这样步数显然是不超过 3(t+c) 的，留作练习 .

CF Submission: 161472728 .