蓝桥杯·3月份刷题集训Day02

本篇博客旨在记录自已打卡蓝桥杯3月份刷题集训，同时会有自己的思路及代码解答希望可以给小伙伴一些帮助。本人也是算法小白，水平有限，如果文章中有什么错误之处，希望小伙伴们可以在评论区指出来，共勉💪。

集训A

A1、刷题统计

题目：小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天 做 a 道题目, 周六和周日每天做 b 道题目。请你帮小明计算, 按照计划他将在 第几天实现做题数大于等于 n 题?

输入格式：

输入一行包含三个整数 a,b 和 n.

输出格式：

输出一个整数代表天数。

样例输入：

10 20 99

样例输出：

8

评测用例规模与约定：

对于 50% 的评测用例, 1≤a,b,n≤10⁶.

对于 100%100% 的评测用例, 1≤a,b,n≤10¹⁸.

运行限制：

• 最大运行时间：1s
• 最大运行内存: 256M

解题代码：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);long a = sc.nextLong();long b = sc.nextLong();long n = sc.nextLong();// 每周做的题目数量long week = a*5 + b*2;// 周数long weekCnt = n / week;// 天数long count = weekCnt * 7;// 剩下不足一周的数量n %= week;for (int i = 1; i <= 7; i++) {if(i <= 5 && n >0) {n -= a;count++;}else if(i > 5 && n > 0){n -= b;count++;}}System.out.println(count);}
}

A2、天干地支

题目：古代中国使用天干地支来记录当前的年份。

天干一共有十个，分别为：甲（jiǎ）、乙（yǐ）、丙（bǐng）、丁（dīng）、戊（wù）、己（jǐ）、庚（gēng）、辛（xīn）、壬（rén）、癸（guǐ）。

地支一共有十二个，分别为：子（zǐ）、丑（chǒu）、寅（yín）、卯（mǎo）、辰（chén）、巳（sì）、午（wǔ）、未（wèi）、申（shēn）、酉（yǒu）、戌（xū）、 亥（hài）。

将天干和地支连起来，就组成了一个天干地支的年份，例如：甲子。

2020 年是庚子年。

每过一年，天干和地支都会移动到下一个。例如 2021 年是辛丑年。

每过 60 年，天干会循环 6 轮，地支会循环 5 轮，所以天干地支纪年每 60 年轮回一次。例如 1900 年，1960 年，2020 年都是庚子年。

给定一个公元纪年的年份，请输出这一年的天干地支年份。

输入格式：

输入一行包含一个正整数，表示公元年份。

其中有 ，输入的公元年份为不超过 9999 的正整数。

输出格式：

输入一行包含一个正整数，表示公元年份。

输入输出样例：

输入：

2020

输出：

gengzi

运行限制：

• 最大运行时间：1s
• 最大运行内存: 128M

解题代码：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int year = sc.nextInt();String[] str1 = new String[]{"geng","xin","ren","gui","jia","yi","bing","ding","wu","ji"};String[] str2 = new String[]{"zi","chou","yin","mao","chen","si","wu","wei","shen","you","xu","hai"};int tg = 0;int dz = 0;if(year == 1900 || year == 1960 || year == 2020) {}else if (year > 1960) {for (int i = 1960; i < year; i++) {if (tg == 9) tg=0;else tg++;if (dz == 11) dz=0;else dz++;}} else {for (int i = year; i < 1960; i++) {if (tg == 0) tg = 9;else tg--;if(dz == 0) dz = 11;else dz--;}}System.out.println(str1[tg] + str2[dz]);}
}

A3、递增序列

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

题目：对于一个字母矩阵，我们称矩阵中的一个递增序列是指在矩阵中找到两个字母，它们在同一行，同一列，或者在同一 45 度的斜线上，这两个字母从左向右看、或者从上向下看是递增的。

例如，如下矩阵中

LANN
QIAO

