Number

形式化题目

给定 k 位十进制整数 n。依次执行 k-1 次操作，第 j 次操作针对当前数从右数第 j 位：

若该位数字 $\leqslant 4$ ：将该位及其右侧所有位全部置 0；
若该位数字 $\geqslant 5$ ：同样全部置 0，并向左一位进 1；进位按十进制加法连锁传播（某位达到 10 即向更高位进 1），允许最高位进位使数位增加；数位增加后仍只执行剩余的 k-1 次操作。

要求输出初始数及每次操作后的数，共 k 个数，用 " -> " 连接（k = 1 时只输出初始数）。

思路

一句话本质：每一步都是把"当前的数"舍入到 $10^j$ 的倍数（第 $j$ 位 $\geqslant 5$ 就进位），而低位进位会改写高位数字，所以必须模拟"当前数"，且进位要当场连锁处理。

问题？ 每一步具体做了什么？

看最低位：数字 $\leqslant 4$ 就把它和更低位全部置 0； $\geqslant 5$ 就置 0 后向前一位进 1。例如 2023 的最低位是 3，于是 2023 -> 2020。更一般地，第 j 步（从右数第 j 位）就是"把数舍入到 $10^j$ 的倍数，逢 5 进位"。

问题？ 进位会改写高位，后面的步骤会不会因此受影响？

会，而且这正是本题最关键的坑。以 14995 为例：最低位 5 进位后，9+1=10 连锁进位，把千位的 4 改写成 5；之后处理千位时，看到的数字是 5 而不是原始数字 4，还要再进位一次。所以绝不能拿原始数字逐位独立判断——每一步看到的都是"当前数"。

问题？ 进位会连锁发生吗？

会。299997 的最低位 7 进位后，一路 9+1=10 连锁，直接变成 300000。所以进 1 之后要用 while 循环把超过 9 的位逐位归一化（本位减 10、更高位加 1），直到全部小于 10。

问题？ 最高位进位会把数变长吗？变长后怎么处理？

会，例如 95 -> 100：十位 9+1=10 后继续进位，新开一个百位。题目说"位数编号规则不变"，意思是不管数变多长，仍然只做原来的 k-1 步，新增的最高位不参与后续步骤。实现上给数组多留几个高位空位即可。

问题？ 数字最多 100 位，装不进整数，怎么模拟？

字符串读入，逆序存进 int 数组（个位在 0 号位），预留高位空间；每一步：若第 p 位 $\geqslant 5$ 就向 p+1 位进 1 并连锁进位，然后把第 p 位及其以下全部置 0（更低位在之前步骤已是 0），最后从最高非零位输出。

先看一个小数据版本，它直接按题意用 long long 整数模拟，把"连锁进位"完全交给整数加法：

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/**
 * 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-08-28 19:08
 * update_at: 2026-08-28 19:08
 */
// brute.cpp：小数据暴力解，直接按题意逐步"把当前数舍入到 10^j 的倍数"。
// 用 long long 整数模拟：舍去低位 = 除以 10^j 再乘回；第 j 位 >= 5 就再 +10^j。
// 连锁进位由整数加法自动完成，是最贴近题意的写法。
// 只适合 k <= 15 左右的小数据（对拍用），k 大时数装不进 long long。
#include <bits/stdc++.h>
using namespace std;

int k;
string s;

// 计算 10^e
long long pow10(int e) {
    long long res = 1;
    for (int i = 0; i < e; i++) res *= 10;
    return res;
}

