2025蓝桥杯JAVA编程题练习Day1

1.刑侦科推理试题

题目描述

有以下10道单选题，编程求这10道题的答案。

这道题的答案是：

A. A B. B C. C D. D

第5题的答案是：

A. C B. D C. A D. B

以下选项中哪一题的答案与其他三项不同：

A. 第3题 B. 第6题 C. 第2题 D. 第4题

以下选项中哪两题的答案相同：

A. 第1、5题 B. 第2、7题 C. 第1、9题 D. 第6、10题

以下选项中哪一题的答案与本题相同：

A. 第8题 B. 第4题 C. 第9题 D. 第7题

以下选项中哪两题的答案与第8题相同：

A. 第2、4题 B. 第1、6题 C. 第3、10题 D. 第5、9题

在这十道题中，被选中次数最少的选项字母为：

A. C B. B C. A D. D

以下选项中哪一题的答案与第1题的答案在字母中不相邻：

A. 第7题 B. 第5题 C. 第2题 D. 第10题

已知“第1题与第6题的答案相同”与“第X题与第5题的答案相同”的真假性相反，那么X为：

A. 第6题 B. 第10题 C. 第2题 D. 第9题

在这10道题的答案中，ABCD四个字母出现次数最多与最少者的差为：

A. 3 B. 2 C. 4 D. 1

输入描述

无输入。

输出描述

输出这10道题的答案，用空格隔开。输出示例：A A A A A A A A A A。（显然这不是本题的答案）

知识点

命题的表示
命题的真值
枚举

运行限制

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

AC代码

public class exercise1{
	public static void main(String[] args) {
		System.out.println("BCACACDABA");
	}
}

2.被污染的支票

问题描述

小蓝有一张支票，上面记录了一些数字。小蓝不小心打翻了墨水导致了支票上的一个数字被污染了，现在小蓝想通过剩下的数字来推断出那个被污染的数字。

设支票上被污染的数字为 xx ，没有被污染的数字共有 nn 个（设为 d1,d2,…,dnd1,d2,…,dn ），小蓝知道支票如果没有错误的话，上面没有被污染的数字应当是 xx 除了 11 和 xx 之外的其他所有因数，但是他无法确定支票是否错误。支票错误的情况有以下几种：

支票没有被污染的数字中混入了不是 xx 的因数的数字；
支票没有被污染的数字中缺失或重复 xx 的部分因数。

小蓝想请你帮助他判断支票是否没有错误，若没有错误，小蓝希望你能帮他求出支票上被污染的数字。

输入格式

第一行包含一个整数 nn ，表示没有被污染的数字的个数。

第二行包含 nn 个整数 d1,d2,…,dnd1,d2,…,dn ，表示支票上的数字。

输出格式

若支票没有错误，那么输出支票上被污染的数字；反之，若支票错误，被污染的数字不存在，则输出 −1−1 。

样例输入

8
8 2 12 6 4 24 16 3

样例输出

评测数据规模

对于所有评测数据， 1≤n≤300,2≤di≤1061≤n≤300,2≤di≤106 。

AC代码

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class exercise1{
	public static int gcd(int a,int b) {
		if(a<b) {
			int temp=a;
			a=b;
			b=temp;
		}
		while(b!=0) {
			int temp=b;
			b=a%b;
			a=temp;
		}
		return a;
	}
	public static int lcm(int a,int b) {
		return Math.abs(a*b)/gcd(a,b);
	}
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		int x = 0;
		ArrayList<Integer>d=new ArrayList<>();
		for(int i=0;i<n;i++) {
			int t = scan.nextInt();
			d.add(t);
		}
		Collections.sort(d);//默认升序
	    //降序：Collections.sort(d,Comparator.reserveOrder())
		x = d.get(0)*d.get(n-1);
		for(int i=0;i<n;i++) {
			for(int j=i+1;j<n;j++) {
				if(d.get(i)==d.get(j)) {
					System.out.println("-1");
					return;
				}
			}
			if(x!=d.get(i)*d.get(n-i-1)) {
				System.out.println("-1");
				return;
			}
		}
		System.out.println(x);
		scan.close();
	}
}

3.小蓝的奇妙冒险

问题描述