有L N、L N、A N、A N、I O、A O、L Q、A I、N O、N O、A Q、I N、A N 等 13 个 递增序列。注意当两个字母是从左下到右上排列时，从左向右看和从上向下看 是不同的顺序。

对于下面的 30 行 50 列的矩阵，请问总共有多少个递增序列？

VLPWJVVNNZSWFGHSFRBCOIJTPYNEURPIGKQGPSXUGNELGRVZAG
SDLLOVGRTWEYZKKXNKIRWGZWXWRHKXFASATDWZAPZRNHTNNGQF
ZGUGXVQDQAEAHOQEADMWWXFBXECKAVIGPTKTTQFWSWPKRPSMGA
BDGMGYHAOPPRRHKYZCMFZEDELCALTBSWNTAODXYVHQNDASUFRL
YVYWQZUTEPFSFXLTZBMBQETXGXFUEBHGMJKBPNIHMYOELYZIKH
ZYZHSLTCGNANNXTUJGBYKUOJMGOGRDPKEUGVHNZJZHDUNRERBU
XFPTZKTPVQPJEMBHNTUBSMIYEGXNWQSBZMHMDRZZMJPZQTCWLR
ZNXOKBITTPSHEXWHZXFLWEMPZTBVNKNYSHCIQRIKQHFRAYWOPG
MHJKFYYBQSDPOVJICWWGGCOZSBGLSOXOFDAADZYEOBKDDTMQPA
VIDPIGELBYMEVQLASLQRUKMXSEWGHRSFVXOMHSJWWXHIBCGVIF
GWRFRFLHAMYWYZOIQODBIHHRIIMWJWJGYPFAHZZWJKRGOISUJC
EKQKKPNEYCBWOQHTYFHHQZRLFNDOVXTWASSQWXKBIVTKTUIASK
PEKNJFIVBKOZUEPPHIWLUBFUDWPIDRJKAZVJKPBRHCRMGNMFWW
CGZAXHXPDELTACGUWBXWNNZNDQYYCIQRJCULIEBQBLLMJEUSZP
RWHHQMBIJWTQPUFNAESPZHAQARNIDUCRYQAZMNVRVZUJOZUDGS
PFGAYBDEECHUXFUZIKAXYDFWJNSAOPJYWUIEJSCORRBVQHCHMR
JNVIPVEMQSHCCAXMWEFSYIGFPIXNIDXOTXTNBCHSHUZGKXFECL
YZBAIIOTWLREPZISBGJLQDALKZUKEQMKLDIPXJEPENEIPWFDLP
HBQKWJFLSEXVILKYPNSWUZLDCRTAYUUPEITQJEITZRQMMAQNLN
DQDJGOWMBFKAIGWEAJOISPFPLULIWVVALLIIHBGEZLGRHRCKGF
LXYPCVPNUKSWCCGXEYTEBAWRLWDWNHHNNNWQNIIBUCGUJYMRYW
CZDKISKUSBPFHVGSAVJBDMNPSDKFRXVVPLVAQUGVUJEXSZFGFQ
IYIJGISUANRAXTGQLAVFMQTICKQAHLEBGHAVOVVPEXIMLFWIYI
ZIIFSOPCMAWCBPKWZBUQPQLGSNIBFADUUJJHPAIUVVNWNWKDZB
HGTEEIISFGIUEUOWXVTPJDVACYQYFQUCXOXOSSMXLZDQESHXKP
FEBZHJAGIFGXSMRDKGONGELOALLSYDVILRWAPXXBPOOSWZNEAS
VJGMAOFLGYIFLJTEKDNIWHJAABCASFMAKIENSYIZZSLRSUIPCJ
BMQGMPDRCPGWKTPLOTAINXZAAJWCPUJHPOUYWNWHZAKCDMZDSR
RRARTVHZYYCEDXJQNQAINQVDJCZCZLCQWQQIKUYMYMOVMNCBVY
ABTCRRUXVGYLZILFLOFYVWFFBZNFWDZOADRDCLIRFKBFBHMAXX

