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

Kagamino_Natsumi · 2025-04-13 02:36:35 · 题解

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

思路

我们可以把一整个串分割为多个极大的“连续非递减子串”，称之为“块”。例如， 12258 可以被分割为 122 ， 5 和 8 。

题目中要求一个好串长度为 1 （此时其本身为连续非递减子串），或可以拆分为两个连续非递减子串（注意到长度大于 1 的连续非递减子串也可以被拆分成两个连续非递减子串）。也就是，好串要么本身就是连续非递减子串，要么是两个连续非递减子串拼接的结果。

换句话说，好串必须在某个块内，或正好在相邻的两个块中。

据此可以写出代码，时间复杂度为 O(n)。

Code

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

int n;
char s[100007];
int cut[100007];
int cnt = 0;
long long ans = 0;

int main()
{
    cin >> (s + 1);
    n = strlen(s + 1);
    int last = 0;
    for(int i = 2; i <= n; i++)
    {
        if(s[i] == s[i - 1] || s[i] == s[i - 1] + 1)
            continue;
        cut[++cnt] = i - last - 1;
        last = i - 1;
    }
    cut[++cnt] = n - last;
    for(int i = 1; i <= cnt; i++)
    {
        ans += 1ll * cut[i] * (cut[i] - 1) / 2 + cut[i];//在块内，长度大于1或长度为1 
        ans += 1ll * cut[i] * cut[i - 1];//分在相邻两块中 
    }

    cout << ans << endl;
    return 0;
}

考场Code

考场上没来得及细想，使用了更劣、更丑陋的算法进行统计，不过也足以通过此题。思路是：枚举好串的首位，则在它所处的块的下一块末尾之前的所有数，都可以成为该好串的末位。

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

int n;
char s[100007];
int cut[100007];
int cnt = 1;
long long ans = 0;

int main()
{
    cin >> (s + 1);
    n = strlen(s + 1);
    cut[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        if(s[i] == s[i - 1] || s[i] == s[i - 1] + 1)
            continue;
        else 
        {
            cnt++;
            cut[cnt] = i;
        }
    }
    cnt++;
    cut[cnt] = n + 1;
    cnt++;
    cut[cnt] = n + 1;
    for(int i = 1; i <= n; i++)
    {
        int pos = upper_bound(cut + 1, cut + cnt + 1, i) - cut - 1;
        ans += (cut[pos + 2] - i);
    }
    cout << ans << endl;
    return 0;
}