形式化题目

给定一个长度为 $n$、只含数字字符 0–9 的字符串 $s$，把它视作一个允许前导零的十进制数。 一次操作选取下标对 $l<r$，把子串 $s[l..r]$ 原地反转，其余字符不动，得到新串 $t$。

统计满足 $t<s$ 的下标对 $(l,r)$ 的数量（位置不完全相同就算不同方案）。 由于 $t$ 与 $s$ 等长，这里的比较就是等长串的字典序比较，前导零不需要特殊处理。

例如 $s=\texttt{210102}$ 时答案为 $8$，对应的下标对是 $(0,1),(0,2),(0,3),(0,4),(0,5),(1,2),(1,4),(3,4)$。

暴力解法

思路

最直接的做法就是照抄题面：枚举所有 $l<r$，把 $s[l..r]$ 真的反转出来得到 $t$， 再从头逐位比较 $t$ 与 $s$，若 $t<s$ 就计数。

写成 brute.cpp 里的三层循环：

1. 外层 $l$ 从 $0$ 到 $n-1$，中层 $r$ 从 $l+1$ 到 $n-1$，枚举一个子串；
2. 把原串复制到 t，用双指针 i、j 从两端向中间交换，完成原地反转；
3. smaller_than(t, s) 逐位比较，遇到第一处不同就返回该位是否更小；两串完全相同则返回 false（因为要求严格小于）。

这个做法没有用到任何规律，所以不可能漏解或算错，但它也把「中间段 $s[l+1..r-1]$ 与它的反转哪个更小」 在每一个包含它的区间里重复算了一遍。