小蓝是一位勇敢的冒险家，他的目标是寻找传说中的黄金城。黄金城藏在一个神秘的迷宫中，迷宫有 nn 个房间，房间按照 11 到 nn 的顺序排列。每个房间中都有一堆金币，从房间 ii 中能够获得 a[i]a[i] 枚金币。房间的编号越大，里面的金币越多。小蓝一开始在房间 11，手头上没有金币。

如果小蓝在房间 xx，则他可以选择收集其中的金币，获得 a[x]a[x] 枚金币，如果小蓝在房间 xx（x<nx<n）并且拥有至少 b[x]b[x] 枚金币，他可以选择使用 b[x]b[x] 枚金币购买房间中的秘密地图，然后移动到房间 x+1x+1。

传说中的黄金城需要 cc 枚金币才能开启。请判断小蓝能否在 kk 天内（包括 kk 天）累积到足够的金币开启黄金城，若可以输出 Yes，反之输出 No。

输入格式

第一行包含三个整数 n,c,kn,c,k (2≤n≤1052≤n≤105, 1≤c,k≤1091≤c,k≤109) —— 表示迷宫中房间的数量、开启黄金城所需要的金币数量和天数上限。

第二行包含 nn 个整数 a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) —— 表示每个房间中的金币数量。

第三行包含 n−1n−1 个整数 b1,b2,…,bn−1b1,b2,…,bn−1 (1≤bi≤1091≤bi≤109) —— 表示从房间 ii 移动到房间 i+1i+1 所需的金币数量。

数据保证 a1≤a2≤⋯≤ana1≤a2≤⋯≤an。

输出格式

一行一个字符串，若可以在 kk 天内开启黄金城则输出 Yes，反之输出 No。

样例输入

5 6 7
1 2 3 4 5
4 3 2 1

样例输出

Yes

运行限制

最大运行时间：2s
最大运行内存: 512M

AC代码

import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class exercise1{
	static int n,c,k;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		c = scan.nextInt();
		k = scan.nextInt();
		int[] a = new int[n+1];
		int[] b = new int[n];
		for(int i=1;i<=n;i++) {
			a[i] = scan.nextInt();
		}
		for(int i=1;i<=n-1;i++) {
			b[i] = scan.nextInt();
		}
		if(dfs(1,0,0,a,b))System.out.println("Yes");
		else System.out.println("No");
		scan.close();
	}
	private static boolean dfs(int idx,int gold,int time,int[] a,int[] b) {
		if(gold>=c)return true;
		if(time>k)return false;
		if(idx<=n && dfs(idx,gold+a[idx],time+1,a,b))
			return true;
		if(idx<n && gold>=b[idx] && dfs(idx+1,gold-b[idx],time+1,a,b))
			return true;
		return false;
	}
}

4.摆玩具

问题描述

小蓝是一个热爱收集玩具的小伙子，他拥有 nn 个不同的玩具。

这天，他把 nn 个玩具按照高度顺序从矮到高摆放在了窗台上，然后，他希望将这些玩具分成 kk 个段，使得所有分段的极差之和尽可能小。

具体来说，你需要将一个长度为 nn 的序列分为 kk 段，我们定义 GiGi 为第 ii 个分段的极差，你要最小化 ∑i=1kGi∑i=1kGi。

你能帮助小蓝找到最小值是多少吗？

极差：是指每个分段中最高和最矮玩具高度之差，例如有一段为：{3,6,10,12}{3,6,10,12}，那么极差为 12−3=912−3=9。

分段：即每一段在原始序列中是一段连续区间，例如将 {1,2,3,4,5}{1,2,3,4,5} 分为两段，{1,2,3}∣{4,5}{1,2,3}∣{4,5} 是合法的，但是 {1,2,4}∣{3,5}{1,2,4}∣{3,5} 不是合法的。

输入格式

第一行输入两个整数 n,kn,k，代表玩具数量和需要分段的数量。

第二行输入 nn 个整数 {h1,h2,...,hn}{h1,h2,...,hn}，代表每个玩具的高度。

输出格式

输出一个整数，表示最小的极差和。

样例输入

5 2
2 5 7 10 13

样例输出

说明

存在多种分段方式，其结果都是最小值：

