专栏文章

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

TTzh20111118
P14113题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minkjoq9
此快照首次捕获于
2025/12/02 03:55
3 个月前
此快照最后确认于
2025/12/02 03:55
3 个月前
查看原文
写这题让我彻底怒了，赛时怒写近百行大模拟挂掉了

题目大意

金将军有两个长度为 nn 的字符串 s,ts,t，他认为一个字符串的愤怒值为其 CDNL 子串的个数。
现在，他想在 ss 中选出一个长度至多为 mm 的子串 s′s'，在 tt 中选出一个长度至多为 kk 的子串 t′t'，使 s′,t′s',t' 按顺序拼接后的字符串的愤怒值最大，你需要帮他求出这个值。

解题思路

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

代码实现

CPP
#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;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...