文字教学

这道题的核心是枚举第一个不同位置+对称扩展，避免暴力比较所有子串。

1. 关键观察：反转子串 [i,j] 后，新数与原数的大小仅由子串 [i,j] 反转后的部分决定。我们需要找到第一个位置 l（在 [i,j] 内），使得反转后的字符与原字符不同，且反转后的字符更小。
2. 枚举位置对：枚举所有 l < r 且 s[l] > s[r] 的位置对，此时子串 [l,r] 反转后一定更小。
3. 对称扩展：从 [l,r] 向左右扩展，只要左右对称位置的字符相等，扩展后的子串 [i,j] 反转后第一个不同位置仍是 l，因此也合法。

代码

#include <bits/stdc++.h>
using namespace std;

char s[5005];

int main() {
    cin >> s;
    int n = strlen(s);
    long long ans = 0;
    for (int l = 0; l < n; ++l) {
        for (int r = l + 1; r < n; ++r) {
            if (s[l] > s[r]) {
                ans++;
                int i = l - 1;
                int j = r + 1;
                while (i >= 0 && j < n && s[i] == s[j]) {
                    ans++;
                    i--;
                    j++;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}