运行限制：

• 最大运行时间：1s
• 最大运行内存: 128M

解题代码：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {System.out.println(52800);}
}

集训B

B1、123

题目：小蓝发现了一个有趣的数列，这个数列的前几项如下：

1,1,2,1,2,3,1,2,3,4,⋯

小蓝发现，这个数列前 1 项是整数 1，接下来 2 项是整数 1 至 2，接下来 3 项是整数 1 至 3，接下来 4 项是整数 1 至 4，依次类推。

小蓝想知道，这个数列中，连续一段的和是多少。

输入格式：

输入的第一行包含一个整数 T，表示询问的个数。

接下来 T 行，每行包含一组询问，其中第 i 行包含两个整数 l i 和 r i，表示询问数列中第 l i 个数到第 r i 个数的和。

输出格式：

输出 T 行，每行包含一个整数表示对应询问的答案。

输入输出样例：

输入：

3
1 1
1 3
5 8

输出：

1
4
8

运行限制：

• 最大运行时间：5s
• 最大运行内存: 256M

解题代码：

水平有限，用例过了4/10

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int t = sc.nextInt();long[][] T = new long[t][2];for (int i = 0; i < t; i++) {T[i][0] = sc.nextLong();T[i][1] = sc.nextLong();}for (int i = 0; i < T.length; i++) {System.out.println(sum(T[i][0],T[i][1]));}}private static long sum(long a, long b){// 求求和long sum = 0;long count = 1;for (int j = 1; count <= b; j++) {for (int i = 1; i <= j; i++) {if(count >= a) {sum += i;}count++;if (count > b) {break;}}}return sum;}
}

B2、答疑

题目：有 n 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。

老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。 一位同学答疑的过程如下：

1. 首先进入办公室，编号为 i 的同学需要 s i 毫秒的时间。
2. 然后同学问问题老师解答，编号为 i 的同学需要 a i 毫秒的时间。
3. 答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可 以忽略。
4. 最后同学收拾东西离开办公室，需要 e i 毫秒的时间。一般需要 10 秒、20 秒或 30 秒，即 e i 取值为 10000，20000 或 30000。

一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。

答疑从 0 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群 里面发消息的时刻之和最小。

输入格式：

输入第一行包含一个整数 n，表示同学的数量。

接下来 n 行，描述每位同学的时间。其中第 i 行包含三个整数 s i, a i, e i，意义如上所述。

其中有 ，1 ≤ n ≤ 1000，1≤ s_i ≤60000，1≤ a_i ≤106， e_i ∈10000,20000,30000，即 e_i 一定是 10000、20000、30000之一。

输出格式：

输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少。

输入输出样例：

输入：

3
10000 10000 10000
20000 50000 20000
30000 20000 30000

输出：

280000

运行限制：

• 最大运行时间：3s
• 最大运行内存: 128M

解题代码：

import java.util.Arrays;
import java.util.Scanner;/*** @author QIA* @create 2023-03-23-14:07*/
public class Main{public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();long[][] list = new long[n][4]; // 用第四个数来存储三个数之和long num = 0l; // num记录每个同学的发信息的时间long sum = 0l; // sum记录所有同学发的时间的总和for (int i = 0; i < n; i++) {for (int j = 0; j < 3; j++) {list[i][j] = sc.nextLong(); // 输入list[i][3] += list[i][j]; // 前三个数的和}}// 下面两个sort用于排序，由小到大排序// 可能会有几个同学所花的时间一样，所以先给收拾所花的时间排序Arrays.sort(list, (a,b) -> (int)(a[2]-b[2]));// 这样第二个排序，时间相同的同学，收拾所花的时间长的会在后面，Arrays.sort(list, (a,b) -> (int)(a[3]-b[3]));for (int i = 0; i < n; i++) {num += list[i][3]; // 每个同学的发信息时间sum += num-list[i][2]; // 同学发信息时间的总和}System.out.println(sum);}
}

