階梯數字 (APCS 2018-02 高級) 的題解
前置知識
這題是「按位數計數」的入門題（常被歸在數位 DP），下面的講解直接把這些當成已知，沒讀過的先讀；同一個主題兩邊都有的，對照著讀會更快上手：
- 動態規劃的基本概念：NTUCPC Guide〈基本概念〉與〈狀態與轉移〉——「先定義好一個表格每格的意思，再寫出格子之間的關係」；吳邦一《AP325》第 6 章的 P-6-19 正是本題，用的也是下面這張「開頭數字 × 位數」的表（教材 PDF 第 201～205 頁；Python 版第 6 章（III））。
- 把數字拆成一位一位：語法書 10.9（讀成字串最省事）。
簡潔題意
十進位數字由左到右不下降的正整數叫階梯數字（\(9\)、\(112\)、\(777\) 都是；\(0\) 不算、不能有前導零）。求不超過 \(N\) 的階梯數字有幾個（\(1 \le N \le 10^{18}\)；APCS 逐筆給分）。
先拿下小測資：一個一個檢查
\(N\) 不大時直接從 \(1\) 數到 \(N\)，每個數拆位檢查「每一位都不小於左邊那位」。寫一個判斷函式，從個位往高位拆，只要出現「高位比低位大」就不是：
#include <bits/stdc++.h>
using namespace std;
// x 是不是階梯數字：從個位往左拆，左邊那位不能比右邊大
bool isStair(long long x) {
int right = 9; // 比個位更右邊沒有數字，先放一個最大的 9
while (x > 0) {
int d = x % 10;
if (d > right) return false; // 左邊這位比右邊大：不是
right = d;
x /= 10;
}
return true;
}
int main() {
long long n;
cin >> n;
long long count = 0;
for (long long x = 1; x <= n; x++) // N 大時跑不完
if (isStair(x)) count++;
cout << count << '\n';
return 0;
}
\(N\) 到 \(10^{18}\) 這份程式永遠跑不完，但 \(N\) 在百萬以內的測資它都對——逐筆給分之下這幾筆的分數穩穩到手（本題的計分測資裡 \(N \le 10^6\) 的有 \(12\) 筆，\(60\) 分）。
從小測資到 100 分：按「位數」和「開頭數字」分群數
把階梯數字按位數分群：一位數 \(9\) 個；二位數有幾個？開頭是 \(d\) 的二位階梯數字，第二位可以是 \(d \sim 9\)，共 \(10 - d\) 個——開頭 \(1\) 有 \(9\) 個、開頭 \(2\) 有 \(8\) 個……總共 \(45\) 個。推廣成一張表：
\[\mathrm{cnt}[L][d] = \text{開頭是 } d \text{ 的 } L \text{ 位階梯數字個數} = \sum_{e = d}^{9} \mathrm{cnt}[L - 1][e]\]意思是「開頭 \(d\) 之後接的那個 \(L - 1\) 位階梯數字，開頭 \(e\) 不能比 \(d\) 小」；\(\mathrm{cnt}[1][d] = 1\)。\(L\) 最多 \(18\)、\(d\) 只有 \(1 \sim 9\)，表格一下就填完。
有了表，不超過 \(N\) 的怎麼數？分三群（圖 1 用 \(N = 358\) 示範）：
- 位數比 \(N\) 少的：整群都比 \(N\) 小，查表全加——\(N\) 有 \(L\) 位就是 \(\sum_{\ell < L} \sum_d \mathrm{cnt}[\ell][d]\)。
- 位數相同、第一位比 \(N\) 的第一位小的：不管後面接什麼都比 \(N\) 小，查表加 \(\mathrm{cnt}[L][d]\)（\(d\) 從 \(1\) 到 \(N\) 的第一位減一）。
- 第一位跟 \(N\) 一樣的：那就「貼著 \(N\)」看第二位——第二位比 \(N\) 的第二位小的（而且不小於第一位，不然就不是階梯了），整群查表加進來；第二位也跟 \(N\) 一樣的，再貼著看第三位……一路走到底。
走到底有兩種結局：某一位 \(N\) 的數字比前一位還小——貼著 \(N\) 的數字從這裡起不可能是階梯數字，停；或者 \(N\) 的每一位都走完了，代表 \(N\) 本身就是階梯數字，再加 \(1\)。
#include <bits/stdc++.h>
using namespace std;
long long cnt[20][10]; // cnt[L][d]：開頭是 d 的 L 位階梯數字個數
int main() {
string s;
cin >> s; // N 讀成字串，一位一位看
int L = s.size();
for (int d = 0; d <= 9; d++) cnt[1][d] = 1;
for (int len = 2; len <= L; len++)
for (int d = 0; d <= 9; d++)
for (int e = d; e <= 9; e++) // 下一位 e 不能比 d 小
cnt[len][d] += cnt[len - 1][e];
long long count = 0;
for (int len = 1; len < L; len++) // 群 1：位數比 N 少的，全算
for (int d = 1; d <= 9; d++)
count += cnt[len][d];
int prev = 1; // 這一位至少要是 prev（第一位至少 1：不能有前導零）
bool stillStair = true;
for (int i = 0; i < L; i++) { // 群 2、3：位數相同，貼著 N 走
int digit = s[i] - '0';
for (int d = prev; d < digit; d++) // 這一位比 N 小、又不小於前一位：整群加
count += cnt[L - i][d];
if (digit < prev) { // N 自己在這一位往下掉：貼著走的都不是階梯了
stillStair = false;
break;
}
prev = digit; // 跟 N 一樣，繼續貼著走
}
if (stillStair) count++; // 每一位都走完：N 本身是階梯數字
cout << count << '\n';
return 0;
}
答案最大是 \(10^{18}\) 以下全部的階梯數字，共 \(4686824\) 個，int 夠但表格和累加統一用 long long 省得想。cnt[1][0] = 1 讓表的 \(d = 0\) 那一欄也有值，但數的時候 \(d\) 永遠從 \(1\)（或前一位）起跳，前導零不會混進來。
測過再交：範例的 N 都是「貼著走就掉下去」
範例 1 的 \(25\) 本身是階梯數字（貼著走到底要 \(+1\)），範例 2 的 \(101\) 在第二位 \(0 < 1\) 掉下去。沒蓋到的：\(N\) 是一位數、\(N\) 剛好 \(10\)（二位數開頭 \(1\) 但第二位 \(0\) 掉下去）、\(N\) 全部同一個數字、\(N = 10^{18}\) 這種 \(1\) 後面全是 \(0\)。
| 輸入 | 正確輸出 | 這一筆在測什麼 |
|---|---|---|
7 |
7 |
一位數：\(1 \sim 7\)（小測資版就能驗） |
10 |
9 |
\(10\) 不是階梯數字，答案跟 \(N = 9\) 一樣（小測資版就能驗） |
111 |
55 |
\(N\) 本身是階梯數字：二位以下 \(54\) 個，加上 \(111\) 自己 |
99 |
54 |
二位數全部：\(9 + 45\) |
1000000000000000000 |
4686824 |
\(N = 10^{18}\)：第二位就掉下去，答案是 \(18\) 位以內全部 |
五筆都親眼看過正確，這題就穩了。
常犯錯誤
- 第一位允許從 \(0\) 起跳（前導零混進來，一個數被算很多次）：範例 1 印
32、範例 2 印109。 - 把 \(0\) 本身也算一個：每筆都多 \(1\)——範例 1 印
23、範例 2 印55。 - 「不下降」寫成「嚴格上升」（相等不算）：\(11\)、\(22\) 都被漏掉——範例 1 印
20、範例 2 印45。 - 走到底忘了加 \(N\) 本身：\(N\) 是階梯數字時少 \(1\)——範例 1 印
21。 - 貼著走時 \(N\) 的這一位比前一位小還繼續往下加：加進不存在的群——範例 2 印
55。 - 用
int讀 \(N\)：\(10^{18}\) 讀不進去；讀成字串或long long都可以。 - 一個一個檢查硬上 \(10^{18}\)：永遠跑不完。