真题详解 day29"/>
【蓝桥杯冲刺篇】真题详解 day29
🍔目录
- 🥤饮料换购
- 🍿解题分析
- 🍿参考代码(Java版）
- 🥤密文搜索
- 🍿解题分析
- 🍿参考代码(Java版）
- 🥤蓝桥骑士
- 🍿解题分析
- 🍿参考代码(Java版）
- 🧡写在最后
🥤饮料换购
⛵️题目描述
题目传送门🚀
🍿解题分析
一道很简单的模拟题目，没三个瓶盖能换一瓶新的饮料，意味着新的饮料会带来额外的一个瓶盖。在while循环中模拟喝饮料与置换饮料的过程，直到没有饮料能够置换。
🍿参考代码(Java版）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.HashMap;
import java.util.Map;public class Main {public static class cin {static PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer tokenizer = new StreamTokenizer(reader);static public int nextInt() throws IOException {tokenizer.nextToken();return (int) tokenizer.nval;}static public long nextLong() throws IOException {tokenizer.nextToken();return (long) tokenizer.nval;}static public double nextDouble() throws IOException {tokenizer.nextToken();return tokenizer.nval;}public static String readLine() throws IOException {return reader.readLine();}}public static void main(String[] args) throws IOException {// n 记录剩余饮料数量// red 记录剩余瓶盖数量int n, red, ans;red = ans = 0;n = cin.nextInt();while (n > 0) {ans += n;red += n;n = red / 3;red %= 3;}cin.writer.println(ans);cin.writer.close();}
}
🥤密文搜索
⛵️题目描述
⛵️输入输出案例
输入：
aaaabbbbaabbcccc 2 aaaabbbb abcabccc输出
4
题目传送门🚀
🍿解题分析
本题的核心是理解题意，题目所要求的是给定长度为8的字符串的任意排列在 s 串中的出现次数，出现一定是连续的，因此本题关键点就在连续二字。
⭐️解题关键在于比较
资料串中任意8个连续字符组成的串 str 各个字符的出现次数与8位的密码串字符出现次数是否相同。换句话来说：因为无论如何排列 8 位密码串的各个字符出现次数一定是固定的，因此只需要比较资料串中是否存在长度为 8 的连续子串各个字符出现次数与密码串一致。为了方便比较，选用一个较大的数做字符出现次数哈希，该数一定是要大于 1024 * 1024 的，这里我选择的是1333313,每一个字符的贡献值定义为： 133331 3 ( s [ i ] − ′ a ′ ) 1333313^{(s[i]-'a')} 1333313(s[i]−′a′) ，确保了串中各个字符出现次数一致，哈希值一致。
定义HashMap存储资料串中每一个哈希值出现的次数，随后只需要得到密码串的哈希值与HashMap中存储哈希值作比较，获得出现次数，即是答案所求。
🍿参考代码(Java版）
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.HashMap;
import java.util.Map;public class Main {public static class cin {static PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer tokenizer = new StreamTokenizer(reader);static public int nextInt() throws IOException {tokenizer.nextToken();return (int) tokenizer.nval;}static public long nextLong() throws IOException {tokenizer.nextToken();return (long) tokenizer.nval;}static public double nextDouble() throws IOException {tokenizer.nextToken();return tokenizer.nval;}public static String readLine() throws IOException {return reader.readLine();}}static final int H = 1333313;// 预处理 H 的1-25次方static long[] h = new long[26];static StringBuilder baseStr;static int n;static Map<Long, Integer> usedMap = new HashMap<Long, Integer>();// 获取哈希值static long getHash(String string) {long ret = 0;int len = string.length();for (int i = 0; i < len; ++i) {char c = string.charAt(i);ret += (h[c - 'a']);}return ret;}// 预处理资料串中连续的8位串放入HashMap中static void build() throws IOException {h[0] = 1;for (int i = 1; i <= 25; ++i) {h[i] = h[i - 1] * H;}baseStr = new StringBuilder(cin.readLine());n = cin.nextInt();cin.readLine();long curHash = getHash(baseStr.substring(0, 8));usedMap.put(curHash, 1);int idx = 8;int len = baseStr.length();while (idx < len) {curHash -= (h[baseStr.charAt(idx - 8)-'a']);curHash += (h[baseStr.charAt(idx)-'a']);usedMap.put(curHash, usedMap.getOrDefault(curHash, 0) + 1);++idx;}}public static void main(String[] args) throws IOException {build();int ans = 0;for(int i=0;i<n;++i) {String str = cin.readLine();long hash = getHash(str);if(usedMap.containsKey(hash)) {ans+=usedMap.get(hash);}}cin.writer.println(ans);cin.writer.close();}
}🥤蓝桥骑士
⛵️题目描述
⛵️输入输出案例
输入：
6 1 4 2 2 5 6输出
4
题目传送门🚀
🍿解题分析
最长递增子序列的模板题有两种做法，一种是DP也就是动态规划，第i个元素之前的最小上升子序列的长度无非就是max(dp[i],dp[j]+1),那么另一种做法就是二分查找法，无非就是再新建一个数组，第一个数先放进去，第二个数和第一个数比较，如果说大于第一个数，那么就接在他后面，如果小于第一个数，那么就替换，一般的，如果有i个数，那么每进来一个新的数，都要用二分查找法来得知要替换在哪个位置的数。因为有个for循环，所以是O(N),在加上循环里有个二分查找，所以最后是O(NlogN)的时间复杂度。
🍿参考代码(Java版）
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.StreamTokenizer;
import java.lang.ProcessBuilder.Redirect;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;public class Main {public static class cin {static PrintWriter writer = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer tokenizer = new StreamTokenizer(reader);static public int nextInt() throws IOException {tokenizer.nextToken();return (int) tokenizer.nval;}static public long nextLong() throws IOException {tokenizer.nextToken();return (long) tokenizer.nval;}static public double nextDouble() throws IOException {tokenizer.nextToken();return tokenizer.nval;}public static String readLine() throws IOException {return reader.readLine();}}public static final int N = 30010;public static int[] arr = new int[N];public static int lower_bound(int val) {int l = 0;int r = N;while (l < r) {int m = (l + r) / 2;if (arr[m] < val) {l = m + 1;} else {r = m;}}return l;}public static void main(String[] args) throws IOException {int ans = 0;int n = cin.nextInt();Arrays.fill(arr, Integer.MAX_VALUE);for (int i = 0; i < n; ++i) {int v = cin.nextInt();int idx = lower_bound(v);if (idx == ans) {arr[ans++] = v;} else {arr[idx] = v;}}cin.writer.println(ans);cin.writer.close();}
}
🧡写在最后
今天的题目虽然简单，但都是很重要的知识点，一定要熟练掌握。例如二分查找和模拟题目都是蓝桥杯每年的热门题目，希望大家都能AC。
最后祝愿大家都能取得优异的成绩！
更多推荐
【蓝桥杯冲刺篇】真题详解 day29
发布评论