2025蓝桥杯JAVA编程题练习Day5

1.最少步数【省模拟赛】

问题描述

小蓝要上一个楼梯，楼梯共有 n 级台阶（即小蓝总共要走 nn级）。小蓝每一步可以走 1 级、2 级或 3 级台阶。

请问小蓝至少要多少步才能上到楼梯顶端？

输入格式

输入一行包含一个整数 n。

输出格式

输出一行包含一个整数，表示答案。

样例输入1

样例输出1

样例输入2

样例输出2

AC代码

java">import java.util.*;public class exercise1 {static Scanner scan=new Scanner(System.in);public static void main(String[] args) {int n=scan.nextInt();int ans=0;if(n==0)ans=0;else if(n<=3)ans=1;else {ans+=(n/3);n=n-(n/3)*3;ans+=(n/2);n=n-(n/2)*2;ans+=n;}System.out.println(ans);}
}

2.赢球票

题目描述

某机构举办球票大奖赛。获奖选手有机会赢得若干张球票。

主持人拿出 N 张卡片（上面写着 1⋯N 的数字），打乱顺序，排成一个圆圈。

你可以从任意一张卡片开始顺时针数数: 1,2,3 ⋯⋯

如果数到的数字刚好和卡片上的数字相同，则把该卡片收入囊中，从下一个卡片重新数数。

直到再无法收获任何卡片，游戏结束。囊中卡片数字的和就是赢得球票的张数。

比如：

卡片排列是：1 2 3

我们从 1 号卡开始数，就把 1 号卡拿走。再从 2 号卡开始，但数的数字无法与卡片对上，很快数字越来越大，不可能再拿走卡片了。因此这次我们只赢得了 1 张球票。

还不算太坏！如果我们开始就傻傻地从 2 或 3 号卡片数起，那就一张卡片都拿不到了。

如果运气好，卡片排列是 2 1 3，那我们可以顺利拿到所有的卡片！

本题的目标：已知顺时针卡片序列，随便你从哪里开始数，求最多能赢多少张球票（就是收入囊中的卡片数字之和）

输入描述

第一行一个整数 N (N≤100)，表示卡片数目。

第二行 N 个整数，表示顺时针排列的卡片。

输出描述

输出一行，一个整数，表示最好情况下能赢得多少张球票。

输入输出样例

输入

3
1 2 3

输出

AC代码

javascript">import java.util.*;public class exercise1 {static Scanner scan=new Scanner(System.in);public static void main(String[] args) {int n=scan.nextInt();ArrayList<Integer> a=new ArrayList<>();int ans=0;for(int i=0;i<n;i++) {a.add(scan.nextInt());}for(int i=0;i<n;i++) {ArrayList<Integer> temp=new ArrayList<>(a);int idx=i,sum=0,num=1;while(num<=n&&temp.size()!=0) { //数到n或者被取完了if(temp.get(idx)==num) {sum+=temp.remove(idx);num=1;//重新开始数}else {idx++;num++;}if(idx==temp.size())idx=0;//数组到末尾,重新置为0}ans=Math.max(ans, sum);}System.out.println(ans);}
}

3.拉马车

题目描述

小的时候，你玩过纸牌游戏吗？

有一种叫做"拉马车"的游戏，规则很简单，却很吸引小朋友。

其规则简述如下：

假设参加游戏的小朋友是 A 和 B ，游戏开始的时候，他们得到的随机的纸牌序列如下：

A方：[K,8,X,K,A,2,A,9,5,A]

B方：[2,7,K,5,J,5,Q,6,K,4]

其中的 X表示 "10"，我们忽略了纸牌的花色。

从 A 方开始，A、B双方轮流出牌。

当轮到某一方出牌时，他从自己的纸牌队列的头部拿走一张，放到桌上，并且压在最上面一张纸牌上（如果有的话）。

此例中，游戏过程：

A出 K，B 出 2，A 出 8，B 出 7，A 出 X，此时桌上的序列为：

K,2,8,7,X

当轮到 B 出牌时，他的牌 K 与桌上的纸牌序列中的 K 相同，则把包括 K 在内的以及两个 K 之间的纸牌都赢回来，放入自己牌的队尾。注意：为了操作方便，放入牌的顺序是与桌上的顺序相反的。

此时，A、B双方的手里牌为：

A 方：[K,A,2,A,9,5,A]

B 方：[5,J,5,Q,6,K,4,K,X,7,8,2,K]

