题解

每个数能走的路线是确定的，我们只能决定在哪一步停下。因此可以先研究一个数会怎么变，再判断哪些数最终能走到一起。

操作只用到了个位。若当前个位是 $d$，下一次个位就是 $2d\bmod 10$。把十种个位的变化写出来，会分成两类。

个位为 $0$ 的数不再变化；个位为 $5$ 的数加一次 $5$，也会停下来。比如 $15$ 能变成 $20$，但它不能继续变成 $30$。这一类要比较的是最后停下来的具体数值。

其他个位最终都会进入

奇数个位先变成偶数，再进入这个循环；整个过程不会出现 $0$ 或 $5$。所以它们不可能与前面那一类相遇，可以分开统计。

把循环中的数放到同一个阶段比较

两个数的个位不同，直接比较余数不方便。我们把它们都操作到个位为 $2$，分别得到 $b_i$。

从个位为 $2$ 出发，走完一圈会增加

也就是说，以后再遇到个位为 $2$，数值只能是

于是，两个这样的数能相遇，当且仅当它们模 $20$ 相同。

余数相同时，让较小的那个继续走若干圈，就能追到较大的那个。反过来，如果两个数能在某一步相遇，那么相遇后继续操作到个位为 $2$，也会得到同一个值；这个值分别与两人的 $b_i$ 同余模 $20$，所以两人的余数必须相同。

这里还要确认整组数能不能同时相等。对同一余数下的所有 $b_i$，取最大的那个，其他数都能走到它，所以统计一组的大小就够了。

实现时用两种标记区分它们。

• 会停下来的数，标记记为最终值 $b_i$，并注明它属于停止这一类。
• 持续循环的数，标记记为 $b_i\bmod20$，并注明它属于循环这一类。

相同标记的数放在一起，最大的组就是答案。代码用偶数 $2b_i$ 表示第一类，用奇数 $2(b_i\bmod20)+1$ 表示第二类，避免两类碰巧使用同一个标记。

每个数至多操作四次就能完成归一化，之后排序计数。时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。中间值和标记用 long long。

部分分可以怎么拿

小值域的 20 分可以直接模拟。记初始最大值为 $M$，对每个数枚举它能到达的不超过 $M+40$ 的值，用桶统计有多少个原数能到达这里；遇到个位 $0$ 就停止，不能重复计数。

这个上界可以由前面的循环分析说明。非停止的数第一次到达个位 $2$，至多比初值增加 $25$；同一组都能到达这批归一化结果的最大值。停止的数最多增加 $5$。因此有用的公共目标一定能在 $M+40$ 内找到。模拟耗时 $O(n(M+40))$、空间 $O(M+40)$，能处理 $n\le2000,M\le10^4$。

个位仅含 $0,5$ 的 18 分，只用统计停止位置；没有 $0,5$ 的 18 分，只用处理循环。两种性质分别把停止值和周期这两件事单独拿出来。结合小规模模拟可以保证前三档的 56 分；把两类正确合并，就得到了完整做法。

参考代码

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<long long> keys;
    keys.reserve(n);
    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        long long key;
        if (x % 10 == 0) key = x * 2;
        else if (x % 10 == 5) key = (x + 5) * 2;
        else {
            while (x % 10 != 2) x += x % 10;
            key = x % 20 * 2 + 1;
        }
        keys.push_back(key);
    }
    sort(keys.begin(), keys.end());
    int answer = 0, run = 0;
    for (int i = 0; i < n; ++i) {
        run = (i > 0 && keys[i] == keys[i - 1]) ? run + 1 : 1;
        answer = max(answer, run);
    }
    cout << answer << '\n';
}