Codeforces - 313B - Ilya and Queries

Question

题目大意

就是给你一串字符串 str ， n 个查询，每次查询给你两个数 l 、 r 代表一个区间，问你在 [l，r) 范围内有多少个连续的字符相同。

解析

一开始又看错题目，还以为是求任意一个位置 i ，满足 S_i = S_i+1。。。。

用类似 dp 的思想， dp[i] 记录的是 0~i ( [0,i] ) 之间连续出现的字符数个数。记录了这个数组之后，后面的 m 次查询就每次查询区间 [l, r] 就直接输出 dp[r-1] - dp[l-1] 就可以了。

import java.io.*;
import java.util.StringTokenizer;

public class Main {

    private static class FastReader{
        public BufferedReader br;
        public StringTokenizer st;

        public FastReader(InputStream is){
            br = new BufferedReader(new InputStreamReader(is));
            st = null;
        }

        String next(){
            while(st == null || !st.hasMoreElements()){
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public long nextLong(){
            return Long.parseLong(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
        public String nextLine(){
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

    public static void main(String[] args){
        FastReader fr = new FastReader(new BufferedInputStream(System.in));
        String s = fr.next();
        int n = fr.nextInt();
        int[] dp = new int[s.length()];
        dp[0] = 1;
        for(int i = 1; i < s.length(); i++)
            dp[i] = s.charAt(i) == s.charAt(i-1) ? dp[i-1] + 1 : dp[i-1];
        for(int i = 0; i < n; i++){
            int l = fr.nextInt();
            int r = fr.nextInt();
            System.out.println(dp[r-1] - dp[l-1]);
        }
    }
}

这里使用了 FastReader 类，这是我第一次在 Codeforces 使用 Scanner 会超时（偶尔) 的题目，下面的代码会超时( Scanner 的读入会比 BufferReader 慢很多。

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner cin = new Scanner(new BufferedInputStream(System.in));

        String s = cin.next();
        int n = cin.nextInt();
        int[] dp = new int[s.length()];
        dp[0] = 1;
        for(int i = 1; i < s.length(); i++)
           dp[i] = s.charAt(i) == s.charAt(i-1) ? dp[i-1] + 1 : dp[i-1];

        for(int i = 0; i < n; i++){
            int l = cin.nextInt();
            int r = cin.nextInt();
            System.out.println(dp[r-1] - dp[l-1]);
        }
    }
}