AT_dwacon5th_prelims_c k-DMC 题解

分析

先考虑 \(k=n\) 的情况。

对于 \(s_j=M\) 的时候，其能够匹配的 \(s_i=D\) 的数量很显然是 \(i \le j-1\) 的时候的数量，求前缀和就能得到。而对于 \(s_j=C\) 的时候，能够完整匹配的就是 \(i \le j-1\) 的时候所有 \(s_i=M\) 能够匹配的数量之和，再套个前缀和就行了。复杂度是 \(O(n)\) 的。

考虑 \(3 \le k \le n\) 的情况。

和上面的差不多，对于 \(s_j=C\) 的时候，它能够得到贡献的 \(M,D\) 都是在 \([j-k+1,j]\) 的。处理这个，只需要在 \(j-k\) 没有越界的时候减去 \(s_{j-k}\) 的贡献。如果 \(s_{j-k}=M\)，因为 \(s_{j-k}\) 之前所有的 \(D\) 对 \(j\) 的贡献都减完了，所以将 \(M\) 出现数量的和 \(-1\)（这个后面会用到）。如果 \(s_{j-k}=D\)，其贡献是 \([j-k+1,j]\) 中 \(M\) 的数量，这个已经统计出来了，直接剪掉即可。如果 \(s_{j-k}=C\)，则不理会，因为它本身不会产生贡献。至于 \(s_j=M,D\) 的情况，跟 \(k=n\) 的时候差不多，只需要注意 \(M\) 的数量。

单次询问的答案就是所有 \(s_j=C\) 的时候得到贡献之和。复杂度 \(O(qn)\)。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define re register
#define il inline
#define PII pair<int,int>
#define x first
#define y second 

const int N=1e6+10;
int n,q,k;
string s;

il void solve(){
	cin>>n>>s>>q;
	while(q--){
		cin>>k;
		int ans=0,sum_d=0,sum_m=0,sum=0;
		for(re int i=0;i<n;++i){
			if(i-k>=0){
				if(s[i-k]=='D') sum-=sum_m,--sumd;
				if(s[i-k]=='M') --sum_m;
			}
			if(s[i]=='D') ++sum_d;
			if(s[i]=='M') sum+=sum_d,++sum_m;
			if(s[i]=='C') ans+=sum;
		}
		cout<<ans<<"\n";
	}
	return ;
}

signed main(){
	solve();
	return 0;
}