细分等价类的过程
题面
现在有一个长度为 n 的十进制数字，对于它的每一位的每个数字，都可以通过给定的方式转化为一个字母，从时刻 1 开始，每秒都会给这个数字加上 1，当这个数长度改变后会停止。
现在 Bob 知道了数字的转化方式，知道了每一个时刻的字符串，知道了什么时候停止，求 Bob 在最早在哪个时刻确定原本的十进制数字是什么。
题目解析
这道题的核心是找到一个“最早的时刻 t”，在这个时刻 t 我们能唯一地确定最初的 n 位数字 S 是什么。
“唯一确定”的含义
在时刻 t，我们拥有了从时刻 0 到时刻 t 所有观测到的字符串序列。如果根据这个观测序列，我们可以排除掉所有其他可能的初始数字 S'（S' != S 且 S' 也是 n 位数），那么我们就说在时刻 t 确定了 S。
反向思考：何时无法确定？
在时刻 t 仍然无法确定初始数字 S，意味着存在至少一个不同于 S 的 n 位数 S'，它在 0 到 t 这 t+1 个时刻里，所产生的字符串序列与 S 产生的一模一样。我们称 S' 是一个“混淆项”。
解题目标
为了在时刻 t 唯一确定 S，我们必须能够排除所有的混淆项 S'。要排除某个混淆项 S'，我们必须找到一个时刻 k (k <= t)，在此时刻 S 和 S' 经过 k 次加法后生成的字符串是不同的。
我们设 k(S, S') 为区分 S 和 S' 所需的最小时间。那么，为了排除所有可能的 S'，我们必须等到所有这些 k(S, S') 时刻都过去。因此，最终的答案就是所有这些区分时间中的最大值。
答案 = max { k(S, S') } (对于所有 n 位数 S' != S)
这个 k(S, S') 来自于 S+k 和 S'+k 首次出现不同的观测结果。不同可能源于：
- 某一位的字符不同：在时刻
k，S+k和S'+k在某一位p上的数字分别是d1和d2。如果这一位的字符映射map_p[d1]不等于map_p[d2]，它们就被区分开。 - 停止时刻不同：数字加到
10^n时（即变成n+1位数）会停止。S的观测会持续到10^n - S - 1时刻。S'的观测会持续到10^n - S' - 1时刻。如果它们的字符串始终相同，那么min(10^n - S, 10^n - S')就是它们的区分时刻（因为一个停止了，另一个还在继续）。
我们的任务就是找到那个最“顽固”的混淆项 S'，它能与 S 保持最久的无法区分的状态。
代码逻辑解释
这段代码非常精妙，它采用了一种从高位到低位的动态规划思想来解决这个问题。在遍历数字的每一位时，它同时维护和更新两个核心信息：
ll ans：到当前位为止，已经发现的“最大混淆时间”。这是我们最终的答案。ll dif：要使当前处理过的前缀s[0...i]对应的字符串发生变化，所需要的最小步数（时间）。
让我们跟随循环来理解代码的行为（假设当前处理第 i 位，i 从 0 到 n-1）：
// 在循环开始前，ans = 0, dif = 1for (int i = 0; i < n; ++i) {cin >> t; // 读入第 i 位的 0-9 字符映射int c = s[i] - '0'; // 获取第 i 位的真实数字 c// 1. 更新 ans (寻找最大混淆时间)// 考虑所有与真实数字 s 的前 i-1 位相同，但第 i 位不同的混淆项 s'// (即 s'[i] = j, 其中 j != c)for (int j = 0; j < 10; ++j) {if (j == c) continue;// a. 计算一个混淆时间的上限 `up`// 这个上限是“进位”发生的时间。// `dif` 是使前缀 s[0...i-1] 发生改变的最小时间。// `dif * 10` 意味着让第 i-1 位进位需要的时间。// `dif * 10 - max(c, j)` 是考虑当前位 c 和 j 之后，// 传递到第 i-1 位的进位发生所需的最小时间。// 简单理解：这是在不考虑当前位字符映射差异的情况下，// 仅靠进位机制能区分它们的最晚时间。ll up = dif * 10 - max(c, j);// b. 检查是否存在更早的区分时间// 模拟时间流逝 k = 0, 1, 2...，检查当前位的字符是否会提前变得不同for (int k = 0; k < min(up, 10ll); ++k) {if (t[(c + k) % 10] != t[(j + k) % 10]) {up = k; // 找到了更早的区分时间 kbreak;}}// c. 更新全局最大混淆时间// `up` 是区分 s[i]=c 和 s'[i]=j 所需的时间。// 我们要取所有 j 的情况中最大的那个，作为当前位的最大混淆时间，// 并与之前位的 ans 比较，取最大值。ans = max(ans, up);}// 2. 更新 dif (为下一轮迭代做准备)// a. 计算真实前缀 s[0...i] 因进位而改变需要的时间// 上一轮的 dif 是 10^i - val(s[0...i-1])// 本轮更新后就是 10^(i+1) - val(s[0...i])dif = dif * 10 - c;// b. 计算真实前缀 s[0...i] 因第 i 位字符映射改变而需要的时间ll change_time = 1e18; // 设一个大数for (int j = 1; j < 10; ++j) {if (t[(c + j) % 10] != t[c]) {change_time = j; // 找到了最小的步数 j 使得字符不同break;}}// c. 更新 dif 为两者中的较小值// 因为 dif 的定义是“发生改变所需的最小时间”，// 改变可能来自进位，也可能来自当前位字符变化，取最先发生的那一个。dif = min(dif, change_time);
}
cout << ans << "\n";
代码核心逻辑总结：
-
ans的迭代：ans在循环中不断与新发现的、可能更大的“混淆时间”up进行比较并取最大值。up代表了在当前位i，一个最“顽固”的混淆数字（s'[i] = j）能与真实数字s保持一致多久。这个up要么是靠数字本身递增导致字符映射不同（k循环），要么是等到低位进位彻底改变了数字（dif * 10 - max(c, j)）。ans最终会เก็บ下所有位数、所有可能混淆情况下的最大值。 -
dif的迭代：dif是一个辅助变量，但至关重要。它告诉下一轮循环（处理i+1位时），当前已经处理完的前缀s[0...i]本身至少要过多久才会“露出马脚”（即发生字符串上的变化）。这个信息被用来计算下一位up的一个初始上限。dif的值由两种可能决定：要么是整个前缀数字加到溢出（产生进位），要么是前缀的最后一位数字s[i]变化导致了字符不同，取这两种情况中发生得更早的那个。
特殊情况（样例2）
s = 42, 两个映射表都是 aaaaaaaaaa。
这意味着无论数字怎么变，每一位产生的字符永远是 a。我们永远无法通过字符串内容来区分任何两个数字。
此时，唯一的区分方式是停止时刻。
S = 42会在100 - 42 = 58秒后停止（即在t=57是最后一次观测）。- 一个混淆项
S' = 99会在100 - 99 = 1秒后停止。t=0时，两者都输出aa。t=1时，S=43输出aa，而S'已经停止，不再输出。所以在t=1时刻可以区分它们。 - 我们要找最晚的区分时间。最晚被区分的
S'是与S最接近的数，比如S'=41。S=42在t=57结束，S'=41在t=58结束。在t=58时刻，S没有输出，而S'仍在运行，两者被区分。 - 所以，对于任意
S' != S，区分时刻是min(100-S, 100-S')。为了让这个时刻最晚，S'需要离100最远，即S'最小，为00。 max_{S' != S} { min(100-S, 100-S') }=max_{S' != S} { min(58, 100-S') }。当100-S' >= 58(即S'<=42) 时，min取58。当S' > 42时，min取100-S'，小于58。所以最大值是58。
代码中的 ans 会正确地计算出这个值。因为字符映射相同，k 循环永远不会 break，up 将始终等于 dif * 10 - max(c, j)。最终 ans 会收敛到 10^n - S - 1 或类似的值，这需要详细的数学推导，但其逻辑上是正确的。在样例2中，最终答案是 58。等等，100-42=58，这是运行58次加法，所以时刻是从0到57，总时长是58。当t=58时，S=100，停止。而S'=41，在t=58时，41+58=99，仍在运行。因此区分时刻是 58。这个例子说明了当字符串无法区分时，停止时刻成为关键。代码通过 dif 的传递正确地处理了这种情况。
希望这个解释能帮助你理解这道题的精髓和代码的巧妙之处。