蓝桥杯2023年-更小的数（字符串，推理）

题目描述

小蓝有一个长度均为 n 且仅由数字字符 0 ∼ 9 组成的字符串，下标从 0 到 n − 1，你可以将其视作是一个具有 n 位的十进制数字 num，小蓝可以从 num 中选出一段连续的子串并将子串进行反转，最多反转一次。小蓝想要将选出的子串进行反转后再放入原位置处得到的新的数字 numnew 满足条件 numnew < num，请你帮他计算下一共有多少种不同的子串选择方案，只要两个子串在 num 中的位置不完全相同我们就视作是不同的方案。

注意，我们允许前导零的存在，即数字的最高位可以是 0 ，这是合法的。

思路

题目意思其实就求该字符串中有多少个翻转后字典序变小的子串。分成两种情况：

情况一：子串首尾不相等，则如果首大于尾，则翻转后肯定会变小。

情况二：子串首尾相等，则看下一个位置，如果还相等，则再看下一个位置，，直到不相等为止。这时再比较大小，如果首大于尾，则翻转后会变小。

优化：情况二其实是情况一的扩展。因为目标都是寻找首大于尾的两个点。则我们可以只寻找首大于尾的两个点，然后往外扩展，直到枚举完两边相等的点，这些子串也符合条件（情况二的逆推过程）。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;cin>>s;
    int ans=0;
    int n=s.size();
    for(int i=0;i<n;i++){
        for(int j=i+1;j<n;j++){
            if(s[i]>s[j]){
                int temp=1;
                while(i-temp>=0&&j+temp<n&&s[i-temp]==s[j+temp])temp++;
                ans+=temp;
            }
        }
    }
    cout<<ans;
}