集训C

C1、包子凑数

题目：小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有 N 种蒸笼，其中第 i 种蒸笼恰好能放 A_i 个包子。每种蒸笼都有非常多笼，可以认为是无限笼。

每当有顾客想买 X 个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有 X 个包子。比如一共有 3 种蒸笼，分别能放 3、4 和 5 个包子。当顾客想买 11 个包子时，大叔就会选 2 笼 3 个的再加 1 笼 5 个的（也可能选出 1 笼 3 个的再加 2 笼 4 个的）。

当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有 3 种蒸笼，分别能放 4、5 和 6 个包子。而顾客想买 7 个包子时，大叔就凑不出来了。

小明想知道一共有多少种数目是包子大叔凑不出来的。

输入格式：

第一行包含一个整数 N (1≤N≤100)。

以下 N 行每行包含一个整数 A_i (1≤*A_i*≤100)。

输出格式：

一个整数代表答案。如果凑不出的数目有无限多个，输出 INF。

输入输出样例：

示例 1：

输入：

2
4
5

输出：

6

样例说明：

凑不出的数目包括：1, 2, 3, 6, 7, 11。

示例 2：

输入：

2
4
6

输出：

INF

样例说明：

所有奇数都凑不出来，所以有无限多个

运行限制：

• 最大运行时间：1s
• 最大运行内存: 256M

解题代码：

借鉴大佬的题解

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
// 借鉴大佬的代码public class Main {static int n,g;public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();int[] a = new int[n];for (int i = 0; i < a.length; i++) {a[i] = sc.nextInt();if (i == 0){  // 从第一个数开始g = a[i];}g = gcd(g,a[i]); // 和其他笼数看是否互质}boolean[] dp = new boolean[10001];if(g != 1) {// 所有系数不互质,解有无数个System.out.println("INF");} else {// 每种笼里面的个数对应的整数倍，都能凑出来// 方法一：先用第一笼开始装，在装第二笼，即i=1时，在遍历过程中即有可能会和i= 0时判断的dp[0]进行组合也会和自己的dp[1]进行叠加，以此类推，在后面几笼都会加到前面的dp[]for (int i = 0; i < n; i++) {dp[a[i]] = true;for (int j = 1; j + a[i]< dp.length ; j++) {if(dp[j]) dp[j+a[i]] = true;}}/*//方法2：for (int i = 0; i < a.length; i++) {for (int j = 1; j < dp.length; j++) {if (j%a[i]==0) {  //每一笼的倍数必定能够装dp[j]=true;}}}for (int i = 1; i < a.length; i++) {for (int j = 1; j < dp.length; j++) {if (dp[j]) {//在能凑出来的情况下，他的下一个能凑出来的个数是//一种笼子里面的包子数加上当前能凑出来的个数是一定能凑出来的if (j+a[i]<dp.length) {dp[j+a[i]]=true;}}}}*/int ans = 0;for (int i = 1; i < dp.length; i++) {if (!dp[i]) {ans++;}}System.out.println(ans);}}// 找出最大公约数方法private static int gcd(int a,int b) {return b%a == 0 ? a : gcd(b, a%b);}
}

C2、背包与魔法

题目：小蓝面前有 N 件物品, 其中第 i 件重量是 W_i, 价值是 V_i 。她还有一个背包, 最大承重是 M 。

小蓝想知道在背包称重范围内, 她最多能装总价值多少的物品?

特别值得一提的是, 小蓝可以使用一个魔法 (总共使用一次), 将一件物品 的重量增加 K, 同时价值秝倍。(当然小蓝也可以不使用魔法)

输入格式：

第一行包含 3 个整数 N、M 和 K 。

以下 N 行, 每行两个整数 W_i 和 V_i 。