代码

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
61/**
 * 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-03 10:40
 * update_at: 2026-10-03 10:40
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
// 做法完全照抄题面：枚举所有子串 s[l..r]（l < r），真的把这段反转出来，
// 再逐位和原串比较，统计新数字严格更小的方案数。
// 时间 O(n^3)、空间 O(n)，只适合 n 在几百以内的小数据。
#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1005;

int n;
char s[MAXN]; // 原数字串
char t[MAXN]; // 反转子串后得到的新数字串

// 逐位比较两个等长的数字串：a 是否严格小于 b（允许前导零，等长时字典序就是数值序）
bool smaller_than(const char *a, const char *b) {
    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) {
            return a[i] < b[i];
        }
    }
    return false; // 完全相同，不满足严格小于
}

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

    cin >> s;
    n = (int)strlen(s);

    long long ans = 0;

    for (int l = 0; l < n; l++) {
        for (int r = l + 1; r < n; r++) {
            // 复制原串，再把 s[l..r] 原地反转
            for (int i = 0; i < n; i++) {
                t[i] = s[i];
            }
            for (int i = l, j = r; i < j; i++, j--) {
                char tmp = t[i];
                t[i] = t[j];
                t[j] = tmp;
            }

            if (smaller_than(t, s)) {
                ans++;
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

复杂度

• 时间：$O(n^2)$ 个下标对，每个用 $O(n)$ 完成复制、反转和比较，总 $O(n^3)$。
• 空间：$O(n)$，只需要两个长度 $n$ 的字符数组。

瓶颈

瓶颈不在枚举下标对（那只有 $O(n^2)$），而在每次都要重新比较整个区间。 $n=5000$ 时枚举量约 $1.25\times10^7$，乘上平均 $n/3$ 的比较长度就是 $10^{10}$ 量级，无法接受。 真正被浪费掉的信息是：区间内部的比较结果，其实可以由更短的区间推出来。

正解

关键观察

反转是局部操作：它只改动 $[l,r]$ 这一段，区间外的字符原位不动。由此立刻得到一个结论。

两串的第一处不同，必然出现在 $[l,r]$ 内部。

因为对任意 $i<l$ 或 $i>r$ 都有 $t_i=s_i$，两串在这些位置完全相同，差别只可能落在 $[l,r]$ 里。

于是可以只盯住区间内部，定义

答案就是 $\displaystyle\sum_{l<r} f(l,r)$：一共有 $\dfrac{n(n-1)}{2}$ 个方案，每个方案恰好贡献 $0$ 或 $1$。

为什么可以递推？ 位置 $l$ 是区间内最靠左的位置，它是候选的「第一处不同」。 分两种情况：

情形一：$s[l]\neq s[r]$。 反转后 $t_l=s[r]$，而 $s[l]\neq s[r]$，所以位置 $l$ 就是第一处不同， 比较结果只看这一位就定了：

情形二：$s[l]=s[r]$。 位置 $l$ 上两串相同，位置 $r$ 上两串也相同（$t_r=s[l]=s[r]$）， 所以第一处不同只能更深。此时看位置 $l+1..r-1$：

• $t$ 在这一段的值是 $\mathrm{rev}(s[l+1..r-1])$，
• $s$ 在这一段的值是 $s[l+1..r-1]$ 本身。

「$t$ 与 $s$ 的第一处不同在哪」和「$\mathrm{rev}(u)$ 与 $u$ 的第一处不同在哪」是同一个位置（记 $u=s[l+1..r-1]$）， 所以 $f(l,r)$ 恰好等于「把 $s[l+1..r-1]$ 反转一次后是否变小」，也就是 $f(l+1,r-1)$：

看一个具体的例子，$s=\texttt{210102}$、$(l,r)=(3,4)$：区间是 10，$s[3]=\texttt{1}\neq s[4]=\texttt{0}$ 且 $\texttt{1}>\texttt{0}$，所以 $f=1$。 再取 $(l,r)=(3,5)$：区间是 102，两端 $s[3]=\texttt{1}\neq s[5]=\texttt{2}$，因为 $\texttt{1}\not>\texttt{2}$ 所以 $f=0$ ——确实反转 102 得 201，新串 210201 比原串 210102 大。

递推的边界。 当 $r=l+1$（长度 2，中间是空串）或 $r=l+2$（长度 3，中间只有一个字符）时， 反转整段得到的是它自己或只交换了两端、中间不变，总之新串与原串完全相同，$f=0$。 这正好是「两端相同就往下钻」在钻到空串/单字符时的自然终止。

递推的方向。 $f(l,r)$ 只依赖 $f(l+1,r-1)$，区间长度每次减少 $2$。 所以按区间长度从小到大（等价地，按右端点 $r$ 递增）计算，被依赖的值总是已经算好的。

状态表

把样例 $s=\texttt{210102}$ 的所有 $f(l,r)$ 列出来（行是 $l$，列是 $r$，— 表示 $l\geqslant r$ 不合法）：

所有 $1$ 加起来是 $8$，与样例一致。观察两处递推关系：

• $(l,r)=(0,1)$：$s[0]=\texttt{2}>s[1]=\texttt{1}$，直接给 $1$。
• $(l,r)=(0,3)$：$s[0]=\texttt{2},s[3]=\texttt{1}$，两端不同，给 $1$。
• $(l,r)=(0,5)$：两端 $s[0]=\texttt{2}$ 与 $s[5]=\texttt{2}$ 相等，于是读内层 $f(1,4)=1$，所以 $f(0,5)=1$。
• $(l,r)=(1,5)$：两端 $s[1]=\texttt{1}\neq s[5]=\texttt{2}$，给 $0$。

第 3 条正是「两端相同 → 看中间」的现场演示。

空间压缩

最直接的想法是开一张 $5000\times5000$ 的 int 表，但那是 $10^8$ 字节（约 $100$MB）， 很容易超过内存限制。注意递推只用到「长度少 $2$」的一层，所以可以滚动。

按右端点 $r$ 从 $1$ 递增到 $n-1$：

• 用 dp_prev[l] 保存上一轮（右端点为 $r-1$）的答案，于是 dp_prev[l + 1] 就是 $f(l+1,r-1)$；
• 本轮每个 $f(l,r)$ 写进 cur[l]，并累加到 ans；
• 一轮结束把 cur 整体复制到 dp_prev，进入下一轮。

这样内存降到三个 $O(n)$ 的数组。要注意 dp_prev 与 cur 必须分开： 如果原地只用一个数组，本轮刚写好的 $f(l,r)$ 会在紧接着计算 $f(l-1,r)$ 时 被误读成 $f(l,r-1)$，答案就错了。这个坑很容易踩到，而且样例恰好能暴露它。

代码

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74/**
 * 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-03 10:40
 * update_at: 2026-10-03 10:40
 */
