「PA 2018」Język polski 题解

问题分析

给定字符串 $s$，统计所有包含至少一个长度为 3 的连续元音或连续辅音子串的子串数量。

波兰语元音字母：a, e, i, o, u, y 辅音字母：其他小写字母

关键思路：补集转换

直接统计满足条件的子串比较困难，因为一个子串可能包含多个"坏段"（连续3个相同类型字符），会重复计数。

更好的方法：

• 计算总子串数：$\frac{n(n+1)}{2}$
• 计算不满足条件的子串数
• 两者相减得到答案

不满足条件的子串特征

不满足条件的子串：没有任何长度为 3 的连续元音或连续辅音段

这意味着：

• 任意连续的 3 个字符必须包含至少一个元音和一个辅音
• 即：不能出现连续 3 个元音或连续 3 个辅音

算法步骤

1. 预处理：标记每个字符是元音还是辅音
2. 寻找极长的不合法段：使用双指针找到最长的满足"没有连续3个相同类型字符"的子串
3. 计算不合法子串数：对每个极长段计算 $\frac{L(L+1)}{2}$
4. 最终答案：总子串数 - 不合法子串数之和

C++ 代码实现

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    string s;
    cin >> s;
    int n = s.length();
    
    // 标记元音字母
    vector<bool> is_vowel(n, false);
    string vowels = "aeiouy";
    for (int i = 0; i < n; i++) {
        if (vowels.find(s[i]) != string::npos) {
            is_vowel[i] = true;
        }
    }
    
    long long ans = 0;
    
    // 对于每个位置，找到以它开头的最短满足条件的子串
    for (int i = 0; i < n; i++) {
        // 找到从i开始的最短包含连续3个相同类型的子串
        int j = i;
        int cnt_vowel = 0, cnt_consonant = 0;
        
        while (j < n) {
            if (is_vowel[j]) {
                cnt_vowel++;
                cnt_consonant = 0;
            } else {
                cnt_consonant++;
                cnt_vowel = 0;
            }
            
            if (cnt_vowel >= 3 || cnt_consonant >= 3) {
                // 找到满足条件的子串，后面的所有子串都满足
                ans += (n - j);
                break;
            }
            j++;
        }
    }
    
    cout << ans << endl;
    
    return 0;
}

最终算法思路

对于每个起始位置 $i$：

1. 找到从 $i$ 开始的最短满足条件的子串 $s[i..j]$
2. 那么所有 $s[i..k]$（$k \ge j$）都满足条件
3. 对每个 $i$ 累加 $(n - j)$

复杂度

• 时间复杂度：$O(n^2)$ 最坏情况，但实际运行较快
• 可以通过预处理优化到 $O(n)$

算法标签

• 双指针扫描
• 字符串处理
• 子串计数

总结

本题的关键在于正确理解题意：统计包含至少一个长度为3的连续元音或辅音段的子串数量。通过对于每个起始位置寻找最短满足条件的子串，可以高效统计答案。