void solve() {
    cin >> k >> s;

    // 字符串转成整数（小数据才装得下）
    long long n = 0;
    for (int i = 0; i < k; i++) n = n * 10 + (s[i] - '0');

    cout << n;
    for (int j = 1; j <= k - 1; j++) { // 第 j 步处理从右数第 j 位
        long long p = pow10(j);                    // 10^j
        long long digit = (n / (p / 10)) % 10;     // 当前数从右数第 j 位的数字
        if (digit >= 5)
            n = (n / p + 1) * p; // 舍去低位并向前进 1（进位自动连锁）
        else
            n = (n / p) * p;     // 只舍去低位
        cout << " -> " << n;
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

暴力版与正解是同一个模拟：小数据装得进整数，进位就由整数加法自动完成；正解因为 k <= 100 装不进整数，改用数组手动进位，流程一字不差。

下面这张表展示 14995 的完整过程，注意千位 4 如何被最低位的进位改写成 5：

步骤	处理位（从右数）	处理前数字	该位数字	动作
1	第 1 位	14995	5	$\geqslant 5$ ，进 1：9+1=10 连锁进位，千位 4 -> 5，得 15000
2	第 2 位	15000	0	$\leqslant 4$ ，舍去，不变
3	第 3 位	15000	0	$\leqslant 4$ ，舍去，不变
4	第 4 位	15000	5	$\geqslant 5$ ，进 1：万位 1 -> 2，得 20000

从表中看两件事：一是第 1 步的连锁进位把千位 4 改写成 5；二是第 4 步处理的正是改写后的 5，于是又进了一次位。这就是"必须对当前数模拟"的直接证据。

代码

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
56
57
58
59
60/**
 * 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-08-28 19:08
 * update_at: 2026-08-28 19:08
 */
// A. Number：按位四舍五入的数组模拟。
// 逆序存数字（a[0] 是个位），每步对"当前数"的第 p 位判断：
// 该位 >= 5 就向前一位进 1 并连锁进位，然后把第 p 位及以下全部置 0。
#include <bits/stdc++.h>
using namespace std;

const int MAXK = 105;

int k;
int a[MAXK + 5]; // a[0] 是个位，逆序存放数字，多留几个位置给最高位进位

// 输出当前数：从最高非零位开始，跳过前导零。
void print_num() {
    int top = MAXK + 4;
    while (top > 0 && a[top] == 0) top--;
    for (int i = top; i >= 0; i--) cout << a[i];
}

void solve() {
    string s;
    cin >> k >> s;
    memset(a, 0, sizeof(a));
    for (int i = 0; i < k; i++) a[i] = s[k - 1 - i] - '0';

    print_num();
    for (int p = 0; p < k - 1; p++) { // 从个位向高位依次处理 k-1 步
        // 第 p 位 >= 5：舍去后向前一位进 1
        if (a[p] >= 5) {
            a[p + 1]++;
            // 连锁进位：某位超过 9 就继续向更高位进，直到全部小于 10
            int j = p + 1;
            while (a[j] >= 10) {
                a[j + 1] += a[j] / 10;
                a[j] %= 10;
                j++;
            }
        }
        a[p] = 0; // 舍去第 p 位（更低的位在之前步骤已全部为 0）
        cout << " -> ";
        print_num();
    }
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

复杂度

每步的判断与置 0 是 $O(1)$ ，进位链一次最多推进 $O(k)$ 位，共 k-1 步，总时间复杂度 $O(k^2)$ ；空间复杂度 $O(k)$ （一个长度为 MAXK + 5 的数组）。k <= 100、T <= 10，绰绰有余。

总结

本题是典型的"带状态按位模拟"：状态就是当前数，步骤顺序固定，没有需要推导的数学结论。三个易错点：

对当前数判断——低位进位会改写高位，后续步骤看到的是改写后的数字（14995 -> 20000）；
进位连锁归一化——某位达到 10 必须继续向上进位，直到全部小于 10（299997 -> 300000）；
最高位预留空间——进位可能使数变长（95 -> 100），数组要多开几个位置，且数位编号规则不变。

小数据先写整数模拟（brute.cpp）验证题意理解，再用数组版实现满分做法，二者对拍一致，是最稳的做题节奏。

目录

形式化题目

思路

代码

复杂度

总结