【sorting+暴力】CF624div3 C. Perform the Combo

ゝ一世哀愁。 2024-03-22 14:21 70阅读 0赞

[Problem - C - Codeforces][]

题意：

给定一个字符串s和一个数列a，遍历数列a，每次操作都会给字符串前缀的前ai个的元素出现次数++，问你所有操作过后的字符出现次数

![12e7f3dcfcbf458c8e2060c8ed741700.png][]

思路：

注意到操作前后顺序不会变化，且注意到每次回溯是O(n^2)复杂度，因此考虑将a数组sort一下

排序之后就能用DS维护答案了(有点像莫队？）

然后每次操作就相当于前缀这么多字符次数+=前缀这些字符的出现次数 和 新的字符出现次数++

所以还要维护每个字符出现次数的前缀和

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using namespace std;
    
    const int mxn=2e5+10;
    const int mod=1e9+7;
    
    string s;
    
    int n,m;
    int a[mxn],mp[30],pre[mxn][30];
    
    void solve(){
    	memset(mp,0,sizeof(mp));
    	s.clear();
    	cin>>n>>m>>s;
    	s=" "+s;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=26;j++){
    			pre[i][j]=pre[i-1][j];
    		}
    		pre[i][s[i]-'a'+1]++;
    	}
    	for(int i=1;i<=m;i++) cin>>a[i];
    	sort(a+1,a+1+m);
    	int last=1;
    	for(int i=1;i<=m;i++){
    		for(int j=1;j<=26;j++){
    			if(mp[j]!=0) mp[j]+=pre[a[i-1]][j];
    		}
    		for(int j=last;j<=a[i];j++) mp[s[j]-'a'+1]++;
    		last=a[i]+1;
    	}
    	for(int i=1;i<=n;i++)  mp[s[i]-'a'+1]++;
    	for(int i=1;i<=26;i++) cout<<mp[i]<<" \n"[i==26];
    }
    signed main(){
        ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int __=1;cin>>__;
        while(__--)solve();return 0;
    }

[Problem - C - Codeforces]: https://codeforces.com/contest/1311/problem/C
[12e7f3dcfcbf458c8e2060c8ed741700.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/fee336df79a94698a1de8b048cdfc9ed.png