codeforce D2. RGB Substring (hard version) 滑动窗口

codeforce D2. RGB Substring (hard version) 滑动窗口

D2. RGB Substring (hard version)The only difference between easy and hard versions is the size of the input.You are given a string ss consisting of nn characters, each character is 'R', 'G' or 'B'.You are also given an integer kk. Your task is to change the minimum number of characters in the initial string ss so that after the changes there will be a string of length kk that is a substring of ss, and is also a substring of the infinite string "RGBRGBRGB ...".A string aa is a substring of string bb if there exists a positive integer ii such that a1=bia1=bi, a2=bi+1a2=bi+1, a3=bi+2a3=bi+2, ..., a|a|=bi+|a|−1a|a|=bi+|a|−1. For example, strings "GBRG", "B", "BR" are substrings of the infinite string "RGBRGBRGB ..." while "GR", "RGR" and "GGG" are not.You have to answer qq independent queries.InputThe first line of the input contains one integer qq (1≤q≤2⋅1051≤q≤2⋅105) — the number of queries. Then qq queries follow.The first line of the query contains two integers nn and kk (1≤k≤n≤2⋅1051≤k≤n≤2⋅105) — the length of the string ss and the length of the substring.The second line of the query contains a string ss consisting of nn characters 'R', 'G' and 'B'.It is guaranteed that the sum of nn over all queries does not exceed 2⋅1052⋅105 (∑n≤2⋅105∑n≤2⋅105).OutputFor each query print one integer — the minimum number of characters you need to change in the initial string ss so that after changing there will be a substring of length kk in ss that is also a substring of the infinite string "RGBRGBRGB ...".ExampleinputCopy 3 5 2 BGGGG 5 3 RBRGR 5 5 BBBRR outputCopy 1 0 3 NoteIn the first example, you can change the first character to 'R' and obtain the substring "RG", or change the second character to 'R' and obtain "BR", or change the third, fourth or fifth character to 'B' and obtain "GB".In the second example, the substring is "BRG".来自：​​Problem - 1196D2 - Codeforces​​

翻译(大概)：

你有个长度为 n 的字符串，只有三种字符 R G B, 然后你希望从中截取一段长度为 k 的进行部分字母的修改，让它成为长度为 k 的 RGB 子串，RGB子串就是 RGBRGBRGB....，这样无限循环的字符串中截取的一段。我们希望这个修改的次数尽可能地少，请返回这个最少的修改次数。第一行的输入：q ，代表测试用例的个数，范围是1到2e5每个测试用例第一行：两个数字，n 和 k，n代表字符串长度，k代表截取长度，k小于等于 n， 两者范围 1 到 2e5每个测试用例第二行：一个字符串，代表目前位修改的字符串，所有测试用例的范围和不会超过2e5输入：35 2BGGGG5 3RBRGR5 5BBBRR输出：103说明：RGB的一种长度为2的子串为 BR,它和 BG相差一个字符，所以第一个是 1RGB长度为3的子串有BRG,可和子串 BRG 完全匹配，所以第二个为 2RGB长度为5的子串有RGBRG，和BBBRR相差3个，所以第三个为 3

方法1： 前缀和

1. 使用 dp 数组记录以某个字母结尾的字符串，需要的总的修改次数

2. 减掉倒推回开头的字母对应的修改次数

