第十六届蓝桥杯模拟赛/校赛第二期个人题解,有错误的地方欢迎各位大佬指正
问题一(填空题)
【问题描述】
如果一个数 p 是个质数,同时又是整数 a 的约数,则 p 称为 a 的一个质因数。
请问, 2024 的最大的质因数是多少?
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
(1)思路::直接暴力枚举
(2)代码
public class Pro1 { public static void main(String[] args) { int ans=0; for(int i=1;i<=2024;i++){ if(get(i)&&2024%i==0){ ans=Math.max(ans,i); } } System.out.println(ans); } static boolean get(int x){ if(x<2)return false; for(int i=2;i<=x/i;i++){ if(x%i==0)return false; } return true; }}
(3)答案:23
问题二(填空题)
【问题描述】
对于两个整数 a, b,既是 a 的整数倍又是 b 的整数倍的数称为 a 和 b 的公倍数。公倍数中最小的正整数称为 a 和 b 的最小公倍数。
请问, 2024 和 1024 的最小公倍数是多少?
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
(1)思路:从2024开始枚举即可
(2)代码
public class Pro2 { public static void main(String[] args) { for(int i=2024;;i++){ if(i%2024==0&&i%1024==0){ System.out.println(i); break; } } }}
(3)答案: 259072
问题三(填空题)
【问题描述】
两个数按位异或是指将这两个数转换成二进制后,最低位与最低位异或作为结果的最低位,次低位与次低位异或作为结果的次低位,以此类推。
例如,3 与 5 按位异或值为 6 。
请问,有多少个不超过 2024 的正整数,与 2024 异或后结果小于 2024 。
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
(1)思路:只需要用异或计算符即可 比如 3^5=6
(2)代码
public class Pro3 { public static void main(String[] args) { int ans=0; for(int i=1;i<=2024;i++){ if((i^2024)<2024)ans++; } System.out.println(ans); }}
(3)答案: 2001
问题四(填空题)
【问题描述】
小蓝有一个整数,初始值为 1 ,他可以花费一些代价对这个整数进行变换。
小蓝可以花费 1 的代价将整数增加 1 。
小蓝可以花费 3 的代价将整数增加一个值,这个值是整数的数位中最大的那个(1 到 9)。
小蓝可以花费 10 的代价将整数变为原来的 2 倍。
例如,如果整数为 16,花费 3 将整数变为 22 。
又如,如果整数为 22,花费 1 将整数变为 23 。
又如,如果整数为 23,花费 10 将整数变为 46 。
请问,如果要将整数从初始值 1 变为 2024,请问最少需要多少代价?
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
(1)思路:dp问题 dp[i]表示 1-i的最小代价
状态转移方程 dp[i+1]=Math.min(dp[i+1],dp[i]+1);
dp[i+dg(i)]=Math.min(dp[i+dg(i)],dp[i]+3)
dp[2*i]=Math.min(dp[2*i],dp[i]+10)
也可以直接暴力写
(2)代码
import java.util.*;public class Pro4 { public static void main(String[] args) { int year = 2024; int maxN = year * 2; int[] dp = new int[maxN + 1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[1] = 0; Queue<Integer> queue = new LinkedList<>(); queue.offer(1); while (!queue.isEmpty()) { int num = queue.poll(); int cost = dp[num]; if (num + 1 <= maxN) { if (dp[num + 1] > cost + 1) { dp[num + 1] = cost + 1; queue.offer(num + 1); } } int maxDigit = get(num); if (num + maxDigit <= maxN) { if (dp[num + maxDigit] > cost + 3) { dp[num + maxDigit] = cost + 3; queue.offer(num + maxDigit); } } if (num * 2 <= maxN) { if (dp[num * 2] > cost + 10) { dp[num * 2] = cost + 10; queue.offer(num * 2); } } } System.out.println(dp[year]); } private static int get(int num) {//最大数位 int maxDigit = 0; while (num > 0) { int digit = num % 10; if (digit > maxDigit) { maxDigit = digit; } num /= 10; } return maxDigit; }}
(3)答案: 79
问题五(填空题)
【问题描述】
小蓝有以下 100 个整数:
534, 386, 319, 692, 169, 338, 521, 713, 640, 692, 969, 362, 311, 349, 308, 357, 515, 140, 591, 216,
57, 252, 575, 630, 95, 274, 328, 614, 18, 605, 17, 980, 166, 112, 997, 37, 584, 64, 442, 495,
821, 459, 453, 597, 187, 734, 827, 950, 679, 78, 769, 661, 452, 983, 356, 217, 394, 342, 697, 878,
475, 250, 468, 33, 966, 742, 436, 343, 255, 944, 588, 734, 540, 508, 779, 881, 153, 928, 764, 703,
459, 840, 949, 500, 648, 163, 547, 780, 749, 132, 546, 199, 701, 448, 265, 263, 87, 45, 828, 634.
小蓝想从中选出一部分数求和,使得和是 24 的倍数,请问这个和最大是多少?
【答案提交】
这是一道结果填空的题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。
(1)思路:简单的0-1背包问题
状态转移方程 dp[mod]=Math.max(dp[mod],dp[i]+num)
(2)代码
import java.util.Arrays;public class Pro5 { public static void main(String[] args) { int[] arr = { 534, 386, 319, 692, 169, 338, 521, 713, 640, 692, 969, 362, 311, 349, 308, 357, 515, 140, 591, 216, 57, 252, 575, 630, 95, 274, 328, 614, 18, 605, 17, 980, 166, 112, 997, 37, 584, 64, 442, 495, 821, 459, 453, 597, 187, 734, 827, 950, 679, 78, 769, 661, 452, 983, 356, 217, 394, 342, 697, 878, 475, 250, 468, 33, 966, 742, 436, 343, 255, 944, 588, 734, 540, 508, 779, 881, 153, 928, 764, 703, 459, 840, 949, 500, 648, 163, 547, 780, 749, 132, 546, 199, 701, 448, 265, 263, 87, 45, 828, 634 }; int[] dp = new int[24]; Arrays.fill(dp, -1); dp[0] = 0; for (int num : arr) { int[] newDp = dp.clone(); for (int i = 0; i < 24; i++) { if (dp[i] != -1) { int newSum = dp[i] + num; int mod = newSum % 24; newDp[mod] = Math.max(newDp[mod], newSum); } } dp = newDp; } System.out.println(dp[0]); }}
(3)答案: 49176
问题六(编程题)
【问题描述】
小蓝准备请自己的朋友吃饭。小蓝朋友很多,最终吃饭的人总数达 2024 人(包括他自己)。
请问如果每桌最多坐 n 人,最少要多少桌才能保证每个人都能吃饭。
【输入格式】
输入一行包含一个整数 n 。
【输出格式】
输出一行包含一个整数,表示最少的桌数。
【样例输入】
10
【样例输出】
203
【样例输入】
8
【样例输出】
253
【评测用例规模与约定】
对于所有评测用例,1 <= n <= 2024。
(1)思路:如果2024%n不等于0则多加一张桌,否则刚好够
(2)代码
import java.util.Scanner;public class Pro6 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); System.out.println(2024%n==0?2024/n:(2024/n)+1); }}
问题七(编程题)
【问题描述】
小蓝有一个数组 a[1], a[2], ..., a[n] ,请求出数组中值最小的偶数,输出这个值。
【输入格式】
输入的第一行包含一个整数 n 。
第二行包含 n 个整数,相邻数之间使用一个空格分隔,依次表示 a[1], a[2], ..., a[n] 。
【输出格式】
输出一行,包含一个整数,表示答案。数据保证数组中至少有一个偶数。
【样例输入】
9
9 9 8 2 4 4 3 5 3
【样例输出】
2
【样例输入】
5
4321 2143 1324 1243 4312
【样例输出】
1324
【评测用例规模与约定】
对于 30% 的评测用例,1 <= n <= 100,0 <= a[i] <= 1000。
对于 60% 的评测用例,1 <= n <= 1000,0 <= a[i] <= 1000。
对于所有评测用例,1 <= n <= 10000,0 <= a[i] <= 1000000。
(1)思路:数据量不大,直接暴力,一边输入一边找
(2)代码
import java.util.Scanner;public class Pro7 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int ans=Integer.MAX_VALUE;//直接1000000也可以 while(n-->0){ int tmp=sc.nextInt(); if(tmp%2==0)ans=Math.min(ans,tmp); } System.out.println(ans); }}
问题八(编程题)
【问题描述】
一个字符串包含LANQIAO是指在字符串中能取出几个字符,将他们按照在原串中的位置顺序摆成一排后字符串为 LANQIAO 。即字符串包含 LANQIAO 是指 LANQIAO 是这个串的子序列。
例如:LLLLLANHAHAHAQLANIIIIALANO 中包含 LANQIAO 。
又如:OAIQNAL 中不包含 LANQIAO 。
给点一个字符串,判断字符串中是否包含 LANQIAO 。
【输入格式】
输入一行包含一个字符串
【输出格式】
如果包含 LANQIAO ,输出一个英文单词 YES ,否则输出一个英文单词 NO 。
【样例输入】
LLLLLANHAHAHAQLANIIIIALANO
【样例输出】
YES
【样例输入】
OAIQNAL
【样例输出】
NO
【评测用例规模与约定】
对于所有评测用例,输入的字符串非空串,由大写字母组成,长度不超过 1000 。
(1)思路:用一个id来表示已经找到的LANQIAO的子字符的位置
(2)代码
import java.util.Scanner;public class Pro8 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String s=sc.next(); String s2 = "LANQIAO"; int id = 0; // 已经找到的字符串的位置 for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == s2.charAt(id)) { id++; } if (id == s2.length()) { System.out.println("YES"); return; } } System.out.println("NO"); }}
问题九(编程题)
【问题描述】
小蓝有一个 n 行 m 列的矩阵 a[i][j] ,他想在矩阵中找出一个“口”字形状的区域,使得区域上的值的和最大。
具体讲,一个“口”字形状的区域可以由两个坐标 (x1, y1) 和 (x2, y2) 确定,满足:
1 <= x1 < x2 <= n ;
1 <= y1 < y2 <= m ;
x2 - x1 = y2 - y1 。
对应的区域由满足以下条件之一的点 (x, y) 构成:
x1 <= x <= x2,且 y = y1 ,对应“口”的左边一竖;
y1 <= y <= y2,且 x = x1 ,对应“口”的上面一横;
x1 <= x <= x2,且 y = y2 ,对应“口”的右边一竖;
y1 <= y <= y2,且 x = x2 ,对应“口”的下面一横。
请注意有些点满足以上条件的多个,例如左上角的点 (x1, y1) ,在计算时算为一个点。
区域上的值是指对应区域的所有点的值,即“口”字的框上的值,不含框内和框外的值。
【输入格式】
输入的第一行包含两个整数 n, m ,分别表示行数和列数。
接下来 n 行,每行包含 m 个整数,相邻数之间使用一个空格分隔,依次表示矩阵的每行每列的值,本部分的第 i 行第 j 列表示 a[i][j] 。
【输出格式】
输出一行包含一个整数,表示最大的和。
【样例输入】
5 6
1 -1 2 -2 3 -3
-1 2 -2 3 -3 4
2 -2 3 -3 4 -4
-2 3 -3 4 -4 5
3 -3 4 -4 5 -5
【样例输出】
4
【样例说明】
取 (x1, y1) = (1, 1) , (x2, y2) = (5, 5) 可得到最大值。
【评测用例规模与约定】
对于 30% 的评测用例,1 <= n, m <= 30 ,-1000 <= a[i][j] <= 1000 。
对于 60% 的评测用例,1 <= n, m <= 100 ,-1000 <= a[i][j] <= 1000 。
对于所有评测用例,1 <= n, m <= 300 ,-1000 <= a[i][j] <= 1000 。
(1)思路:一开始以为是前缀和,但是只是口的边框上的值,所以暴力写了,不知道能不能拿满分
(2)代码
import java.util.Scanner;public class Pro9 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); int[][] matrix = new int[n][m]; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { matrix[i][j] = sc.nextInt(); } } int ans = Integer.MIN_VALUE; for (int x1 = 0; x1 < n; x1++) { for (int y1 = 0; y1 < m; y1++) { for (int len = 1; x1 + len < n && y1 + len < m; len++) { int x2 = x1 + len; int y2 = y1 + len; int tmp = 0; for (int y = y1; y <= y2; y++) {//上 tmp += matrix[x1][y]; } for (int y = y1; y <= y2; y++) {//下 tmp += matrix[x2][y]; } for (int x = x1 + 1; x < x2; x++) {//左 tmp += matrix[x][y1]; } for (int x = x1 + 1; x < x2; x++) {//右 tmp += matrix[x][y2]; } ans = Math.max(ans, tmp); } } } System.out.println(ans); }}
问题十(编程题)
【问题描述】
小蓝正在玩一个寻宝游戏。寻宝游戏在一个方格图上进行。方格图中的每一个格子都有一个坐标 (r, c),其中越往北 r 越小,越往南 r 越大,越往东 c 越大,越往西 c 越小。南北相邻方格的 c 坐标相同,r 坐标差一。东西相邻方格的 r 坐标相同, c 坐标差一。
游戏开始时,小蓝站在 (0, 0) 处,面向北边。游戏区域无限大,且没有障碍。每一步,小蓝控制自己的角色走一步,他可以有如下三种选择:
向前走:朝现在的方向前进到相邻的方格中,并保持当前的方向。
向左走:向左转90度,并前进到相邻的方格中(即进入到原来左边的方格),面向的方向变为了原来的左边。
向右走:向右转90度,并前进到相邻的方格中(即进入到原来右边的方格),面向的方向变为了原来的右边。
小蓝玩了一会儿,一共走了 n 步,他记录了自己的每一个动作。但是他没有找到宝藏。他怀疑前面的某一步出现了失误。他想知道,如果他改变之前的某一步,能到的位置有哪些。由于这个太复杂,他想知道最终到的位置(第 n 步后到的位置)有多少种。
【输入格式】
输入的第一行包含一个整数 n ,表示小蓝走了 n 步。
第二行包含一个长度为 n 的由大写字母组成的字符串,依次表示小蓝走的每一步。字母 F 、 L 、 R 分别表示对应的步是向前走、向左走、向右走。
【输出格式】
输出一行,包含一个整数,表示如果改变某一步,可以到的位置的种类数。
【样例输入】
3
FLR
【样例输出】
6
【样例说明】
如果不改变,三步依次走到:(-1, 0), (-1, -1), (-2, -1) ,最终位置为 (-2, -1) 。
如果第一步改成 L,三步依次走到:(0, -1), (1, -1), (1, -2) ,最终位置为 (1, -2) 。
如果第一步改成 R,三步依次走到:(0, 1), (-1, 1), (-1, 2) ,最终位置为 (-1, 2) 。
如果第二步改成 F,三步依次走到:(-1, 0), (-2, 0), (-2, 1) ,最终位置为 (-2, 1) 。
如果第二步改成 R,三步依次走到:(-1, 0), (-1, 1), (0, 1) ,最终位置为 (0, 1) 。
如果第三步改成 F,三步依次走到:(-1, 0), (-1, -1), (-1, -2) ,最终位置为 (-1, -2) 。
如果第三步改成 L,三步依次走到:(-1, 0), (-1, -1), (0, -1) ,最终位置为 (0, -1) 。
共有 6 种不同的最终位置。
【样例输入】
4
RRRR
【样例输出】
6
【样例说明】
有 8 种改变方法:
改为 FRRR ,最终位置为 (0, 0);
改为 LRRR ,最终位置为 (0, 0);
改为 RFRR ,最终位置为 (1, 1);
改为 RLRR ,最终位置为 (0, 2);
改为 RRFR ,最终位置为 (2, 0);
改为 RRLR ,最终位置为 (2, 2);
改为 RRRF ,最终位置为 (1, -1);
改为 RRRL ,最终位置为 (2, 0)。
不同的最终位置共有 6 种。
【评测用例规模与约定】
对于 30% 的评测用例,1 <= n <= 20。
对于 60% 的评测用例,1 <= n <= 1000。
对于所有评测用例,1 <= n <= 100000
(1)思路:暴力写,写的很乱,有好思路的大佬可以分享一下
(2)代码
import java.io.*;import java.util.*;public class Pro10 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine().trim()); String op = br.readLine().trim(); int[] dir = new int[n + 1];//方向 dir[0] = 0; // 初始方向北 int[] turn = new int[n + 1]; for(int i = 1; i <= n; i++) { char c = op.charAt(i - 1); if(c == 'F') { turn[i] = 0; } else if(c == 'L') { turn[i] = -1; } else if(c == 'R') { turn[i] = 1; } } for(int i = 1; i <= n; i++) {// 计算每一步后的方向 dir[i] = (dir[i - 1] + turn[i]) % 4; if(dir[i] < 0) dir[i] += 4; } int[] moveX = new int[n + 1]; int[] moveY = new int[n + 1]; for(int i = 1; i <= n; i++) { switch(dir[i]){ case 0: // 北 moveX[i] = -1; moveY[i] = 0; break; case 1: // 东 moveX[i] = 0; moveY[i] = 1; break; case 2: // 南 moveX[i] = 1; moveY[i] = 0; break; case 3: // 西 moveX[i] = 0; moveY[i] = -1; break; } } long[] sumX = new long[n + 2]; long[] sumY = new long[n + 2]; sumX[n + 1] = 0; sumY[n + 1] = 0; for(int i = n; i >= 1; i--) { sumX[i] = sumX[i + 1] + moveX[i]; sumY[i] = sumY[i + 1] + moveY[i]; } // 原始的最终坐标 long origX = sumX[1]; long origY = sumY[1]; HashSet<String> ans = new HashSet<>(); // 修改每一步 for(int k = 1; k <= n; k++) { char originalAction = op.charAt(k - 1); List<Character> replacements = new ArrayList<>(); if(originalAction == 'F') { replacements.add('L'); replacements.add('R'); } else if(originalAction == 'L') { replacements.add('F'); replacements.add('R'); } else if(originalAction == 'R') { replacements.add('F'); replacements.add('L'); } //计算新的最终位置 for(char rep : replacements) { int delta_turn = 0; if(originalAction == 'F') { if(rep == 'L') { delta_turn = -1; } else if(rep == 'R') { delta_turn = 1; } } else if(originalAction == 'L') { if(rep == 'F') { delta_turn = 1; } else if(rep == 'R') { delta_turn = 2; } } else if(originalAction == 'R') { if(rep == 'F') { delta_turn = -1; } else if(rep == 'L') { delta_turn = -2; } } //转身后 long rotatedX = nextX((int)sumX[k], (int)sumY[k], delta_turn); long rotatedY = nextY((int)sumX[k], (int)sumY[k], delta_turn); // 最终坐标 long newX = origX + rotatedX - sumX[k]; long newY = origY + rotatedY - sumY[k]; // 把位置变成对应的单独的字符串保存到Set 这样还可以顺带去重 String ss=newX+""+newY; ans.add(ss); } } System.out.println(ans.size()); } static long nextX(int x, int y, int next) { //改变X坐标 int steps = ((next % 4) + 4) % 4; switch(steps){ case 0: return x; case 1: return y; case 2: return -x; case 3: return -y; default: return x; // 默认返回x } } static long nextY(int x, int y, int next) { // 改变Y坐标 int steps = ((next % 4) + 4) % 4; switch(steps){ case 0: return y; case 1: return -x; case 2: return -y; case 3: return x; default: return y; // 默认返回y } }}