{2}∣{5,7,10,13}{2}∣{5,7,10,13}，极差和为 0+8=80+8=8。
{2,5,7}∣{10,13}{2,5,7}∣{10,13}，极差和为 5+3=85+3=8。
{2,5,7,10}∣{13}{2,5,7,10}∣{13}，极差和为 8+0=88+0=8。

不存在其他方案使得答案小于 88。

评测数据范围

1≤k≤n≤1051≤k≤n≤105 。

1≤h1≤h2≤h3≤...≤hn≤1091≤h1≤h2≤h3≤...≤hn≤109 。

解题思路

首先极差就是相邻数的差加起来，因此要得到最小的极差和，就要减去最大的相邻数的差（贪心）。相邻数是有n-1个的，把相邻数的差排序之后，根据要分段的段数，去掉相应的差即为答案。

AC代码

import java.util.*;
public class exercise1{
	static int n,k;
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		n = scan.nextInt();
		k = scan.nextInt();
		int[] h = new int[n+1];
		for(int i=1;i<=n;i++) {
			h[i] = scan.nextInt();
		}
		int ans=0;
		int[] d = new int[n];//相邻差
		for(int i=1;i<n;i++) {
			d[i]=h[i+1]-h[i];
			ans+=d[i];//段极差就是段相邻数的差相加
		}
		Arrays.sort(d);//使用排序（默认从小到大）
		int idx=1;//段数
		for(int i=n-1;i>=1;i--) {
			if(k==idx)break;
			ans-=d[i];
			idx++;
		}
		System.out.println(ans);
		scan.close();
	}
}

5.条件联结词

题目描述

给定原子变元P、Q的真值(用1表示T，用0表示F)，求命题公式P→Q的真值。

输入描述

输入原子变元P、Q的真值(1或0)，用空格隔开。

输出描述

输出命题公式P→Q的真值(1或0)。

样例输入

1 1

样例输出

知识点

联结词

解题思路

P->Q 即求 P<=Q

AC代码

import java.util.*;
public class exercise1{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int p = scan.nextInt();
		int q = scan.nextInt();
		int ans = 0;
		if(p==1&&q==1)ans=1;
		else if(p==1&&q==0)ans=0;//1->0是0
		else if(p==0&&q==1)ans=1;//0->1是1
		else ans=1;
		System.out.println(ans);
		scan.close();
	}
}

6.单身贵族游戏

问题描述

单身贵族游戏规则：游戏玩法似跳棋，但不能走步，只能跳；棋子只能跳过相邻的棋子（相邻位置上一定要有棋子）到空位上，并且把被跳过的棋子吃掉；棋子可以沿格线横、纵方向跳，但是不能斜跳。

在本题中，给定单身贵族游戏走若干步后的棋盘状态（不用判断是否合理），判断游戏是否已经结束了（即不能再走下去了）。

以下图(a)为单身贵族游戏的棋盘，图(b)演示了走棋的规则，图(c)所示的棋盘状态已经结束了，无法再走棋。

输入格式

输入数据占 77 行，描述了一个单身贵族游戏的棋盘状态。注意第 11、22、66、77 行的数据也是顶格的（在程序处理时，需要还原到棋盘中的位置）。每个位置上为 11 或 00，前者表示有棋子，后者表示没有。

输出格式

测试数据所表示的单身贵族游戏，如果游戏无法进行下去了，输出 yes，否则输出 no。

样例输入

样例输出

yes

AC代码

import java.util.*;
public class exercise1{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String[] s=new String[8];
		for(int i=1;i<=7;i++)s[i]=scan.nextLine();
		char[][] b = new char[8][8];
		for(int i=1;i<=2;i++) {
			for(int j=3;j<=5;j++) {
				b[i][j]=s[i].charAt(j-3);
			}
		}
		for(int i=3;i<=5;i++) {
			for(int j=1;j<=7;j++) {
				b[i][j]=s[i].charAt(j-1);
			}
		}
		for(int i=6;i<=7;i++) {
			for(int j=3;j<=5;j++) {
				b[i][j]=s[i].charAt(j-3);
			}
		}
		int ans=1;
		for(int i=1;i<=7;i++) {
			for(int j=1;j<=7;j++) {
				if(b[i][j]=='1') {
					if(b[i-1][j]=='1'||b[i+1][j]=='1'||
					   b[i][j-1]=='1'||b[i][j+1]=='1') {
						ans=0;
						break;
					}
				}
			}
			if(ans==0)break;
		}
		if(ans==0)System.out.println("no");
		else System.out.println("yes");
		scan.close();
	}
}

