题解：P13291 [GCJ 2013 #1C] Consonants

_DATA_X_ · 2025-08-09 16:17:06 · 题解

P13291 题解：

主要思路：

定义数组存储到当前字符的辅音字母子串的长度，再循环遍历数组，如果当前长度 \ge n，就加上当前的 i-n+1，用变量存储这个值，否则就加上变量的值，最后输出结果。

解释：为什么要加 i-n+1？

我们不难想到，如果出现了一个长度为 n 的辅音字母子串，那么这个子串加上前面一个字母构成的新子串也一定满足其中包含一个长度为 n 的辅音字母子串，所以这个问题就转化成了求出当前辅音字母子串前面字母的数量，最后在加上这个子串本身。不难看出，这个值就是子串的左端点，子串的右端点为当前循环遍历到的 i，那左端点就是 i 减去子串长度 n 再加上子串本身的数量 1，即 i-n+1。

代码实现：

• 定义数组 dp 存储到当前字符的辅音字母子串的长度，再定义一个判断辅音字母的函数，如果当前字母为辅音字母，就让 dp_i=dp_{i-1}+1，否则 dp_i=0。
• 数组处理完后，定义变量 cnt1 和 cnt2，初始化为 0，循环遍历数组，如果当前的 dp_i>=n，就更新 cnt2=i-n+1，再让 cnt1 加上 cnt2。遍历完以后，此时的 cnt1 存储的就是结果，输出答案即可。（注意输出格式）

AC Code：

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
char f[6]={' ','a','e','i','o','u'};
inline bool fun(char a){
    for(int i=1;i<=5;i++){
        if(a==f[i]){
            return false;
        }
    }
    return true;
}
constexpr int N=1e7; 
int T; 
int dp[N];
int32_t main(){
    cin.tie(nullptr)->ios::sync_with_stdio(false);
    cout.tie(nullptr)->ios::sync_with_stdio(false);
    cin>>T;
    for(int res=1;res<=T;res++){
        string s;cin>>s;
        int n;cin>>n;
        for(int i=0;i<N;i++){
            dp[i]=0;
        }
        int cnt1=0,cnt2=0;
        for(int i=1;i<=s.size();i++){
            if(fun(s[i-1])){
                dp[i]=dp[i-1]+1;
            }
        }
        for(int i=n;i<=s.size();i++){
            if(dp[i]>=n){
                cnt2=i-n+1;
            }
            cnt1+=cnt2;
        }
        cout<<"Case #"<<res<<": "<<cnt1<<endl;
    }
    return 0;
}