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

链接: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 {
 
    static StreamTokenizer sc = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static void main(String[] args) throws IOException {
         
        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;

   转载规则


《牛客网小白月赛6D 字符串丝带》 xfx 采用 知识共享署名 4.0 国际许可协议 进行许可。
 上一篇
poj3278,cow poj3278,cow
题目链接 Catch That CowTime Limit: 2000MS Memory Limit: 65536KTotal Submissions: 120702 Accepted: 37665Descrip
2018-09-18
下一篇 
牛客网练习赛24B凤凰 牛客网练习赛24B凤凰
题目链接 时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 262144K,其他语言524288K64bit IO Format: %lld 题目描述 凤凰于飞,翙翙其羽,亦集爰止。凤凰于飞,翙翙其羽,亦集爰止。
2018-09-16
  目录