7.仲夏！幻夜？奇想曲！

问题描述

夏天来临，旅行者受可莉邀请来到了一个名为 "仲夏！幻夜？奇想曲！" 的音乐盛典。旅行者需要收集不同种类的魔法音符来完成曲目。这些魔法音符分布在 nn 个岛屿上，每个岛屿都有其特定的音符。岛屿之间存在依赖关系，即访问某些岛屿可能需要先访问其他岛屿并收集到特定音符。

旅行者的背包有容量限制 WW，需要选择合适的音符组合来完成曲目。给定岛屿的依赖关系和每个岛屿上音符的价值与重量，请帮助旅行者计算如何选择音符以得到最大的价值。

输入格式

第一行输入两个正整数 nn 和 WW，分别表示岛屿的数量和旅行者背包的容量。

接下来 nn 行，每行两个非负整数 vivi 和 wiwi，分别表示第 ii 个岛屿的音符价值和体积。

接下来的一行输入一个正整数 mm，表示接下来会有 mm 条依赖关系。

随后的 mm 行，每行两个整数 a,ba,b，表示获取岛屿 aa 的音符之前需要持有岛屿 bb 的音符。

输出格式

在一行中输出旅行者可以获得的最大音符价值。

样例输入

样例输出

样例说明

旅行者可以先去岛屿 11，然后可以选择去岛屿 22 或岛屿 33，但由于背包容量限制，他只能选择岛屿 22 的音符，所以最大价值为 50+80=13050+80=130。

测评数据规模

1≤n≤1001≤n≤100，1≤m≤n−11≤m≤n−1，1≤vi,wi≤1041≤vi,wi≤104，1≤W≤1051≤W≤105。

解题思路

依赖关系：联想到拓扑排序。

在图论中，拓扑排序（Topological Sorting）是一个有向无环图（DAG, Directed Acyclic Graph）的所有顶点的线性序列。且该序列必须满足下面两个条件：每个顶点出现且只出现一次。若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。而且必须是有向无环图才有拓扑排序

比如，如果用一个DAG图来表示一个工程，其中每个顶点表示工程中的一个任务，用有向边表示在做任务 B 之前必须先完成任务 A。故在这个工程中，任意两个任务要么具有确定的先后关系，要么是没有关系，绝对不存在互相矛盾的关系（即环路）。

动态规划方程：dp[k] = Math.max(dp[k], dp[k - w[u]] + v[u]);

dp[k] 表示在背包容量为 k 的情况下，旅行者能够获得的最大价值。
初始化时，dp[k] 为 0，因为背包为空时，最大的价值显然是 0。

如果将岛屿 u 的音符放入容量为 k 的背包中，能获得的最大价值是 dp[k - w[u]] + v[u]（即在放入该音符之前，剩余容量 k - w[u] 的最大价值，加上该音符的价值）。我们与当前 dp[k] 值做比较，取较大值。

AC代码

import java.util.*;
public class exercise1{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n=scan.nextInt();
		int W=scan.nextInt();
		int[] v=new int[n+1];
		int[] w=new int[n+1];
		for(int i=1;i<=n;i++) {
			v[i]=scan.nextInt();
			w[i]=scan.nextInt();
		}
		//建立邻接表
		List<List<Integer>> graph=new LinkedList<>();
		for(int i=0;i<=n;i++) {
			graph.add(new LinkedList<>());
		}
		int[] indg=new int[n+5];//记录点的入度
		int m=scan.nextInt();
		for(int i=1;i<=m;i++) {
			int a=scan.nextInt();
			int b=scan.nextInt();
			//b->a（有a之前必须要有b）
			graph.get(b).add(a);//邻接表连接边
			indg[a]++;
		}
		//进行拓扑排序
		Queue<Integer> q = new LinkedList<>();
		for(int i=1;i<=n;i++) { //先把入度为0的点先加入
			if(indg[i]==0)q.add(i);
		}
		List<Integer> topo = new LinkedList<>();
		while(!q.isEmpty()) {
			int u=q.poll();//弹出Queue队列的头部元素
			topo.add(u); //即删掉从u出发的所有边
			for(int t:graph.get(u)) { //枚举起点为u的所有邻边t
				indg[t]--;
				if(indg[t]==0)q.add(t);
			}
		}
		//开始进行动态规划
		int[] dp=new int[W+5];
		for(int u:topo) { //先把拓扑排序在前面的先放进来（最被依赖）
			for(int k=W;k>=1;k--) { //已知最大容量（01背包-逆序）
				if(k-w[u]>=0) {
					dp[k]=Math.max(dp[k],dp[k-w[u]]+v[u]);
				}
			}
		}
		System.out.println(dp[W]);
		scan.close();
	}
}

