题解 P1061 【Jam的计数法】

Actinoi · 2019-07-21 15:56:12 · 题解

为获取最佳阅读效果，欢迎访问https://www.actinoi.com/2019/07/21/noip2006%20%E6%99%AE%E5%8F%8A%E7%BB%84/

读完题目之后，我们可以想，什么时候这个数字最小呢？无疑，如果最后一位数字能够加 1 的话，那么我们新得到的 Jam 数字绝对是最小的。但是，如果最后一位加 1 大于 t 怎么办呢？这个时候怎样构建数字最小呢？我们便可以向前一位寻找，如果倒数第二位一位加 1 不大于 t - 1 的话，我们便更新倒数第二位的数字。由于 Jam 数字是左到右是严格递增的，所以我们便向后更新，为了确保得到的数字尽可能地小，当前位数上的数字也就是上一位上的数字加 1 ，这样，我们便可以令 Jam 数字最小了。

整理一下上面的思路，也就是从最后一位数字开始枚举，如果它加 1 不大于 t 的话，我们便更新这个数字。否则，便向前一位寻找有没有数字可以更新，如果有的话，便更新这个数字。为了确保数字值最小且满足左到右是严格递增的要求，我们将它后面的数字依次更新，使得这个数字后面的所有数字都是前面数字的值加 1 。如果找到了第一位且无法更新的话，那么便停止计算。

还不太明白的同学可以看一下代码：

#include <iostream>
using namespace std;
int main() {
    int s, t, w; //s为所使用的最小的字母的序号，t为所使用的最大的字母的序号，w为数字的位数
    string Jam;
    cin >> s >> t >> w >> Jam;
    bool r = false; //判断是否更新了Jam数字
    int k = 0;
    for (int q = 1; q <= 5; q++) { //输出5个Jam数字
        for (int i = w - 1; i >= 0; i--) { //从最后一位开始，向前查找能不能替换
            if (Jam[i] + 1 <= 'a' - 1 + t - k) { //如果加一不超过最大值，则更新
                Jam[i] = Jam[i] + 1;
                for (int j = i + 1; j <= w; j++)
                    Jam[j] = Jam[j - 1] + 1;
                r = true;
                break;
            }
            k++;
        }
        if (r == true) //判断是否更新了Jam数字
            cout << Jam << endl; //输出当前的Jam数字
        else
            return 0;
        k = 0;
        r = false;
    }
    return 0;
}