题解：P14113 [IAMOI R4] 彻底怒了

· · 题解

写这题让我彻底怒了，赛时怒写近百行大模拟挂掉了

题目大意

金将军有两个长度为 n 的字符串 s,t，他认为一个字符串的愤怒值为其 CDNL 子串的个数。

现在，他想在 s 中选出一个长度至多为 m 的子串 s'，在 t 中选出一个长度至多为 k 的子串 t'，使 s',t' 按顺序拼接后的字符串的愤怒值最大，你需要帮他求出这个值。

解题思路

定义两个数组用于预处理，分别表示不同区间内包含的 CDNL 的个数，然后就可以计算最多的 CDNL 个数，直接枚举即可得出答案。

代码实现

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int vis1[N],vis2[N];
void solve(){
    int n,m,k;
    string s,t;
    cin>>n>>m>>k>>s>>t;
    s='#'+s,t='#'+t;
    for(int i=1;i<=n;i++){
        vis1[i]=vis1[i-1];
        if(i>=4&&s.substr(i-3,4)=="CDNL") vis1[i]++;
        if(i>m&&s.substr(i-m,4)=="CDNL") vis1[i]--;
    }
    for(int i=n;i;i--){
        vis2[i]=vis2[i+1];
        if(i<=n-3&&t.substr(i,4)=="CDNL") vis2[i]++;
        if(i<=n-k&&t.substr(i+k-3,4)=="CDNL") vis2[i]--;
    }
    int c=-1,cd=-1,cdn=-1,dnl=-1,nl=-1,l=-1,maxn1=0,maxn2=0;
    c=cd=cdn=dnl=nl=l=-1;
    for(int i=1;i<=n;i++){
        maxn1=max(maxn1,vis1[i]);
        if(s[i]=='C') c=max(c,vis1[i]);
        if(i>1&&s.substr(i-1,2)=="CD") cd=max(cd,vis1[i]);
        if(i>2&&s.substr(i-2,3)=="CDN") cdn=max(cdn,vis1[i]);
    }
    for(int i=n;i;i--){
        maxn2=max(maxn2,vis2[i]);
        if(t[i]=='L') l=max(l,vis2[i]);
        if(i<n&&t.substr(i,2)=="NL") nl=max(nl,vis2[i]);
        if(i<n-1&&t.substr(i,3)=="DNL") dnl=max(dnl,vis2[i]);
    }
    int ans=maxn1+maxn2;
    if(c!=-1&&dnl!=-1) ans=max(ans,c+dnl+1);
    if(cd!=-1&&nl!=-1) ans=max(ans,cd+nl+1);
    if(cdn!=-1&&l!=-1) ans=max(ans,cdn+l+1);
    cout<<ans<<"\n";
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int T;cin>>T;
    while(T--) solve();
    return 0;
}