import java.io.*;import java.util.*;public class Main { public static void main(String[] args) { Reader r = new Reader(); //3 //5 2 //BGGGG //5 3 //RBRGR //5 5 //BBBRR int m = r.nextInt(); for(int a = 0; a < m; a++){ int n = r.nextInt(); int k = r.nextInt(); String s = r.nextLine(); int[][] dp = new int[s.length()+1][3];//RGB for(int i = 0; i < s.length(); i++){ char c = s.charAt(i); dp[i+1][0]= (c=='R'?0:1) +dp[i][2]; dp[i+1][1]= (c=='G'?0:1) +dp[i][0]; dp[i+1][2]= (c=='B'?0:1) +dp[i][1]; } int move = 3-k%3; int ans = k; for(int i = k; i <= s.length(); i++){ ans = Math.min(ans,dp[i][0]-dp[i-k][move%3]); ans = Math.min(ans,dp[i][1]-dp[i-k][(move+1)%3]); ans = Math.min(ans,dp[i][2]-dp[i-k][(move+2)%3]); } System.out.println(ans); } } static class Reader { private BufferedReader br; private StringTokenizer st; Reader() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { try { while (st == null || !st.hasMoreTokens()) { st = new StringTokenizer(br.readLine()); } } catch (IOException e) { e.printStackTrace(); } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } int[] nextIntArray(int n) { int[] arr = new int[n]; for (int i = 0; i < n; i++) arr[i] = nextInt(); return arr; } long nextLong() { return Long.parseLong(next()); } String nextLine() { String s = ""; try { s = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return s; } }}

时间复杂度：O(n)

空间复杂度：O(n)【除去输入】

方法2：滑动窗口

把代码贴出来后，群友说这太麻烦了，用滑动窗口简单多了。思考了5分钟，想到了滑动窗口的写法。

1. 三种字符，只有三种开头的可能性，那就循环3遍都试一下

2. 指定窗口大小为k,到达k个以后，每加一个尾巴，进行累加，减掉一个开头，进行减法

3. 滑动过程计算最优解法

import java.io.*;import java.util.*;public class Main { public static void main(String[] args) { Reader r = new Reader(); //3 //5 2 //BGGGG //5 3 //RBRGR //5 5 //BBBRR int m = r.nextInt(); char[] cs1 = new char[]{'R','G','B'}; char[] cs2 = new char[]{'G','B','R'}; char[] cs3 = new char[]{'B','R','G'}; char[][] cs = new char[][]{cs1,cs2,cs3}; for(int a = 0; a < m; a++){ int n = r.nextInt(); int k = r.nextInt(); String s = r.nextLine(); int ans = k; for(int i = 0; i < 3; i++){ int cnt = 0; for(int j = 0; j < k; j++){ if(cs[i][j%3]!=s.charAt(j)) ++cnt; } ans = Math.min(cnt,ans); for(int j = k; j < n; j++){ if(cs[i][(j-k)%3]!=s.charAt(j-k)) --cnt; if(cs[i][j%3]!=s.charAt(j)) ++cnt; ans = Math.min(cnt,ans); } } System.out.println(ans); } } static class Reader { private BufferedReader br; private StringTokenizer st; Reader() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { try { while (st == null || !st.hasMoreTokens()) { st = new StringTokenizer(br.readLine()); } } catch (IOException e) { e.printStackTrace(); } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } int[] nextIntArray(int n) { int[] arr = new int[n]; for (int i = 0; i < n; i++) arr[i] = nextInt(); return arr; } long nextLong() { return Long.parseLong(next()); } String nextLine() { String s = ""; try { s = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return s; } }}

时间复杂度：O(n)

空间复杂度：O(1)【除了输入】

然后就很困惑了，这个写法简单了这么多，效率怎么没什么提升呢？灵神给了提示：查一查 Java 快读快写。实际上快读已经在用了，快写暂时还没用，试一下，果然快很多。另外，发现用不着罗列三遍RGB的不同写法，使用 i 索引代表偏移量就可以了，加上这两个优化后，时间效率好了很多，如下：

import java.io.*;import java.util.*;public class Main { public static void main(String[] args) { Reader r = new Reader(); //3 //5 2 //BGGGG //5 3 //RBRGR //5 5 //BBBRR PrintWriter out=new PrintWriter(new OutputStreamWriter(System.out)); int m = r.nextInt(); char[] cs1 = new char[]{'R','G','B'}; for(int a = 0; a < m; a++){ int n = r.nextInt(); int k = r.nextInt(); String s = r.nextLine(); int ans = k; for(int i = 0; i < 3; i++){ int cnt = 0; for(int j = 0; j < k; j++){ if(cs1[(j+i)%3]!=s.charAt(j)) ++cnt; } ans = Math.min(cnt,ans); for(int j = k; j < n; j++){ if(cs1[(i+j-k)%3]!=s.charAt(j-k)) --cnt; if(cs1[(i+j)%3]!=s.charAt(j)) ++cnt; ans = Math.min(cnt,ans); } } out.println(ans); out.flush();//输出一次之后要刷新 } } static class Reader { private BufferedReader br; private StringTokenizer st; Reader() { br = new BufferedReader(new InputStreamReader(System.in)); } String next() { try { while (st == null || !st.hasMoreTokens()) { st = new StringTokenizer(br.readLine()); } } catch (IOException e) { e.printStackTrace(); } return st.nextToken(); } int nextInt() { return Integer.parseInt(next()); } int[] nextIntArray(int n) { int[] arr = new int[n]; for (int i = 0; i < n; i++) arr[i] = nextInt(); return arr; } long nextLong() { return Long.parseLong(next()); } String nextLine() { String s = ""; try { s = br.readLine(); } catch (IOException e) { e.printStackTrace(); } return s; } }}

正当我觉得效率已经不错的时候，灵神说了一句：不对啊，我一个 go 都只用跑 200多 怎么你们那么慢的？把 flush放外面试试：

这个代码就不贴了，和前面一样的，唯一的区别就是flush放外面了。很棒啊，今天的茶学到很多呢！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。