搜索到
9
篇与
的结果
-
蓝桥杯|历届真题:完全二叉树的权值 1.题目问题描述 给定一棵包含 N 个节点的完全二叉树，树上每个节点都有一个权值，按从 上到下、从左到右的顺序依次是 A1, A2, · · · AN，如下图所示： 现在小明要把相同深度的节点的权值加在一起，他想知道哪个深度的节点 权值之和最大？如果有多个深度的权值和同为最大，请你输出其中最小的深度。 注：根的深度是 1。输入格式 第一行包含一个整数 N。 第二行包含 N 个整数 A1, A2, · · · AN 。输出格式 输出一个整数代表答案。样例输入7 1 6 5 4 3 2 1样例输出2评测用例规模与约定对于所有评测用例，1 ≤ N≤ 100000，−100000 ≤ Ai ≤ 100000。2. 题解2.1 思路分析1.根据节点数量N求解二叉树的高度 完全二叉树为满二叉树或者除去最后一层为满二叉树。 高度为H的满二叉树的节点数量为2^H-1。(根节点记为第1层) 根据这一条件即可求出N个节点对应的完全二叉树的高度treeHeight 2.求解完全二叉树最后一层节点的数量 最后一层节点的数量为N-Math.pow(2,treeHeight-1)+1 3.按层输入每层节点的权值并计算每层的权值和2.2 代码实现import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { int N = scanner.nextInt(); // 求解完全二叉树高度 int treeHeight = 0; int count = 1; while (count<N+1){ count*=2; treeHeight++; } // 记录每层的权值和 int[] weightSumArr = new int[treeHeight+1]; Arrays.fill(weightSumArr,0); // 输入并求权值和 for (int i = 1; i <treeHeight; i++) { for (int j = 0; j < Math.pow(2,i-1); j++) { weightSumArr[i] += scanner.nextInt(); } } for (int i = 0; i < N-Math.pow(2,treeHeight-1)+1; i++) {//最后一层需要单独处理 weightSumArr[treeHeight] += scanner.nextInt(); } int maxWeightHeight = 1; for (int i = 2; i <= treeHeight; i++) { if(weightSumArr[i]>weightSumArr[maxWeightHeight]){ maxWeightHeight = i; } } System.out.println(maxWeightHeight); } }2.3 提交结果评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.0078ms22.48MB输入 输出2正确10.0062ms22.47MBVIP特权3正确10.0078ms22.51MBVIP特权4正确10.0093ms22.58MBVIP特权5正确10.0093ms25.16MBVIP特权6正确10.00187ms34.37MBVIP特权7正确10.00375ms91.69MBVIP特权8正确10.00390ms91.57MBVIP特权9正确10.00359ms90.37MBVIP特权10正确10.00406ms92.12MBVIP特权参考资料http://lx.lanqiao.cn/problem.page?gpid=T2695 -
蓝桥杯|历届真题:作物杂交 1.题目【问题描述】作物杂交是作物栽培中重要的一步。已知有$N$种作物（编号$1$至$N$），第$i$种作物从播种到成熟的时间为$T_i$。作物之间两两可以进行杂交，杂交时间取两种中时间较长的一方。如作物$A$种植时间为5天，作物$B$种植时间为7天，则$AB$杂交花费的时间为7天。作物杂交会产生固定的作物，新产生的作物仍然属于N种作物中的一种。初始时，拥有其中$M$种作物的种子（数量无限，可以支持多次杂交）。同时可以进行多个杂交过程。求问对于给定的目标种子，最少需要多少天能够得到。如存在4种作物$ABCD$，各自的成熟时间为5天、7天、3天、8天。初始拥有AB两种作物的种子，目标种子为$D$，已知杂交情况为$A \times B→C，A \times C→D$。则最短的杂交过程为：第1天到第7天（作物B的时间），$A \times B→C$。第8天到第12天（作物A的时间），$A \ times C→D$。花费12天得到作物D的种子。【输入格式】输入的第1行包含4个整数$N，M，K，T，N$表示作物种类总数（编号1至$N$），$M$表示初始拥有的作物种子类型数量，$K$表示可以杂交的方案数，$T$表示目标种子的编号。第2行包含$N$个整数，其中第i个整数表示第i种作物的种植时间T；（$1 \leq T_i \leq 100$）第3行包含$M$个整数，分别表示已拥有的种子类型$K_j( 1 \leq K_j \leq M)$，$K_j$两两不同。第4至$K+3$行，每行包含3个整数$A，B，C$，表示第$A$类作物和第$B$类作物杂交可以获得第$C$类作物的种子。【输出格式】输出一个整数，表示得到目标种子的最短杂交时间。【样例输入】6 2 4 6 5 3 4 6 4 9 1 2 1 2 3 1 3 4 2 3 5 4 5 6【样例输出】16【样例说明】第1天至第5天，将编号1与编号2的作物杂交，得到编号3的作物种第6天至第10天，将编号1与编号3的作物杂交，得到编号4的作物种第6天至第9天，将编号2与编号3的作物杂交，得到编号5的作物种第11天至第16天，将编号4与编号5的作物杂交，得到编号6的作物种总共花费16天【评测用例规模与约定】对于所有评测用例，$1 \leq N \leq 2000,2 \leq M \leq N，1 \leq K \leq 100000,1 \leq T \leq N$，保证目标种子一定可以通过杂交得到。2. 题解2.1 思路分析思路1：暴力求解 设置一个数字minGetTime用于保存每类种子的最小获取时间 循环遍历杂交方案： minGetTime[C] = min(minGetTime[C],maxAB获取时间+maxAB成熟数据) 直至数组minGetTime收敛(不再有任何位置发生变化)2.2 代码实现import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); // 判断minGetTime数组是否收敛|是否存在某位发生修改 无则返回true public static boolean isNoChange(boolean[] changeFlag){ boolean res = true; for (int i = 0; i < changeFlag.length; i++) { res = res&changeFlag[i]; } return res; } public static void main(String[] args) { int N = scanner.nextInt(); // 作物种类数 int M = scanner.nextInt(); // 初始时候拥有的种子数量 int K = scanner.nextInt(); // 可以杂交的方案数量 int T = scanner.nextInt(); // 目的种子编号 int[] timeSpendArr = new int[N];// 作物成熟时间 for (int i = 0; i < N; i++) { timeSpendArr[i] = scanner.nextInt(); } int[] startSeedArr = new int[M]; //初始拥有的种子 for (int i = 0; i < M; i++) { startSeedArr[i] = scanner.nextInt(); } int[][] methodArr = new int[K][3]; //杂交方案数 for (int i = 0; i < K; i++) { for (int j = 0; j < 3; j++) { methodArr[i][j] = scanner.nextInt(); } } int[] minGetTime = new int[N];//最小获取时间 // 初始化最小获取时间 for (int i = 0; i < N; i++) { minGetTime[i] = Integer.MAX_VALUE; } for (int i = 0; i < M; i++) { minGetTime[startSeedArr[i]-1] = 0; } boolean[] changeFlag = new boolean[K];//用于判断本轮处理杂交方案是否导致了最小时间发生修改|判断收敛 Arrays.fill(changeFlag,false); while (!isNoChange(changeFlag)){//知道未发生修改位置 Arrays.fill(changeFlag,true); for (int i = 0; i < K; i++) { int seedA = methodArr[i][0]-1; int seedB = methodArr[i][1]-1; if(minGetTime[seedA]==Integer.MAX_VALUE||minGetTime[seedB]==Integer.MAX_VALUE)continue; int newSeed = methodArr[i][2]-1;//新品种 int minGetTimeOfNewSeed = Math.min(minGetTime[newSeed],Math.max(minGetTime[seedA],minGetTime[seedB])+Math.max(timeSpendArr[seedA],timeSpendArr[seedB])); if(minGetTimeOfNewSeed!=minGetTime[newSeed]){ changeFlag[i] = false; minGetTime[newSeed] = minGetTimeOfNewSeed; } } } System.out.println(minGetTime[T-1]); } }2.3 提交结果评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.00125ms25.54MB输入 输出2正确10.00109ms25.46MBVIP特权3正确10.00468ms75.14MBVIP特权4正确10.00406ms68.42MBVIP特权5正确10.00390ms77.67MBVIP特权6正确10.00296ms54.73MBVIP特权7正确10.00500ms99.37MBVIP特权8正确10.00453ms98.50MBVIP特权9正确10.00578ms97.82MBVIP特权10正确10.00500ms98.80MBVIP特权参考资料http://lx.lanqiao.cn/problem.page?gpid=T2859
-
蓝桥杯|历届真题:修改数组 1.题目【问题描述】给定一个长度为N的数组$A=[A_1,A_2,\dots,A_N]$，数组中有可能有重复出现的整数。现在小明要按以下方法将其修改为没有重复整数的数组。小明会依次修改$A_2,A_3,\dots,A_N$当修改$A_i$；时，小明会检查$A_i$是否在$A_1 \rightarrow A_{i-1}$中出现过。如果出现过，则小明会给$A_i$加上$1$；如果新的$A_i$仍在之前出现过，小明会持续给$A_i$加上1直到$A_i$没有在$A_1 \rightarrow A_{i-1}$中出现过。当$A_n$也经过上述修改之后，显然A数组中就没有重复的整数了。现在给定初始的A数组，请你计算出最终的A数组。【输入格式】第一行包含一个整数$N$。第二行包含N个整数$A_1,A_2,\dots,A_N$【输出格式】输出N个整数，依次是最终的$A_1,A_2,\dots,A_N$【样例输入】5 2 1 1 3 4【样例输出】2 1 3 4 5【评测用例规模与约定】对于80%的评测用例，$1 \leq N \leq 10000$。对于所有评测用例，$1 \leq N \leq 100000,1 \leq A_i \leq 1000000$。2. 题解2.1 思路分析思路1：暴力求解(80分) 用一个set保存已遍历过的数字，当遍历到新的位置时，如果再set里则一直++，再将其加入回set 思路2：并查集 维护并查集并通过查操作直接找到A_i2.2 代码实现思路1：暴力求解// 暴力求解 80分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { int N = scanner.nextInt(); int[] arr = new int[N]; for (int i = 0; i < N; i++) { arr[i] = scanner.nextInt(); } Set<Integer> set = new HashSet<>(); for (int i = 0; i < N; i++) { while (set.contains(arr[i])){ arr[i]++; } set.add(arr[i]); } for (int i = 0; i < N-1; i++) { System.out.print(arr[i]+" "); } System.out.println(arr[N-1]); } }思路2：并查集// 并查集 80分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); static int[] find = new int[1000001]; // 查操作 找到x的真正祖先 public static int findRoot(int x){ return x==find[x]?x:findRoot(find[x]); } public static void main(String[] args) { int N = scanner.nextInt(); int[] arr = new int[N]; // 初始化find数组(用于查找祖先) for (int i = 0; i < find.length; i++) { find[i] = i; } for (int i = 0; i < N; i++) { arr[i] = scanner.nextInt(); int root = findRoot(arr[i]); //找到目标A_{i-1} arr[i] = root; find[root] = findRoot(root+1);// 并操作 用并查集维护大小关系 } for (int i = 0; i < N-1; i++) { System.out.print(arr[i]+" "); } System.out.println(arr[N-1]); } }// 并查集+路径压缩 100分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); static int[] find = new int[1000100]; // 查操作 找到x的真正祖先 增加路径压缩降低耗时 public static int findRoot(int x){ if(x==find[x]){ return x; }else { find[x] = findRoot(find[x]); return find[x]; } } public static void main(String[] args) { int N = scanner.nextInt(); int[] arr = new int[N]; // 初始化find数组(用于查找祖先) for (int i = 0; i < find.length; i++) { find[i] = i; } for (int i = 0; i < N; i++) { arr[i] = scanner.nextInt(); int root = findRoot(arr[i]); //找到目标A_{i-1} arr[i] = root; find[root] = findRoot(root+1);// 并操作 用并查集维护大小关系 } for (int i = 0; i < N-1; i++) { System.out.print(arr[i]+" "); } System.out.println(arr[N-1]); } }2.3 提交结果思路1：暴力求解评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.00125ms22.51MB输入 输出2正确10.0093ms22.47MBVIP特权3正确10.0093ms22.62MBVIP特权4正确10.00125ms31.51MBVIP特权5正确10.00656ms158.1MBVIP特权6正确10.00484ms149.7MBVIP特权7正确10.00765ms242.9MBVIP特权8正确10.00531ms156.5MBVIP特权9运行超时0.00运行超时287.7MBVIP特权10运行超时0.00运行超时287.8MBVIP特权思路2：并查集评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.00125ms26.23MB输入 输出2正确10.00125ms26.23MBVIP特权3正确10.0078ms26.39MBVIP特权4正确10.00156ms30.05MBVIP特权5正确10.00296ms40.35MBVIP特权6正确10.00296ms42.53MBVIP特权7正确10.00328ms40.65MBVIP特权8正确10.00281ms40.58MBVIP特权9正确10.00609ms96.44MBVIP特权10正确10.00484ms97.01MBVIP特权参考资料http://lx.lanqiao.cn/problem.page?gpid=T2856图论——并查集(详细版)蓝桥杯 -2019年第十届真题 修改数组 暴力|并查集
-
蓝桥杯|历届真题:回文日期 1.题目【问题描述】2020年春节期间，有一个特殊的日期引起了大家的注意：2020年2月2日。因为如果将这个日期按"yyyymmdd”的格式写成一个8位数是20200202，恰好是一个回文数。我们称这样的日期是回文日期。有人表示20200202是“千年一遇”的特殊日子。对此小明很不认同，因为不到2年之后就是下一个回文日期：20211202即2021年12月2日。也有人表示20200202并不仅仅是一个回文日期，还是一个ABABBABA型的回文日期。对此小明也不认同，因为大约100年后就能遇到下一个ABABBABA 型的回文日期：21211212 即2121年12月12日。算不上“千年一遇”，顶多算“千年两遇”。给定一个8位数的日期，请你计算该日期之后下一个回文日期和下一个ABABBABA型的回文日期各是哪一天。【输入格式】输入包含一个八位整数N，表示日期。【输出格式】输出两行，每行1个八位数。第一行表示下一个回文日期，第二行表示下一个ABABBABA型的回文日期。【样例输入】20200202【样例输出】20211202 21211212【评测用例规模与约定】对于所有评测用例，$10000101 \leq N \leq 89991231$，保证N是一个合法日期的8位数表示。2. 题解2.1 思路分析本题需要求解下一个ABCDDCBA型的日期和下一个ABABBABA型的日期 只需先完成nextABCDDCBADate的求解并再此基础上增加ABCD-->ABAB的限制条件即可 nextABCDDCBADate(date)的求解包含内容： 1.date年月日拆解 2.4位数字反转 ABCD-->DCBA 为了降低时间复杂度，只对年进行遍历，月日根据ABCD-->DCBA生成 3.有效日期判断(年月日分别进行判断) 包含闰年判断 4.判断新的日期是否再当前日期之后2.2 代码实现import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); static int[] maxDayOfMonthList = {31,28,31,30,31,30,31,31,30,31,30,31}; // 判断闰年 public static boolean isUniqueYear(int year){ return (year%4==0&&year%100!=0)||year%400==0; } // 判断day是否有效 public static boolean isValidDay(int year,int month,int day){ // 求该月最大天数 int maxDayOfMonth = maxDayOfMonthList[month-1]; if(isUniqueYear(year)&&month==2){ maxDayOfMonth = 29; } return !(day==0||day>maxDayOfMonth); } // 判断month是否有效 public static boolean isValidMonth(int month){ return month>0&&month<13; } // 4位数字反转 ABCD-->DCBA public static int reverse4BitInt(int num){ // 从低位到高位进行分解 int bit1 = num%10; int bit2 = (num%100)/10; int bit3 = (num/100)%10; int bit4 = num/1000; return bit1*1000+bit2*100+bit3*10+bit4; } // 寻找下一个回文/ABCDDCBA日期 public static int nextABCDDCBADate(int date){ int year = date / 10000; int ABCDDCBADate = date; for (int i = year; i < 10000; i++) { int tmp_year = i; int tmp_year_reverse = reverse4BitInt(tmp_year); int tmp_day = tmp_year_reverse%100; int tmp_month = tmp_year_reverse/100; int tmp_date = tmp_year*10000+tmp_month*100+tmp_day; if (isValidMonth(tmp_month) && isValidDay(tmp_year, tmp_month, tmp_day)&&tmp_date>date){//有效日期+日期更后 ABCDDCBADate = tmp_date; break; } } return ABCDDCBADate; } // 寻找下一个符合ABABBABA的日期 public static int nextABABBABADate(int date) { int ABABBABA = nextABCDDCBADate(date); int month = (ABABBABA % 10000) / 100; int day = ABABBABA % 100; while (month!=day){ ABABBABA = nextABCDDCBADate(ABABBABA); month = (ABABBABA % 10000) / 100; day = ABABBABA % 100; } return ABABBABA; } public static void main(String[] args) { int date= scanner.nextInt(); System.out.println(nextABCDDCBADate(date)); System.out.println(nextABABBABADate(date)); } }2.3 提交结果评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.00125ms22.52MB输入 输出2正确10.0078ms22.48MBVIP特权3正确10.00109ms22.49MBVIP特权4正确10.0062ms22.44MBVIP特权5正确10.00109ms22.44MBVIP特权6正确10.0093ms22.47MBVIP特权7正确10.0046ms22.50MBVIP特权8正确10.0093ms22.48MBVIP特权9正确10.0078ms22.51MBVIP特权10正确10.0078ms22.48MBVIP特权参考资料http://lx.lanqiao.cn/problem.page?gpid=T2856
-
蓝桥杯|历届真题:子串分值和 1.题目【问题描述】对于一个字符串$S$，我们定义S的分值$f(S)$为$S$中恰好出现一次的字符个数。例如$f(aba)=1，f(abc)=3，f(aaa) = 0$。现在给定一个字符串$S[0..n-1]$（长度为n），请你计算对于所有S的非空子串$S[i..j]（0 \leq i \leq j \lt n）$，$f(S[i..j])$的和是多少。【输入格式】输入一行包含一个由小写字母组成的字符串S。【输出格式】输出一个整数表示答案。【样例输入】ababc【样例输出】21【样例说明】子串,f值 a,1 ab,2 aba,1 abab,0 ababc,1 b,1 ba,2 bab,1 babc,2 a,1 ab,2 abc,3 b,1 bc,2 c,1【评测用例规模与约定】对于20%的评测用例， $1 \leq n \leq 10$；对于40%的评测用例， $1 \leq n \leq 100$；对于50%的评测用例， $1 \leq n \leq 1000$；对于60%的评测用例， $1 \leq n \leq 10000$；对于所有评测用例， $1 \leq n \leq 100000$；2. 题解2.1 思路分析思路1：暴力求解(50分) 首先需要写一个计算子串得分的函数 1.统计各个字符出现的次数 2.得到只出现一次的字符数 然后遍历所有的子串并对其得分进行求和 思路2：动态规划(50分) 考虑子串之间的关系,即新增一个字符对子串得分的影响,从避免重复统计字符出现次数导致耗时 思路3:考虑每个位置的字符只出现一次的子串总数(100分) 用 pre[i] 记录第 i 位置上的字母上一次出现的位置，用 next[i] 记录第 i 位置上的字母下一次出现的位置； 那么往左最多能延伸到 pre[i] + 1，其到第 i 个字母一共有 i - pre[i] 个字母； 同理往右最多能延伸到 next[i] - 1，其到第 i 个字母一共有 next[i] - i 个字母； 二者相乘，就是该 i 位置上的字符只出现一次的子串总数 具体可以结合上述输入输出例子思考。2.2 代码实现思路1：暴力求解import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static int getScore(String str){ int score = 0; char[] strChars = str.toCharArray(); int[] charCounter = new int[26]; for (int i = 0; i < 26; i++)charCounter[i]=0; for (int i = 0; i < strChars.length; i++) { charCounter[(int)(strChars[i]-'a')]++; } for (int i = 0; i <26 ; i++) { if(charCounter[i]==1)score++; } return score; } public static void main(String[] args) { String str = scanner.next(); char[] strChars = str.toCharArray(); int scoreSum = 0; for (int i = 0; i < strChars.length; i++) { StringBuilder sb = new StringBuilder(); for (int j = i; j < strChars.length; j++) { sb.append(strChars[j]); scoreSum+=getScore(sb.toString()); } } System.out.println(scoreSum); } }// 简化子串得分求解 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { String str = scanner.next(); int len = str.length(); char[] strChars = str.toCharArray(); int scoreSum = 0; for (int i = 0; i < strChars.length; i++) { Set<Character> set1 = new HashSet<>(); //统计所有字符串 Set<Character> set2 = new HashSet<>();//统计不止出现一次的字符串 for (int j = i; j < strChars.length; j++) { if(set1.contains(strChars[j])){ set2.add(strChars[j]); } set1.add(strChars[j]); scoreSum+= set1.size()-set2.size(); } } System.out.println(scoreSum); } }思路2：动态规划// 40分 会爆内存 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { String str = scanner.next(); char[] strChars = str.toCharArray(); int[][] dp = new int[str.length()][str.length()]; int scoreSum = 0; for (int i = 0; i < str.length(); i++) { for (int j = 0; j < str.length();j++) { if(j<i){ dp[i][j] = 0; }else if(j==i){ dp[i][j] = 1; }else { int startIndex = str.substring(i,j).indexOf(strChars[j]); if(startIndex!=-1){//旧的子包含待加入字符 int endIndex = str.substring(i,j).lastIndexOf(strChars[j]); if(startIndex==endIndex){//旧的子串只包含1个待加入字符 dp[i][j]=dp[i][j-1]-1; }else {//旧的子串包含多个个待加入字符，之前已进行了-1操作，无需再减 dp[i][j]=dp[i][j-1]; } }else {//旧的子不包含待加入字符 dp[i][j]=dp[i][j-1]+1; } } scoreSum += dp[i][j]; } } System.out.println(scoreSum); } }// dp优化 避免爆内存 还是50分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { String str = scanner.next(); int len = str.length(); char[] strChars = str.toCharArray(); int lastDpstate = 0; int scoreSum = 0; for (int i = 0; i < len; i++) { for (int j = 0; j < len;j++) { if(j<i){ lastDpstate=0; }else if(j==i){ lastDpstate = 1; }else { int startIndex = str.substring(i,j).indexOf(strChars[j]); if(startIndex!=-1){//旧的子串包含待加入字符 int endIndex = str.substring(i,j).lastIndexOf(strChars[j]); if(startIndex==endIndex){//旧的子串只包含1个待加入字符 lastDpstate=lastDpstate-1; } }else { lastDpstate=lastDpstate+1; } } scoreSum += lastDpstate; } } System.out.println(scoreSum); } }思路3：考虑每个位置的字符只出现一次的子串总数// 60分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { String str = scanner.next(); char[] strChars = str.toCharArray(); int scoreSum = 0; for (int i = 0; i < strChars.length; i++) { int nextIndex = str.substring(i+1).indexOf(strChars[i]); //下一个strChars[i]字符的位置 nextIndex = nextIndex==-1? strChars.length : nextIndex+i+1; int preIndex = str.substring(0,i).lastIndexOf(strChars[i]);////前一个strChars[i]字符的位置 scoreSum += (nextIndex-i)*(i-preIndex); } System.out.println(scoreSum); } }// 优化 100分 import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { String str = scanner.next(); char[] strChars = str.toCharArray(); int len = strChars.length; int scoreSum = 0; int[] pre = new int[len]; int[] next = new int[len]; Arrays.fill(pre,-1); Arrays.fill(next,len); // 求解next[i] for (int i = 0; i < len; i++) { for (int j = i+1; j < len; j++) { if(strChars[i]==strChars[j]){ next[i]=j; break; } } } // 求解pre[i] for (int i = 0; i < len; i++) { for (int j = i-1; j>=0; j--) { if(strChars[i]==strChars[j]){ pre[i]=j; break; } } } // 计算得分和 for (int i = 0; i < len; i++) { scoreSum += (next[i]-i)*(i-pre[i]); } System.out.println(scoreSum); } }2.3 提交结果思路1：暴力求解评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.0078ms22.17MB输入 输出2正确10.00109ms22.19MBVIP特权3正确10.00109ms22.19MBVIP特权4正确10.0093ms24.36MBVIP特权5正确10.00359ms233.1MBVIP特权6运行超时0.00运行超时281.0MBVIP特权7运行超时0.00运行超时283.3MBVIP特权8运行超时0.00运行超时435.0MBVIP特权9运行超时0.00运行超时282.5MBVIP特权10运行超时0.00运行超时282.6MBVIP特权思路2：动态规划评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.0078ms22.17MB输入 输出2正确10.00109ms22.19MBVIP特权3正确10.00109ms22.19MBVIP特权4正确10.0093ms24.36MBVIP特权5正确10.00359ms233.1MBVIP特权6运行超时0.00运行超时281.0MBVIP特权7运行超时0.00运行超时283.3MBVIP特权8运行超时0.00运行超时435.0MBVIP特权9运行超时0.00运行超时282.5MBVIP特权10运行超时0.00运行超时282.6MBVIP特权思路3：考虑每个位置的字符只出现一次的子串总数评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.00109ms22.40MB输入 输出2正确10.0046ms22.40MBVIP特权3正确10.0078ms22.41MBVIP特权4正确10.0093ms22.39MBVIP特权5正确10.0078ms22.44MBVIP特权6正确10.00125ms23.34MBVIP特权7正确10.00125ms26.62MBVIP特权8正确10.00140ms26.70MBVIP特权9正确10.00109ms26.51MBVIP特权10正确10.00171ms26.66MBVIP特权参考资料http://lx.lanqiao.cn/problem.page?gpid=T2858蓝桥杯试题 历届试题 子串分值和
-
蓝桥杯|历届真题:重复字符串 1.题目【问题描述】如果一个字符串S恰好可以由某个字符串重复K次得到，我们就称S是K次重复字符串。例如"abcabcabc”可以看作是"abc”重复3次得到，所以"abcabcabc”是3次重复字符串。同理"aaaaaa"既是2次重复字符串、又是3次重复字符串和6次重复字符串。现在给定一个字符串S，请你计算最少要修改其中几个字符，可以使S变为一个K次字符串？【输入格式】输入第一行包含一个整数K。第二行包含一个只含小写字母的字符串S。【输出格式】输出一个整数代表答案。如果S无法修改成K次重复字符串，输出-1。【样例输入】2 aabbaa【样例输出】2【评测用例规模与约定】对于所有评测用例，$1 \leq K \leq 100000，1 \leq |S| \leq 100000$。其中$|S|$表示$S$的长度。2. 题解2.1 思路分析先判断字符串长度是否是K的整数倍，不是则输出-1 若是，则将字符串分为K组，对每组的第i位统计得到各字符出现次数的最大值maxAppear 则要想将该字符串变为重复字符串在第i位上需要修改的最少的次数为K-maxAppear 对每一位需要做的最小修改进行求和即可得到最终的结果2.2 代码实现import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); public static void main(String[] args) { int K = scanner.nextInt(); String str = scanner.next(); int len = str.length(); char[] strChars = str.toCharArray(); if(len%K!=0){ System.out.println(-1); }else { int minChange = 0; int groupLen = len/K; for (int i = 0; i < groupLen; i++) {//将字符串分成K组 // 统计每组字符串第j位的哪个字符出现的次数最多得到次数 int maxAppear = 0; int[] charCounter = new int[26]; for (int j = 0; j < 26; j++) { charCounter[j]=0; } for (int j = 0; j < K; j++) { int tmpIndex = (int)(strChars[j*groupLen+i]-'a'); charCounter[tmpIndex] += 1; } for (int j = 0; j < 26; j++) { maxAppear = Math.max(maxAppear,charCounter[j]); } minChange += (K-maxAppear); } System.out.println(minChange); } } }2.3 提交结果1正确10.0062ms22.22MB输入 输出2正确10.0093ms22.30MBVIP特权3正确10.00109ms22.30MBVIP特权4正确10.0093ms22.26MBVIP特权5正确10.00109ms22.23MBVIP特权6正确10.0078ms22.29MBVIP特权7正确10.00140ms22.99MBVIP特权8正确10.00171ms25.62MBVIP特权9正确10.00125ms25.64MBVIP特权10错误0.00125ms24.57MBVIP特权暂未看出错在哪了参考资料http://lx.lanqiao.cn/problem.page?gpid=T2890
-
-
蓝桥杯|历届真题:砝码称重 1.题目【问题描述】你有一架天平和 $N$个砝码，这 $N$个砝码重量依次是 $W_1, W_2, · · · , W_N$。 请你计算一共可以称出多少种不同的重量？ 注意砝码可以放在天平两边。【输入格式】输入的第一行包含一个整数 $N$。第二行包含 $N$个整数：$W_1, W_2, · · · , W_N$。【输出格式】输出一个整数代表答案。【样例输入】3 1 4 6【样例输出】10【样例说明】能称出的 10 种重量是：1、2、3、4、5、6、7、9、10、11。 1 = 1； 2 = 6 − 4 (天平一边放 6，另一边放 4)； 3 = 4 − 1； 4 = 4； 5 = 6 − 1； 6 = 6； 7 = 1 + 6； 9 = 4 + 6 − 1； 10 = 4 + 6； 11 = 1 + 4 + 6。2. 题解2.1 思路分析增加一个砝码会增加的新的称重组合为 1.原来的各种称重组合+该砝码的重量 2.原来的各种称重组合-该砝码的重量(0除外) 3.该砝码本身的重量 当只有一个砝码的时候称重组合为该砝码本身的重量 由此形成了动态规划链2.2 代码实现import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] weights = new int[n]; for (int i = 0; i < n; i++) { weights[i] = scanner.nextInt(); } Set<Integer> set = new HashSet<>();//用来存储最终可能的组合，set可以自动去重 set.add(weights[0]); for (int i = 1; i < n; i++) { List<Integer> tmpList = new ArrayList<>(set); for(Integer item:tmpList){ if(item!=weights[i]){//避免出现称出0的情况 set.add(Math.abs(item-weights[i])); } set.add(item+weights[i]); } set.add(weights[i]); } System.out.println(set.size()); } }2.3 提交结果评测点序号评测结果得分CPU使用内存使用下载评测数据1正确10.0078ms22.23MB输入 输出2正确10.00109ms22.33MBVIP特权3正确10.0078ms22.32MBVIP特权4正确10.00140ms22.33MBVIP特权5正确10.0062ms22.68MBVIP特权6正确10.00109ms23.85MBVIP特权7正确10.0078ms26.24MBVIP特权8正确10.00171ms33.07MBVIP特权9正确10.00218ms64.09MBVIP特权10正确10.00234ms90.59MBVIP特权参考资料蓝桥杯试题 历届真题 砝码称重【第十二届】【省赛】【JAVAB组】http://lx.lanqiao.cn/problem.page?gpid=T2895
-
蓝桥杯|历届真题:异或数列 1.题目【问题描述】Alice 和 Bob 正在玩一个异或数列的游戏。初始时，Alice 和 Bob 分别有一个整数$a$和$b$，有一个给定的长度为 $n$ 的公共数列 $X_1,X_2, \dots, X_{n_i}$ 。Alice 和 Bob 轮流操作，Alice 先手，每步可以在以下两种选项中选一种：选项 1：从数列中选一个 $Xi$ 给 Alice 的数异或上，或者说令 $a$ 变为 $a ⊕ Xi$。（其中 $⊕$ 表示按位异或）选项 2：从数列中选一个$Xi$ 给 Bob 的数异或上，或者说令 $b$变为$ b ⊕ Xi$。每个数 $X_i$ 都只能用一次，当所有 $Xi$ 均被使用后（$n$ 轮后）游戏结束。游戏结束时，拥有的数比较大的一方获胜，如果双方数值相同，即为平手。现在双方都足够聪明，都采用最优策略，请问谁能获胜？【输入格式】每个评测用例包含多组询问。询问之间彼此独立。输入的第一行包含一个整数 $T$，表示询问数。接下来 $T$ 行每行包含一组询问。其中第 i 行的第一个整数 $n_i$ 表示数列长度，随后 $n_i$个整数 $X_1,X_2, \dots, X_{n_i}$ 表示数列中的每个数。【输出格式】输出 $T$ 行，依次对应每组询问的答案。每行包含一个整数 1、0 或 −1 分别表示 Alice 胜、平局或败。【样例输入】4 1 1 1 0 2 2 1 7 992438 1006399 781139 985280 4729 872779 563580【样例输出】1 0 1 1【评测用例规模与约定】对于所有评测用例，$1 ≤T≤ 200000,1 ≤ \sum^T_{i=1}n_i ≤ 200000,0 ≤X_i <2^{20}$。2. 题解2.1 思路分析a和b起始值都是0 两人数字相同时，即a^b=0时平局 a^b=X1^X2^……^Xn 因此 X1^X2^……^Xn=0-->平局 否则谁数字大就赢，也就是当a和b（二进制）从高到低有一位不同时，是1的那个人赢； 用 bitCount[] 数组 统计X1……Xn每一位为1的次数； eg： 4(100)、6(110)、5（101），这3个数统计后 bitCount[3]=3，bitCount[2]=1，bitCount[1]=1 从最高位遍历bitCount[i] bitCount[i]==1，该位数只要一个1，Alice 先手，胜 bitCount[i]是偶数，无影响，不处理 bitCount[i]是奇数： n是偶数，奇数个1奇数个0，只要后手把0先选完，后手就获得最后一个1的支配权，后手胜 n是奇数，奇数个1偶数个0，先手把0先选完，先手获得最后一个1的支配权,先手胜2.2 代码实现import java.util.*; public class Main { static Scanner scanner = new Scanner(System.in); // 统计x1-xn对应的2进制数的每1位的1的总数量 public static int[] getBitCount(int[] arr){ int[] bitCount = new int[20];//存储每一位对应的1的总数 for (int i = 0; i < bitCount.length; i++) { bitCount[i]=0; } for (int i = 0; i < arr.length ; i++) { int tmp = arr[i]; int bit=0; while (tmp>0){ bitCount[bit++]+=tmp&1; tmp = tmp>>1 ; } } return bitCount; } public static int playOneEpoch(){ int arrNum = scanner.nextInt(); int [] arr = new int[arrNum]; int xor = 0; // 用于计算X1^X2^……^Xn for (int j = 0; j < arrNum; j++) { arr[j]= scanner.nextInt(); xor ^= arr[j]; } if(xor==0)return 0; // 统计所有位的1的个数 int[] bitCountOf1 = getBitCount(arr); // 从高位到低位进行判断 for (int i = bitCountOf1.length-1; i >=0; i--) { if(bitCountOf1[i]==0 || bitCountOf1[i]%2==0){//无需进行处理，对结果没有影响 continue; }else if(bitCountOf1[i]==1){//先手Alice选中直接获胜 return 1; }else if(bitCountOf1[i]%2==1){ // 该位只有奇数个1，则拿到最后一个1的一方获胜 if(arrNum%2==0){//总数为偶数 后手有最后一个1的支配权，后手胜利 return -1; }else{//总数为奇数 先手有最后一个1的支配权，先手胜利 return 1; } } } return 0; } public static void main(String[] args) { int T = scanner.nextInt(); int[] res = new int[T]; for (int i = 0; i < T; i++) { res[i] = playOneEpoch(); } for (int i = 0; i < T; i++) { System.out.println(res[i]); } } }2.3 提交结果评测点序号评测结果得分CPU使用内存使用下载评测数据1正确20.00656ms94.55MB输入 输出2正确20.00687ms95.83MBVIP特权3正确20.00734ms95.92MBVIP特权4正确20.00500ms92.60MBVIP特权5正确20.00406ms92.29MBVIP特权参考资料异或数列（c++位运算）蓝桥杯2021年第十二届省赛-异或数列http://lx.lanqiao.cn/detail.page?submitid=7217417第十二届蓝桥杯大赛软件赛省赛 Python 大学 A 组 试题
