usaco-2.2.1 序言页码

题目描述

给定整数 $N$ （ $1 \leqslant N < 3500$ ）。把 $1,2,\dots,N$ 每个页码写成标准罗马数字，统计 I V X L C D M 各字符出现总次数，按该顺序每行输出 字符次数，未出现的字符不输出。样例：输入 5，输出 I 7 与 V 2。

思路

标准罗马数字每个十进制数位的写法唯一且固定，减法组合只出现在 4 与 9 两列。用千、百、十、个位四张 0…9 片段表把每页逐位拼成罗马数字并累加字符计数，最后按序输出非零项。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26"""ROJ 2026 序言页码：统计 1..N 的罗马数字中每个字符出现次数。"""
import sys
from collections import Counter

# 各数位 0~9 对应的罗马片段（千/百/十/个位），每行即标准罗马记数法
DIGITS = [
    ["", "M", "MM", "MMM"],                                    # 千位：1000~3000
    ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"],  # 百位
    ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"],  # 十位
    ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"],  # 个位
]


def roman(n: int) -> str:
    """把 1..3499 的整数转成标准罗马数字。"""
    return DIGITS[0][n // 1000] + DIGITS[1][n // 100 % 10] + DIGITS[2][n // 10 % 10] + DIGITS[3][n % 10]


def main() -> None:
    n: int = int(sys.stdin.read())
    cnt: Counter[str] = Counter(ch for i in range(1, n + 1) for ch in roman(i))
    # 字符按数字表从小到大输出，跳过未出现的字符
    print("\n".join(f"{c} {cnt[c]}" for c in "IVXLCDM" if cnt[c]))


main()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 09:46
 * update_at: 2026-10-06 09:46
 */
#include <iostream>
using namespace std;

typedef long long ll;

// 各数位 0~9 对应的罗马片段：digit[0] 千位，digit[1] 百位，digit[2] 十位，digit[3] 个位
const char *digit[4][10] = {
    {"", "M", "MM", "MMM", "", "", "", "", "", ""},
    {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"},
    {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"},
    {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"},
};

// 按数字表中从小到大的顺序输出：I V X L C D M
const char ROMAN_CHAR[7] = {'I', 'V', 'X', 'L', 'C', 'D', 'M'};

ll cnt[26]; // cnt[c - 'A'] 记录字符 c 在页码 1..N 的罗马表示中出现次数

// 把一页页码 n 的罗马表示逐字符计入计数器
void count_page(ll n) {
    int d[4]; // d[0] 千位，d[1] 百位，d[2] 十位，d[3] 个位
    d[0] = n / 1000;
    d[1] = n / 100 % 10;
    d[2] = n / 10 % 10;
    d[3] = n % 10;
    for (int p = 0; p < 4; p++) {
        const char *s = digit[p][d[p]];
        for (int k = 0; s[k] != '\0'; k++) {
            cnt[s[k] - 'A']++;
        }
    }
}

int main() {
    ll n;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        count_page(i);
    }
    // 按 I V X L C D M 顺序输出出现过的字符
    for (int k = 0; k < 7; k++) {
        int idx = ROMAN_CHAR[k] - 'A';
        if (cnt[idx] > 0) {
            cout << ROMAN_CHAR[k] << " " << cnt[idx] << "\n";
        }
    }
    return 0;
}

usaco-2.2.1 序言页码

目录

题目描述

思路

参考代码