20180818牛客小白月赛6.D

本文主要是介绍20180818牛客小白月赛6.D，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意

WHZ送给了HtBest一个“字符串丝带”，这条丝带由n个小写字母按照一定的顺序排列组成，HtBest收到新礼物后有许多问题，类似“第i个位置的字母在前i个位置中出现了几次？”，HtBest很希望知道答案，于是求助你帮忙解答。
输入描述:
第一行有2个正整数n，m,分别表示丝带长度和问题个数。第二行，有n个小写字母，第i个表示丝带第i位的小写字母。接下来有m行，每行一个正整数，表示HtBest的一个问题。
输出描述:
共m行，对于每个问题，给出答案。
示例1
输入
3 3
abc
1
2
3
输出
1
1
1

示例2
输入
4 4
abba
1
2
3
4
输出
1
1
2
2

示例3
输入
7 7
yyuahhy
7
6
5
4
3
2
1
输出
3
2
1
1
1
2
1

分析

这道题的内存挺坑人的，竟然是64mb，我开了一个26*1000000的int数组，导致我第一次直接mle，然后将int换为short int，过了90%，嗯。再仔细看题，发现是第i个位置的的字符出现次数，所以，我们可开一个26数组，记录到目前为止这个字母出现了多少次，当遇到一个字母时，相对应的数组++，将这个位置的值记录为数组的值，这样就直接AC了。
上代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int al[27],num[1000010],n,m,q;
char ch[1000010];
int main(){memset(al,0,sizeof(al));scanf("%d%d",&n,&m);scanf("%s",ch+1);for(int i=1;i<=n;i++)al[ch[i]-'a']++,num[i]=al[ch[i]-'a'];while(m--){scanf("%d",&q);printf("%d\n",num[q]);}return 0;
}