// P9232 [蓝桥杯 2023 省 A] 更小的数
// 记 f(l, r) = 「把子串 s[l..r] 反转后，新数字是否严格小于原数字」。
// 反转只改动 [l, r] 这一段，所以新串与原串的比较结果由**第一处不同**决定。
// 按位置从外向内看，第一处不同只能出现在三段之一：
//   1. 位置 l：新串是 s[r]，原串是 s[l]；
//   2. 位置 r：新串是 s[l]，原串是 s[r]；
//   3. 严格夹在中间的 s[l+1..r-1]。
// 情形 1 和 3 是互斥的，于是得到转移：
//   若 s[l] != s[r]：第一处不同就在位置 l，f(l, r) = [s[l] > s[r]]；
//   若 s[l] == s[r]：位置 l、r 都相同，只能看中间，f(l, r) = f(l+1, r-1)。
// 当 r - l + 1 = 2 或 3 时中间为空串或单字符，反转后与原串完全相同，
// 这两个区间的 f 恒为 0（正好是 s[l]==s[r] 分支的边界）。
//
// 实现：按右端点 r 从小到大推进。f(l, r) 在两端相等时需要 f(l+1, r-1)，
// 那是「右端点为 r-1」的上一轮结果，因此只要用 prev[] 保存上一轮的 f，
// 本轮结果写进 cur[]，每轮结束再把 cur 复制给 prev，空间就是 O(n)。
// 答案 = 所有 l < r 的 f(l, r) 之和，最多 n(n-1)/2 个方案。
#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 5005;

int n;
char s[MAXN];  // 输入的数字串，下标 0..n-1
int dp_prev[MAXN]; // dp_prev[l] 保存上一轮（右端点为 r-1）的 f(l, r-1)
int cur[MAXN]; // cur[l] 保存本轮（右端点为 r）的 f(l, r)

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

    cin >> s;
    n = (int)strlen(s);

    long long ans = 0;

    // 枚举右端点 r，左端点 l 从 r-1 递减到 0
    for (int r = 1; r < n; r++) {
        for (int l = r - 1; l >= 0; l--) {
            int v; // v = f(l, r)

            if (s[l] != s[r]) {
                // 第一处不同就在最左边的 l：反转后该位变成原来的 s[r]
                v = (s[l] > s[r]) ? 1 : 0;
            } else {
                // 两端字符相同，整体是否更小取决于中间子串 s[l+1..r-1]
                if (r - l + 1 >= 4) {
                    v = dp_prev[l + 1]; // f(l+1, r-1)，上一轮已算好
                } else {
                    v = 0; // 长度 2、3：中间为空串或单字符，反转后不变
                }
            }

            cur[l] = v;
            ans += v;
        }

        // 本轮结果成为下一轮需要的「右端点为 r」的历史答案
        for (int i = 0; i < n; i++) {
            dp_prev[i] = cur[i];
        }
    }

    cout << ans << "\n";
    return 0;
}

复杂度

• 时间：外层 $r$ 共 $n-1$ 轮，第 $r$ 轮做 $r$ 次 $O(1)$ 转移，合计 $\sum_{r=1}^{n-1} r = O(n^2)$；每轮复制 cur 到 dp_prev 的 $O(n)$ 也包含在内。 $n=5000$ 时约 $1.25\times10^7$ 次转移，实测在 $0.01$s 内返回。
• 空间：s、dp_prev、cur 各 $O(n)$，总 $O(n)$，与暴力的空间同阶。

总结

• 核心观察：反转只改动 $[l,r]$，所以两串的第一处不同必定落在区间内部。 位置 $l$ 就是这个区间的第一位候选人。
• 递推：两端字符不同时，第一处不同就在 $l$，$f(l,r)=[s[l]>s[r]]$； 两端相同时，$l$ 和 $r$ 都被“对齐”，问题等价于去掉两端后的子区间，$f(l,r)=f(l+1,r-1)$。
• 边界：长度为 2、3 的区间反转后与原串完全相同，$f=0$，作为递推的自然终止。
• 实现：按右端点滚动，dp_prev 存上一轮的 $f$、cur 存本轮， 时间和空间都是 $\Theta(n)$ 与 $O(n)$ 的组合；不要省掉 cur 只用单数组原地更新。
• 易错点：严格小于而不是小于等于（相同时不能计数）；$l=r$ 不是合法操作； 答案上限 $n(n-1)/2\approx1.25\times10^7$ 要用 long long； 前导零合法，等长串按字典序比较即可。