D 字符串丝带
题目:
链接: https://www.nowcoder.com/acm/contest/136/D
时间限制: C/C++ 1 秒, 其他语言 2 秒
空间限制: C/C++ 65536K, 其他语言 131072K
64bit IO Format: %lld
题目描述
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
备注:
对于 100% 的测试数据:
1 n 1000000
数据量较大, 注意使用更快的输入输出方式.
思路:
一开始直接开了 1e6*26 的二维数组, 然后对于每个字母预处理前缀和, 但是爆内存了, 所以我们可以做一个空间上的优化, 开两个数组, 一个记录当前每个字母的数量, 一个记录当前位置字母的数量, 然后预处理一遍即可.
代码:
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- using namespace std;
- const int maxn = 1e6+20;
- char s[maxn];
- int sum[26];
- int tot[maxn];
- int main()
- {
- int n, m;
- scanf("%d%d",&n,&m);
- scanf("%s",s+1);
- for(int i=1;s[i];i++){
- sum[ s[i]-'a' ]++;
- tot[i] = sum[s[i]-'a'];
- }
- for(int i=1;i<=m;i++){
- int q;
- scanf("%d",&q);
- printf("%d\n",tot[q]);
- }
- return 0;
- }
原始版 (爆内存)
- #include<cstdio>
- #include<algorithm>
- #include<cstring>
- using namespace std;
- const int maxn = 1e6+20;
- char s[maxn];
- int sum[maxn][26];
- int main()
- {
- int n, m;
- scanf("%d%d",&n,&m);
- scanf("%s",s+1);
- for(int i=1;s[i];i++){
- sum[i][ s[i] -'a']++;
- }
- for(int i=1;s[i];i++){
- for(int j=0;j<26;j++){
- sum[i][j]+=sum[i-1][j];
- }
- }
- for(int i=1;i<=m;i++){
- int q;
- scanf("%d",&q);
- printf("%d\n",sum[q][ s[q]-'a' ]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2733623.html