自动搬运

查看原文

来自洛谷，原作者为

	snnbyyds 114514

搬运于2025-08-24 23:13:05，当前版本为作者最后更新于2025-04-14 12:47:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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)$。