输出格式：

一个整数代表答案。

样例输入：

3 10 3
5 10
4 9
3 8

样例输出：

26

样例说明：

选择第二件和第三件物品, 同时对第二件物品使用魔法。

运行限制：

语言	最大运行时间	最大运行内存
C++	1s	256M
C	1s	256M
Java	3s	256M
Python3	5s	256M

解题代码：

借鉴大佬题解

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;/*** @author QIA* @create 2023-03-23-17:10*/
public class Main {public static StreamTokenizer st=new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));public static void main(String[] args) throws IOException {//dp[i][0]表示背包容量为i，不使用魔法得到的最大价值//dp[i][1]表示背包容量为i，使用魔法得到的最大价值int n = nextInt();int m = nextInt();int k = nextInt();int[] w = new int[n + 1];int[] v = new int[n + 1];int[][] dp = new int[m + 1][2];for (int i = 1; i <=n; i++) {w[i]=nextInt();v[i]=nextInt();}for (int i = 1; i <=n; i++) {       //先遍历物品for (int j = m; j >=w[i] ; j--) {   //再遍历背包，j是容积//如果能选且还没有使用魔法dp[j][0]=Math.max(dp[j-w[i]][0]+v[i],dp[j][0]); //不适用魔法，和01背包模板一样//已经使用过魔法了if(j>=w[i]+k){//dp[j-w[i]][1]+v[i]表示之前的一个物品使用魔法//dp[j-w[i]-k][0]+v[i]*2表示第i件物品这次使用魔法dp[j][1]=Math.max(Math.max(dp[j][1],dp[j-w[i]][1]+v[i]), dp[j-w[i]-k][0]+v[i]*2);}}}//将用魔法和不用魔法的情况取最大值就行System.out.println(Math.max(dp[m][1],dp[m][0]));}public static int nextInt() throws IOException {st.nextToken();return (int)st.nval;}
}

C3、本质上升队列

本题为填空题，只需要算出结果后，在代码中使用输出语句将所填结果输出即可。

题目：小蓝特别喜欢单调递增的事物。

在一个字符串中，如果取出若干个字符，将这些字符按照在字符串中的顺序排列后是单调递增的，则成为这个字符串中的一个单调递增子序列。

例如，在字符串 lanqiao 中，如果取出字符 n 和 q，则 nq 组成一个单调递增子序列。类似的单调递增子序列还有 lnq、i、ano 等等。 小蓝发现，有些子序列虽然位置不同，但是字符序列是一样的，例如取第二个字符和最后一个字符可以取到 ao，取最后两个字符也可以取到 ao。小蓝认为他们并没有本质不同。

对于一个字符串，小蓝想知道，本质不同的递增子序列有多少个？ 例如，对于字符串 lanqiao，本质不同的递增子序列有 21 个。它们分别是 l、a、n、q、i、o、ln、an、lq、aq、nq、ai、lo、ao、no、io、lnq、anq、lno、ano、aio。

请问对于以下字符串（共 200200 个小写英文字母，分四行显示）：

tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf
iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij
gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad
vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl

本质不同的递增子序列有多少个？

运行限制：

• 最大运行时间：1s
• 最大运行内存: 128M

import java.util.Scanner;
import java.util.Arrays;public class Main {public static void main(String[] args) {String str = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhf" +"iadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqij" +"gihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmad" +"vrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";int[] dp = new int[str.length()];Arrays.fill(dp, 1);for (int i = 0; i < str.length(); i++) {for (int j = 0; j < i; j++) {if (str.charAt(i) > str.charAt(j)) {dp[i] += dp[j];} else if (str.charAt(i) == str.charAt(j)) {dp[i] -= dp[j];}}}int count = 0;for (int i : dp) count += i;System.out.println(count);}
}

最后

有帮助的话，希望可以点赞❤️+收藏⭐，谢谢各位大佬~~🙌🙌🙌