8.班级活动

问题描述

小明的老师准备组织一次班级活动。班上一共有 nn 名 (nn 为偶数) 同学，老师想把所有的同学进行分组，每两名同学一组。为了公平，老师给每名同学随机分配了一个 nn 以内的正整数作为 idid，第 ii 名同学的 idid 为 aiai。

老师希望通过更改若干名同学的 idid 使得对于任意一名同学 ii，有且仅有另一名同学 jj 的 idid 与其相同 (ai=ajai=aj)。请问老师最少需要更改多少名同学的 idid？

输入格式

输入共 22 行。

第一行为一个正整数 nn。

第二行为 nn 个由空格隔开的整数 a1,a2,...,ana1,a2,...,an。

输出格式

输出共 11 行，一个整数。

样例输入

4
1 2 2 3

样例输出

样例说明

仅需要把 a1 改为 3 或者把 a3 改为 11即可。

评测用例规模与约定

对于 20%的数据，保证 n≤10^3。

对于 100%的数据，保证 n≤10^5。

AC代码

import java.util.*;
public class exercise1{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int n=scan.nextInt();
		int[] a=new int[n];
		int[] cnt=new int[100000+10];
		for(int i=0;i<n;i++) {
			a[i]=scan.nextInt();
			cnt[a[i]]++;
		}
		int count1=0;
		int count2=0;
    //枚举cnt数组里面的数据
		for(int i=0;i<cnt.length;i++) {
			if(cnt[i]==1)count1++;
			if(cnt[i]>=2)count2+=cnt[i]-2;//cnt[i]-2这些剩下的都要改掉
		}
		int ans=0;
		if(count2>=count1)ans=count2;//剩下都要改，都可以改成和count1成对
		else ans=(count1+count2)/2;//count1一部分和count2成对，一部分自己对半成对
		System.out.println(ans);
		scan.close();
	}
}

9.双条件联结词

题目描述

给定原子变元P、Q的真值(用1表示T，用0表示F)，求命题公式P⇄Q的真值。

输入描述

输入原子变元P、Q的真值(1或0)，用空格隔开。

输出描述

输出命题公式P⇄Q的真值(1或0)。

样例输入

1 1

样例输出

AC代码

import java.util.*;
public class exercise1{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int p=scan.nextInt();
		int q=scan.nextInt();
		int ans=0;
		if(p==q)ans=1;
		else ans=0;
		System.out.println(ans);
		scan.close();
	}
}

10.求“(P∨Q)∧(P→R)∧(Q→R)”成真赋值

题目描述

编程求命题合式公式(P∨Q)∧(P→R)∧(Q→R)取值为T时的赋值（即P、Q、R的值）。禁止采用手工演算列出真值表，再用输出语句输出答案。

输入描述

无输入。

输出描述

按字典序输出该合式公式取值为T时的所有赋值（即P、Q、R的值，1或0，用空格隔开），每种赋值占一行。

样例输入

无输入。

样例输出

0 1 1      (仅给出第1行输出作为示例)

AC代码

import java.util.*;
public class exercise1{
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int[] p= {0,1};
		int[] q= {0,1};
		int[] r= {0,1};
		for(int i=0;i<2;i++) { //p
			for(int j=0;j<2;j++) { //q
				for(int k=0;k<2;k++) { //r
					if((p[i]==1||q[j]==1)&&(p[i]<=r[k])&&(q[j]<=r[k])) {
						System.out.println(p[i]+" "+q[j]+" "+r[k]);
					}
				}
			}
		}
		scan.close();
	}
}