[蓝桥杯 2023 省 A] 更小的数(Smaller Number)

题目描述

小蓝有一个长度为 $n$ 且仅由数字字符 0 $\sim$ 9 组成的字符串，下标从 $0$ 到 $n-1$，你可以将其视作一个具有 $n$ 位的十进制数字 $num$。小蓝可以从 $num$ 中选出一段连续的子串并将子串进行反转，最多反转一次。

小蓝想要使选出的子串反转并放回原位置后得到的新数字 $num_{new}$ 满足 $num_{new} < num$。请你帮他计算一共有多少种不同的子串选择方案（只要两个子串在 $num$ 中的起止位置不完全相同就视作不同的方案）。

注意：允许前导零的存在，即数字的最高位可以是 0。

输入格式

输入一行包含一个长度为 $n$ 的字符串表示 $num$（仅包含数字字符 $0 \sim 9$），从左至右下标依次为 $0 \sim n-1$。

输出格式

输出一行包含一个整数表示答案。

样例输入 #1

210102

样例输出 #1

8

数据范围

【样例说明】

一共有 $8$ 种不同的方案：

1. 所选择的子串下标为 $0\sim1$，反转后的 $num_{new} = 120102 < 210102$；
2. 所选择的子串下标为 $0\sim2$，反转后的 $num_{new} = 012102 < 210102$；
3. 所选择的子串下标为 $0\sim3$，反转后的 $num_{new} = 101202 < 210102$；
4. 所选择的子串下标为 $0\sim4$，反转后的 $num_{new} = 010122 < 210102$；
5. 所选择的子串下标为 $0\sim5$，反转后的 $num_{new} = 201012 < 210102$；
6. 所选择的子串下标为 $1\sim2$，反转后的 $num_{new} = 201102 < 210102$；
7. 所选择的子串下标为 $1\sim4$，反转后的 $num_{new} = 201012 < 210102$；
8. 所选择的子串下标为 $3\sim4$，反转后的 $num_{new} = 210012 < 210102$。

【评测用例规模与约定】

对于 $20\%$ 的评测用例，$1 \le n \le 100$；

对于 $40\%$ 的评测用例，$1 \le n \le 1000$；

对于所有评测用例，$1 \le n \le 5000$。

知识点与难度

本题涉及的知识点从属于 CSP-J，难度（CF Rating）：1250。

测试点分布

出处：原题链接