题解：P12143 [蓝桥杯 2025 省 A] 好串的数目

· · 题解

P12143 [蓝桥杯 2025 省 A] 好串的数目

思路

滑动窗口

先来分析一些性质。阅读题目，我们发现，连续非递减子串必须满足：对于相邻字符 c_1 和 c_2，满足 c_1=c_2 或者 c_1+1=c_2，我们将这个条件称之为一个约束。那么好串的定义就可以简化为“破坏约束的次数小于等于 1 的字符串”。基于此简化的定义，我们不难发现，子串越长，越难以成为好串；子串越短，越可能成为好串。严格来说，如果一个字符串是好串，那么它的所有子串也都是好串。这个性质构成了暴力解法的重要优化方向。

我们可以枚举子串的右端点下标 r，同时维护左端点下标 l，使得以 r 结尾的子串中，从 l 到 r 的部分是满足要求的最长好串，然后将答案累加 r-l+1，此数值即为以 r 结尾的所有好串的个数。其中，用变量 brk 来维护约束破坏的发生次数。当 brk 超过 1 时，滑动窗口左边界 l 向右移动，直至窗口内好串的条件得以恢复。

Code

可以用变量 brk 来维护约束破坏的发生次数。在 brk 过大时，就增加 l。

#include <bits/stdc++.h>

using namespace std;

const int nn = 100005;
char s[nn];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cin >> s;
    int brk = 0, l = 0;
    int64_t ans = 0;
    for (int r = 0; s[r]; r++) {
        if (r && s[r - 1] + 1 != s[r] && s[r - 1] != s[r])
            brk++;
        while (brk > 1) {
            l++;
            if ((s[l] != s[l - 1] && s[l - 1] + 1 != s[l]))
                brk--;
        }
        ans += r - l + 1;
    }
    cout << ans << '\n';
    return 0;
}

时间复杂度

时间复杂度为 O(n)。