「YLLOI-R1-T3」一路向北 的题解

lovelish · 2025-03-20 11:33:54 · 题解

因为数字 x 只能到第 x 个队列，所以若出现循环，则只会是 1 个队列在循环。

下面我们给出一个结论：

• 把 0 放到第 x 个队列，只要 x 的总数量小于 m 个，0 就一定不会出队。

证明：因为当一个 x 出现在 0 后时，在 0 出队前，这个 x 就不可能出队。然而想要 0 出队，至少需要有 m 个 x 入该队。证毕。

因此只要有任意一个 x 的总数量小于 m，就一定可以不再拿回 0。如果想要使所有 x 的总数量都大于等于 m，任意一个 x 的总数量都一定为 m。

下面我们再给出一个结论：

• 当一个 x 的总数量小于等于 m 个时，第 x 个队列一定不会循环。

证明：要想使第 x 个队列循环，首先需要把该队列用 x 填满，不然一定会到其他队列；并且手中还需要拿着 x，不然无法再进入该队列。因此至少需要 m+1 个 x 才可能使第 x 个队列循环。证毕。

当不会有任何队列可能循环时，0 就一定会被拿回手中。

因此，我们把所有情况分为了两种，一种为每个数字的总数量都为 m，该情况 0 一定会被拿回，除此之外 0 一定可以不再被拿回。