赢牌的一方继续出牌。也就是 B 接着出 5，A 出 K，B 出 J，A 出 A，B 出 5，又赢牌了。此时桌上的序列为：

5,K,J,A,5

此时双方手里牌：

A 方：[2,A,9,5,A]

B 方：[Q,6,K,4,K,X,7,8,2,K,5,A,J,K,5]

注意：更多的时候赢牌的一方并不能把桌上的牌都赢走，而是拿走相同牌点及其中间的部分。但无论如何，都是赢牌的一方继续出牌，有的时候刚一出牌又赢了，也是允许的。

当某一方出掉手里最后一张牌，但无法从桌面上赢取牌时，游戏立即结束。

对于本例的初始手牌情况下，最后 A 会输掉，而 B 最后的手里牌为：

9K2A62KAX58K57KJ5

本题的任务就是已知双方初始牌序，计算游戏结束时，赢的一方手里的牌序。当游戏无法结束时，输出 -1。

输入描述

输入为 2 行，2 个串，分别表示 A、B 双方初始手里的牌序列。我们约定，输入的串的长度不超过 30。

输出描述

输出为 1 行，1 个串，表示 AA 先出牌，最后赢的一方手里的牌序。

输入输出样例

输入

96J5A898QA
6278A7Q973

输出

2J9A7QA6Q6889977

AC代码

java">import java.util.*;public class exercise1 {static Scanner scan=new Scanner(System.in);public static void main(String[] args) {StringBuilder a=new StringBuilder(scan.nextLine());StringBuilder b=new StringBuilder(scan.nextLine());StringBuilder table=new StringBuilder();boolean flag=true;// true则a出牌，false则b出牌int idx=0;while(a.length()>0&&b.length()>0) {if(flag) {idx=table.indexOf(String.valueOf(a.charAt(0)));// StringBuilder的indexOf方法可返回字符/字符串在字符串中第一次出现的下标，若字符串里有返回下标，若无返回-1if(idx==-1) {table.append(a.charAt(0));a.delete(0, 1);flag=false;}else {win(a,table,idx);// a收牌后继续出牌}}else {idx=table.indexOf(String.valueOf(b.charAt(0)));if(idx==-1) {table.append(b.charAt(0));b.delete(0, 1);flag=true;}else {win(b,table,idx);// a收牌后继续出牌}}}if(a.length()==0){System.out.println(b);}else {System.out.println(a);}}public static void win(StringBuilder hand,StringBuilder table,int idx) {table.append(hand.charAt(0));hand.delete(0, 1);StringBuilder temp=new StringBuilder(table.substring(idx));hand.append(temp.reverse());table.delete(idx, table.length());}
}

4.正则问题

题目描述

考虑一种简单的正则表达式：

只由 x ( ) | 组成的正则表达式。

小明想求出这个正则表达式能接受的最长字符串的长度。

例如 ((xx|xxx)x|(x|xx))xx 能接受的最长字符串是： xxxxxx，长度是 6。

输入描述

一个由 x()| 组成的正则表达式。输入长度不超过 100，保证合法。

输出描述

这个正则表达式能接受的最长字符串的长度。

输入输出样例

输入

((xx|xxx)x|(x|xx))xx

输出

AC代码

