Perform the Combo（思维）

本文主要是介绍Perform the Combo（思维），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

VJ链接

题意：

长度为n的字符串组合，（仅有：a~z）长度为m的数集a，表示共按错了m次。按完第ai个按钮后，再从头开始。问所有字母被按了几次。

思路：

对b数组排序，优化重复计算的部分即可。
例：

10 5
codeforces 存入字符数组a
2 8 3 2 9 存入整形数组b

对b中m个数进行排序得：2 2 3 8 9
所以：

这样就可以省下重复计算的次数，注意，从b[0]=0开始，i 取[0~m-1]

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 200010
using namespace std;
int b[N],s[30],n;
char a[N];
int main()
{int t,m;scanf("%d",&t);while(t--){memset(s,0,sizeof(s));scanf("%d%d%s",&n,&m,a+1);for(int i=1;i<=m;i++)scanf("%d",&b[i]);sort(b+1,b+1+m);b[0]=0;for(int i=0;i<m;i++)for(int j=b[i]+1;j<=b[i+1];j++)s[a[j]-'a']+=(m-i); //重复的直接加m-i次for(int i=1;i<=n;i++)s[a[i]-'a']++; //正确按一遍组合字母增加的次数for(int i=0;i<26;i++){if(i) printf(" ");printf("%d",s[i]);}printf("\n");}return 0;
}

这篇关于Perform the Combo（思维）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---