专栏文章

题解：P12246 电 van

CCocoonBroken
P12246题解参与者 7已保存评论 6

文章操作

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

当前评论
6 条
当前快照
1 份
快照标识符
@mipk56ex
此快照首次捕获于
2025/12/03 13:19
3 个月前
此快照最后确认于
2025/12/03 13:19
3 个月前
查看原文
题意：
给你一个长度为 nn 的只包括 v\texttt{v}、a\texttt{a}、n\texttt{n} 三个字符的字符串，有 mm 次操作，每次操作交换 sxs_x 和 sx+1s_{x+1}，求每次操作后字符串中 van\texttt{van} 作为子序列的出现次数。
思路：
暴力解法直接排除，思考怎么快速计算。
我们可以寻找每一个字符 a\texttt{a}，统计其前面的 v\texttt{v} 以及后面 n\texttt{n} 的数量，相乘便是含有这个 a\texttt{a} 的子序列的数量，累加便是最后的答案。
再考虑修改，每次修改只会交换前后的字符，重要的是，每次修改只会影响一个 a\texttt{a} 前后 v\texttt{v} 和 n\texttt{n} 的数量。 具体需要分类讨论：
  1. sxs_x 为字符 a\texttt{a}；
  2. sxs_x 为字符 v\texttt{v}；
  3. sxs_x 为字符 n\texttt{n}。
当 sxs_x 为字符 a\texttt{a} 时，讨论 sx+1s_{x+1}：
  1. sx+1s_{x+1} 为字符 x\texttt{x}，则相当于没修改；
  2. sx+1s_{x+1} 为字符 v\texttt{v}，则 a\texttt{a} 前面 v\texttt{v} 的数量加一；
  3. sx+1s_{x+1} 为字符 n\texttt{n}，则 a\texttt{a} 后面 n\texttt{n} 的数量减一。
当 sx+1s_{x+1} 为字符 a\texttt{a} 时，讨论 sxs_{x}：
  1. sxs_{x} 为字符 x\texttt{x}，同上；
  2. sxs_{x} 为字符 v\texttt{v}，则 a\texttt{a} 前面 v\texttt{v} 的数量减一；
  3. sxs_{x} 为字符 n\texttt{n}，则 a\texttt{a} 后面 n\texttt{n} 的数量加一。
都不是则没有影响，因为只有当 a\texttt{a} 是被修改的两个字符中其中一个才会受到影响，具体证明很简单，不再赘述。
每次修改减去当前 a\texttt{a} 的贡献，再更新前后 v\texttt{v} 和 n\texttt{n} 的数量，最后加上更新后 a\texttt{a} 的贡献就是最后的答案。
代码：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
const int N=1e6+5;
int n,m;
string s;
int va[N],an[N];
vector<int>a;
int numa;
signed main(){
    IOS;
    cin>>n>>m;
    cin>>s;
    s=" "+s;
    int numv=0,numn=0;
	for(int i=1;i<=n;i++){
		if(s[i]=='v')numv++;
		if(s[i]=='a'){
			va[i]=numv;
			a.push_back(i);
			numa++;
		}
	}
	for(int i=n;i>=1;i--){
		if(s[i]=='n')numn++;
		if(s[i]=='a'){
			an[i]=numn;
		}
	}
	int ans=0;
	for(int i=0;i<numa;i++){
		ans=ans+va[a[i]]*an[a[i]];
	}
	while(m--){
		int x;
		cin>>x;
		int l=0,r=numa-1;
		int mid;
		while(l<r){
			mid=l+r>>1;
			a[mid]>=x?r=mid:l=mid+1;
		}
		int aid=a[r];
		if(aid==x){
			if(s[x+1]=='a'){
				cout<<ans<<endl;
			}
			if(s[x+1]=='v'){
				ans=ans-va[x]*an[x];
				swap(va[x],va[x+1]);
				swap(an[x],an[x+1]);
				va[x+1]++;
				ans=ans+va[x+1]*an[x+1];
				a[r]++;
				cout<<ans<<endl;
			}
			if(s[x+1]=='n'){
				ans=ans-va[x]*an[x];
				swap(va[x],va[x+1]);
				swap(an[x],an[x+1]);
				an[x+1]--;
				ans=ans+va[x+1]*an[x+1];
				a[r]++;
				cout<<ans<<endl;
			}
		}
		else if(aid==x+1){
			if(s[x]=='v'){
				ans=ans-va[x+1]*an[x+1];
				swap(va[x],va[x+1]);
				swap(an[x],an[x+1]);
				va[x]--;
				ans=ans+va[x]*an[x];
				a[r]--;
				cout<<ans<<endl;
			}
			if(s[x]=='n'){
				ans=ans-va[x+1]*an[x+1];
				swap(va[x],va[x+1]);
				swap(an[x],an[x+1]);
				an[x]++;
				a[r]--;
				ans=ans+va[x]*an[x];
				cout<<ans<<endl;
			}
		}
		else{
			cout<<ans<<endl;
		}
		swap(s[x],s[x+1]);
		/*cout<<s<<endl;
		for(int i=1;i<=numa;i++){
			cout<<a[i-1]<<" ";
			cout<<va[a[i-1]]<<" "<<an[a[i-1]]<<endl;
		}*/
	}
	return 0;
}
很明显可以优化，但作者懒得优化（疑似最劣解）。

评论

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

正在加载评论...