java">import java.util.*;
class pair{int x;int y;pair(int x,int y){this.x=x;this.y=y;}
}
public class exercise1 {static Scanner scan=new Scanner(System.in);public static void main(String[] args) {String s=scan.nextLine();Stack<pair> stack=new Stack<>();int len=0;int ans=0;for(char c:s.toCharArray()) {if(c=='x') {len++;}else if(c=='(') {stack.push(new pair(len,ans));len=0;ans=0;}else if(c==')') {pair temp=stack.pop();// 栈先进后出len=temp.x+Math.max(len, ans);ans=temp.y;}else if(c=='|') {ans=Math.max(ans,len);len=0;}}System.out.println(Math.max(ans, len));}
}

java">import java.util.*;
public class exercise1 {static Scanner scan=new Scanner(System.in);static int pos=-1;static String s=null;public static void main(String[] args) {s=scan.nextLine();System.out.println(dfs());}private static int dfs() {int cur=0; //目前x的最大个数int max=0; //最终x的最大个数while(pos<s.length()-1) {pos++;char c=s.charAt(pos);if(c=='(') { //进入下一层cur+=dfs();}else if(c=='x') {cur++;}else if(c=='|') {max=Math.max(cur, max);cur=0;}else {break; //遇到')'，跳出本轮循环}}return Math.max(max, cur);}
}

5.对局匹配

题目描述

小明喜欢在一个围棋网站上找别人在线对弈。这个网站上所有注册用户都有一个积分，代表他的围棋水平。

小明发现网站的自动对局系统在匹配对手时，只会将积分差恰好是 K 的两名用户匹配在一起。如果两人分差小于或大于 K，系统都不会将他们匹配。

现在小明知道这个网站总共有 N 名用户，以及他们的积分分别是 A1,A2,⋯AN。

小明想了解最多可能有多少名用户同时在线寻找对手，但是系统却一场对局都匹配不起来(任意两名用户积分差不等于 K)？

输入描述

第一行包含两个个整数 N,K。

第二行包含 N 个整数 A1,A2,⋯AN。

其中，1≤N≤10^5,0≤Ai≤10^5,0≤K≤10^5。

输出描述

输出一个整数，代表答案。

输入输出样例

输入

10 0
1 4 2 8 5 7 1 4 2 8

输出

AC代码

java">import java.util.*;
public class exercise1 {static Scanner scan=new Scanner(System.in);public static void main(String[] args) {int n=scan.nextInt();int k=scan.nextInt();int[] a=new int[n];int count=0;for(int i=0;i<n;i++)a[i]=scan.nextInt();Arrays.sort(a); // 从小到大for(int i=0,t=0;i<n;i++) {if(a[i]==-1)continue; // 用户被匹配过，跳过for(int j=t+1;j<n;j++) {if(a[j]==-1)continue;if(Math.abs(a[j]-a[i])==k) {a[i]=-1; // 将两个用户标记为已匹配a[j]=-1;t=j;count++; // 匹配成功，匹配对数加一}else if(a[j]-a[i]>k)break;}}System.out.println(n-count); // 输出无法匹配的用户数目}
}

6.分考场（DFS）

题目描述

n 个人参加某项特殊考试。

为了公平，要求任何两个认识的人不能分在同一个考场。

求是少需要分几个考场才能满足条件。

输入描述

输入格式：

第一行，一个整数 n (1≤n≤100)，表示参加考试的人数。

第二行，一个整数 m，表示接下来有 m 行数据。

以下 m 行每行的格式为：两个整数 a,b，用空格分开 ( 1≤a,b≤n )表示第 a 个人与第 b 个人认识。

输出描述

输出一行一个整数，表示最少分几个考场。

输入输出样例

输入

输出

AC代码

java">import java.util.*;
public class exercise1 {static Scanner scan=new Scanner(System.in);static int sum=110; //最多可以安排的教室static int[][] nums=new int[sum][sum]; //安排座位nums[i][j]:第i考场的j座位static boolean rela[][]=new boolean[sum][sum]; //标记相互认识的static int n=scan.nextInt();static int m=scan.nextInt(); public static void main(String[] args) {for(int i=1;i<=m;i++) {int a=scan.nextInt();int b=scan.nextInt();// a和b不能再同一个考场rela[a][b]=true;rela[b][a]=true;}dfs(1,1); //从第一个学生,第一个考场安排System.out.println(sum);}public static void dfs(int x,int k) { //x代表第几个学生，k代表第几个考场if(k>=sum)return; //要求最少考场数目,sum为当前的答案，如果比这个值还大就不要if(x>n) {//学生安排完，更新sum=Math.min(sum, k);return;}for(int i=1;i<=k;i++) {int j=0; //j为座位号while(nums[i][j]!=0&&!rela[x][nums[i][j]]) {j++;//如果该考场没有认识的}//跳出循环if(nums[i][j]==0) {//有位置nums[i][j]=x; //x可以进行i考场dfs(x+1,k); //k不变nums[i][j]=0;}}//遍历完所有已存在的考场，发现都有认识的人，就要重新再开一个考场nums[k+1][0]=x;dfs(x+1,k+1);nums[k+1][0]=0;}
}

7.合根植物

题目描述

w 星球的一个种植园，被分成 m×n个小格子（东西方向 m 行，南北方向 n 列）。每个格子里种了一株合根植物。

这种植物有个特点，它的根可能会沿着南北或东西方向伸展，从而与另一个格子的植物合成为一体。

如果我们告诉你哪些小格子间出现了连根现象，你能说出这个园中一共有多少株合根植物吗？

输入描述

第一行，两个整数 m,n，用空格分开，表示格子的行数、列数（1≤m,n≤1000）。

接下来一行，一个整数 k (0≤k≤10^5 )，表示下面还有 k 行数据。

接下来 k 行，每行两个整数 a，b，表示编号为 a 的小格子和编号为 b 的小格子合根了。

格子的编号一行一行，从上到下，从左到右编号。

比如：5×4 的小格子，编号：

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
17 18 19 20

输出描述

输出植物数量。

输入输出样例

输入

输出

AC代码

java">import java.util.*;
public class exercise1 {static Scanner scan=new Scanner(System.in);static int m=scan.nextInt();static int n=scan.nextInt();static int k=scan.nextInt();static int[] p=new int[n*m+10];public static int find(int x) {if(x==p[x])return x;else return p[x]=find(p[x]);}public static void main(String[] args) {for(int i=1;i<=n*m;i++) {p[i]=i;}for(int i=1;i<=k;i++) {int a=scan.nextInt();int b=scan.nextInt();int fa=find(a);int fb=find(b);if(fa!=fb) {p[fa]=fb;}}Set<Integer>s=new HashSet<>();for(int i=1;i<=n*m;i++) {int fa=find(i);s.add(fa);}System.out.println(s.size());}
}

8.四平方和

题目描述

四平方和定理，又称为拉格朗日定理：

每个正整数都可以表示为至多 4 个正整数的平方和。

如果把 0 包括进去，就正好可以表示为 4 个数的平方和。

对于一个给定的正整数，可能存在多种平方和的表示法。

要求你对 4 个数排序：

0≤a≤b≤c≤d

并对所有的可能表示法按 a,b,c,d 为联合主键升序排列，最后输出第一个表示法。

输入描述

程序输入为一个正整数 N(N<5×10^6)。

输出描述

要求输出 4 个非负整数，按从小到大排序，中间用空格分开

输入输出样例

输入

输出

0 2 2 2

AC代码

（1）通过87%样例

java">import java.util.*;
public class exercise1 {static Scanner scan=new Scanner(System.in);public static void main(String[] args) {int n=scan.nextInt();ArrayList<Integer> a=new ArrayList<>();for(int i=0;i<=Math.sqrt(n);i++) { //只需在1到根号n下找a.add(i); //0、1、2....}for(int i1=0;i1<=a.size();i1++) {for(int i2=0;i2<=a.size();i2++) {for(int i3=0;i3<=a.size();i3++) {for(int i4=0;i4<=a.size();i4++) {if(n==i1*i1+i2*i2+i3*i3+i4*i4) {System.out.println(i1+" "+i2+" "+i3+" "+i4);return;}}}}}}
}

（2）过100%样例（为了防止重复，只有最外层循环是从0开始的）

java">import java.util.*;
public class exercise1 {static Scanner scan=new Scanner(System.in);public static void main(String[] args) {int n=scan.nextInt();ArrayList<Integer> a=new ArrayList<>();for(int i=0;i<=Math.sqrt(n);i++) {a.add(i); //0、1、2....}for(int i1=0;i1<=a.size();i1++) {for(int i2=i1;i2<=a.size();i2++) {for(int i3=i2;i3<=a.size();i3++) {for(int i4=i3;i4<=a.size();i4++) {if(n==i1*i1+i2*i2+i3*i3+i4*i4) {System.out.println(i1+" "+i2+" "+i3+" "+i4);return;}}}}}}
}

9.数字诗意

问题描述

在诗人的眼中，数字是生活的韵律，也是诗意的表达。

小蓝，当代顶级诗人与数学家，被赋予了"数学诗人"的美誉。他擅长将冰冷的数字与抽象的诗意相融合，并用优雅的文字将数学之美展现于纸上。

某日，小蓝静坐书桌前，目光所及，展现着 n 个数字，它们依次为 a1,a2,…,an，熠熠生辉。小蓝悟到，如果一个数能够以若干个（至少两个）连续的正整数相加表示，那么它就蕴含诗意。例如，数字 6 就蕴含诗意，因为它可以表示为 1+2+3。而 8 则缺乏诗意，因为它无法用连续的正整数相加表示。

小蓝希望他面前的所有数字都蕴含诗意，为此，他决定从这 n 个数字中删除一部分。请问，小蓝需要删除多少个数字，才能使剩下的数字全部蕴含诗意？

输入格式

第一行包含一个整数 n，表示展示的数字个数。

第二行包含 n 个整数 a1,a2,…,an，表示展示的数字。

输出格式

输出一个整数，表示小蓝需要删除的数字个数，以使剩下的数字全部蕴含诗意。

样例输入

3
3 6 8

样例输出

AC代码

java">import java.util.*;
public class exercise1 {static Scanner scan=new Scanner(System.in);public static void main(String[] args) {// 奇数3=1+2,5=2+3,7=3+4,...,29=14+15...都成立// 偶数4=2+2=1+3不行，6=1+2+3行，8=1+2+3+2=4+4不行，10=1+2+3+4行// 偶数得到规律：偶数/2%2==0不行，偶数/2%2==1行// 因此可以得到3、5、6、7、9、10、、、行，2的幂不行int n=scan.nextInt();int ans=0; //不满足的for(int i=1;i<=n;i++) {Long a=scan.nextLong();if(a<3)ans++;else { // 2的幂如8:8/2=4,4/2=2,2/2=1while((a%2==0)&&a>1) {a/=2;}if(a==1)ans++;}}System.out.println(ans);}
}

10.商品库存管理（差分数组）

问题描述

在库存管理系统中，跟踪和调节商品库存量是关键任务之一。小蓝经营的仓库中存有多种商品，这些商品根据类别和规格被有序地分类并编号，编号范围从 1 至 n。初始时，每种商品的库存量均为 0。

为了高效地监控和调整库存量，小蓝的管理团队设计了 m 个操作，每个操作涉及到一个特定的商品区间，即一段连续的商品编号范围（例如区间 [L,R]）。执行这些操作时，区间内每种商品的库存量都将增加 1。然而，在某些情况下，管理团队可能会决定不执行某些操作，使得这些操作涉及的商品区间内的库存量不会发生改变，维持原有的状态。

现在，管理团队需要一个评估机制，来确定如果某个操作未被执行，那么最终会有多少种商品的库存量为 0。对此，请你为管理团队计算出，每个操作未执行时，库存量为 0 的商品的种类数。

输入格式

第一行包含两个整数 n 和 m，分别表示商品的种类数和操作的个数。

接下来的 m 行，每行包含两个整数 L 和 R，表示一个操作涉及的商品区间。

输出格式

输出共 m 行，每行一个整数，第 i 行的整数表示如果不执行第 i 个操作，则最终库存量为 0 的商品种类数。

样例输入

样例输出

1
0
1

样例说明

考虑不执行每个操作时，其余操作对商品库存的综合影响：

不执行操作 1：剩余的操作是操作 2（影响区间 [2,4]）和操作 3（影响区间 [3,5]）。执行这两个操作后，商品库存序列变为 [0,1,2,2,1]。在这种情况下，只有编号为 1 的商品的库存量为 0。因此，库存量为 0 的商品种类数为 1。
不执行操作 2：剩余的操作是操作 1（影响区间 [1,2]）和操作 3（影响区间 [3,5]）。执行这两个操作后，商品库存序列变为 [1,1,1,1,1]。在这种情况下，所有商品的库存量都不为0。因此，库存量为 0 的商品种类数为 0。
不执行操作 3：剩余的操作是操作 1（影响区间 [1,2]）和操作 2（影响区间 [2,4]）。执行这两个操作后，商品库存序列变为 [1,2,1,1,0]。在这种情况下，只有编号为 5 的商品的库存量为 0。因此，库存量为0 的商品种类数为 1。

AC代码

java">import java.util.*;
public class exercise1 {static Scanner scan=new Scanner(System.in);public static void main(String[] args) {int n=scan.nextInt();int m=scan.nextInt();int[] d=new int[n+2]; //差分数组int[][] op=new int[m+1][2];for(int i=1;i<=m;i++) {int l=scan.nextInt();int r=scan.nextInt();op[i][0]=l;op[i][1]=r;d[l]++;d[r+1]--;}for(int i=1;i<=n;i++) {d[i]+=d[i-1];// 变成原来的数组}int ans1=0;for(int i=1;i<=n;i++) {if(d[i]==0)ans1++;}for(int i=1;i<=m;i++) {int l=op[i][0];int r=op[i][1];int ans2=0;for(int j=l;j<=r;j++) {if(d[j]==1)ans2++;}System.out.println(ans1+ans2);}}
}