牛客网小白月赛6D 字符串丝带

字符串

发布日期: 2018-09-17

文章字数: 470

阅读时长: 2 分

阅读次数:

链接：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
数据量较大，注意使用更快的输入输出方式。

该题可以用桶存储每个字符在当前的出现次数，从头开始，出现的字母的桶加1，然后用这个数打表

代码

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.stream.Stream;
 
public class Main &#123;
 
    static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static void main(String[] args) throws IOException &#123;
         
        int n = getInt();
        int m = getInt();
        int[] z = new int[233];
        String sss = getS();
        int out[] = new int[sss.length() + 1];
        for (int i = 0; i < sss.length(); i++) &#123;
            out[i] = ++z[sss.charAt(i)];
        &#125;
        StringBuilder ss = new StringBuilder();
        while (--m > 0) &#123;
            ss.append(out[getInt()-1]+"\n");
        &#125;
        ss.append(out[getInt()-1]);
        System.out.println(ss);
    &#125;
    static int getInt() throws IOException&#123;
        sc.nextToken();
        return (int)sc.nval;
    &#125;
    static String getS() throws IOException&#123;
        sc.nextToken();
        return sc.sval;
    &#125;
&#125;