CSES 2220 Counting Numbers 題解

CSES 2220

題序

給定一個區間 $[a, b](a, b \le 10^{18})$，求區間內有幾個合法的整數，合法的定義為：任兩個相鄰的數字皆不相同，如 $123$ 是一個合法的整數，但 $555$ 不是。

解法

狀態定義

令 $dp_{i ,j}$ 為區間 $[j \times 10^i, (j+1) \times 10^i)$ 內合法的整數個數。

轉移式

可發現，對於所有合法的數字滿足長度為 $i$ 且前端數字為 $j$，那麼這些數字就可以透過在前端加上除了 $j$ 以外的所有正整數來得到一個新的合法整數，因此轉移式便是：$dp_{i, j} = \displaystyle\sum_{k=0, k \neq j}^{9}{dp_{i-1, k}}$

合法個數求法

拿 $2345$ 為例，對於 $\le 2345$ 的所有數字可分為三種：

1. $< 2000$
2. $2000 \sim 2344$
3. $2345$

對於第一種情況答案應該很好算，那就是：$dp_{4, 1} + \sum_{i=0}^{9}{dp_{3, i}} + \sum_{i=0}^{9}{dp_{2, i}} + \sum_{i=0}^{9}{dp_{1, i}}$，而第三種也很簡單，直接判斷就可以了。

至於第二種的部分，我們可以再分成幾種情況：

1. $2000 \sim 2299$：前一位數字貼合上限
2. $2300 \sim 2339$：前兩位數字貼合上限
3. $2340 \sim 2344$：前三位數字貼合上限

假設 $s_i$ 為從前面數來的第 $i$ 位數字（1-based），那麼我們就可以枚舉是前 $i$ 位數字貼合上限，那麼合法的整數數量便是：$\displaystyle\sum_{i=1}^{\log_{10}-1}{\sum_{j=0}^{s_{i+1}}{dp_{i+1, j}}}$

需要額外注意的是像 $555$ 這種數字，如果貼合前兩位的話就已經是不合法的了，這時就需要停止計算

Code

int n, m;
int dp[20][10], sum[20];

void pre() {
    for (int i = 0; i < 10; i++)
        dp[1][i] = 1;
    sum[1] = 10;
    for (int i = 2; i < 20; i++) {
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k < 10; k++) if (j != k)
                dp[i][j] += dp[i - 1][k];
            if (j)
                sum[i] += dp[i][j];
        }
    }
}

int cal(string s) {
    int res = 0;

    if (stoll(s) < 0)
        return 0;
    if (stoll(s) <= 1)
        return 1;

    for (int i = 1; i < s.size(); i++)
        res += sum[s.size() - i];
    for (int j = 1; j < s[0] - '0'; j++)
        res += dp[s.size()][j];

    for (int i = 1; i < s.size(); i++) {
            
        for (int j = 0; j < s[i] - '0'; j++) if (j != s[i - 1] - '0')
            res += dp[s.size() - i][j];
        if (s[i] == s[i - 1])
            break;
    }
    bool legal = true;
    for (int j = 1; j < s.size(); j++) {
        if (s[j] == s[j - 1])
            legal = false;
    }
    res += legal;
    return res;
}


void sol() {
    pre();
    cin >> n >> m;
    cout << cal(to_string(m)) - cal(to_string(n - 1)) << endl;
}