AcWing
4997. 更小的数
题面容许的时间复杂度为$O(n^2)$. 所以最多枚举两层循环。
一般的枚举方式是，先枚举右端点，再枚举左端点，再枚举一层，用于判断倒置后是否变小。但是这样做会超时。
考虑能否用上一次枚举的状态加速判断。由于倒置是以一个点为中心操作的，不妨枚举每一个用于倒置的中心点。为了方便对偶数长度字符倒置的操作，对原字符串进行处理，在每两个字符之间插入一个占位符，这样就能处理偶数长度的字符串倒置。
每次向外扩展前，记录last，表示当前倒置是否能让数字更小。这样在扩展后，如果当前的左右端点已经可以确定倒置后会变小，直接令结果加1，last = true；如果左右端点相等（且不为占位符），就直接判断这个last是否为true即可。
在判断时，如果碰到左右端点都为占位符，直接跳过。
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 5010;
string a;
char b[2 * N];
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> a;
int s = 0;
for(int i = 0; i <= (int)a.size() - 1; i ++) b[s ++] = a[i], b[s ++] = '#';
s --; // 退掉最后的占位符'#'，s为处理后的字符串的长度
int res = 0;
for(int i = 0; i <= s - 1; i ++){ // 枚举所有中间的数
bool last = false;
for(int d = 1; i - d >= 0 && i + d <= s - 1; d ++){ // 枚举一半区间的长度
if(b[i + d] < b[i - d]){
last = true;
res ++;
}
else if(b[i + d] == b[i - d]){
if(b[i + d] == '#') continue;
if(last) res ++;
}
else last = false;
}
}
cout << res;
return 0;
}