当前位置：首页 > news >正文

2025蓝桥杯JAVA编程题练习Day8

news 来源：原创 2025/6/17 14:45:01

1. 路径

题目描述

小蓝学习了最短路径之后特别高兴，他定义了一个特别的图，希望找到图中的最短路径。

小蓝的图由 2021 个结点组成，依次编号 1 至 2021。

对于两个不同的结点 a, b，如果 a 和 b 的差的绝对值大于 21，则两个结点之间没有边相连；如果 a 和 b 的差的绝对值小于等于 21，则两个点之间有一条长度为 a 和 b 的最小公倍数的无向边相连。

例如：结点 1 和结点 23 之间没有边相连；结点 3 和结点 24 之间有一条无向边，长度为 24；结点 15 和结点 25 之间有一条无向边，长度为 75。

请计算，结点 1 和结点 2021 之间的最短路径长度是多少。

提示：建议使用计算机编程解决问题。

解题要点

由于你在图中使用了加权边，传统的 BFS 不能直接用于加权边的最短路径求解。对于加权图，通常使用 Dijkstra 算法来计算最短路径。

主要步骤：

使用 优先队列（最小堆）来帮助处理加权图。
使用 Dijkstra 算法来求解从节点 1 到节点 n 的最短路径。

AC代码

import java.util.*;
class Edge{int target;int weight;public Edge(int target,int weight) {this.target=target;this.weight=weight;}
}
public class exercise1{public static Scanner scan=new Scanner(System.in);public static int gcd(int a,int b) {return b==0?a:gcd(b,a%b);}public static int lcm(int a,int b) {return (a*b)/gcd(a,b);}public static void main(String[] args) {int n=2021;List<List<Edge>>graph=new LinkedList<>();for(int i=0;i<=n;i++) {graph.add(new LinkedList<>());}for(int i=1;i<=n;i++) {for(int j=i+1;j<=n;j++) {if(j-i>21)continue;else {int weight=lcm(j,i);graph.get(i).add(new Edge(j,weight));graph.get(j).add(new Edge(i,weight));}}}//求1到n的最短路径（Dijkstra算法）int[] dist = new int[n+1]; // 存储最短路径Arrays.fill(dist, Integer.MAX_VALUE);dist[1]=0;// 优先队列，存储每个节点和它的当前距离PriorityQueue<int[]>pq=new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); // 按距离排序pq.add(new int[]{1,0});while(!pq.isEmpty()) {int[] cur=pq.poll();int u=cur[0];int cd=cur[1];// 如果当前节点的距离已经大于已知的最短距离，跳过if(cd>dist[u])continue;for(Edge ed:graph.get(u)) {int v=ed.target;int w=ed.weight;int newd=cd+w;if(newd<dist[v]) {dist[v]=newd;pq.add(new int[] {v,newd});}}}System.out.println(dist[n]);}
}

2.排列字母

问题描述

小蓝要把一个字符串中的字母按其在字母表中的顺序排列。

例如，LANQIAO 排列后为 AAILNOQ。

又如，GOODGOODSTUDYDAYDAYUP 排列后为 AADDDDDGGOOOOPSTUUYYY。

请问对于以下字符串，排列之后字符串是什么？

WHERETHEREISAWILLTHEREISAWAY

AC代码

import java.util.*;
public class exercise1{public static Scanner scan=new Scanner(System.in);public static void main(String[] args) {String s="WHERETHEREISAWILLTHEREISAWAY";char[] a=s.toCharArray();Arrays.sort(a);for(int i=0;i<a.length;i++) {System.out.print(a[i]);}}
}

3.饮料换购

题目描述

乐羊羊饮料厂正在举办一次促销优惠活动。乐羊羊 C 型饮料，凭 3 个瓶盖可以再换一瓶 C 型饮料，并且可以一直循环下去(但不允许暂借或赊账)。

请你计算一下，如果小明不浪费瓶盖，尽量地参加活动，那么，对于他初始买入的 n 瓶饮料，最后他一共能喝到多少瓶饮料。

输入描述

输入一个整数 n(0<n<1000)n(0<n<1000)，表示开始购买的饮料数量。

输出描述

输出一个整数，表示实际得到的饮料数

输入输出样例

输入

输出

AC代码

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

4.七边形

问题描述

小蓝迷上了七边形，他正尝试用小球来拼接出他喜欢的七边形图案。下图是他拼出的前四个七边形，第 11 至第 44 个七边形图案消耗的小球数量依次是 11、77、1818、3434。请问对于第 2024060120240601 个七边形图案，需要消耗的小球数量是多少？

AC代码

（记得开long!!）

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);long ans=0;for(int i=1;i<=20240601;i++){if(i==1)ans=1;else{ans+=i*3;ans+=(i-2)*2;}}System.out.println(ans);scan.close();}
}

5.完美数对

问题描述

蓝桥杯作为最热门的程序设计竞赛之一，主办方为了更好地评估选手的程序设计能力，新研制了一台用于检测选手程序设计能力的仪器。

主办方邀请了 NN 位同学进行检测，以验证机器的准确性。检测结果表示为数组 AA，其中第 ii 位同学检测出的能力值为 AiAi。

得知这一检测结果后，蓝桥杯的出题人小蓝获得了出题灵感。他希望统计满足以下条件的正整数对 (a,b)(a,b) 的数量，这些数对被称为 "完美数对"：

完美数对定义：对于数对 (a,b)(a,b)，若在数组 AA 中，数值 aa 至少出现了 bb 次，且数值 bb 至少出现了 aa 次，则数对 (a,b)(a,b) 被称为完美数对。

现在，请您协助小蓝解决这个问题。

输入格式

第一行输入一个整数 N(2≤N≤106)N(2≤N≤106) 表示接受检测的同学数量。

第二行输入 NN 个整数 A1,A2,A3,⋯,AN(1≤Ai≤106)A1,A2,A3,⋯,AN(1≤Ai≤106) 表示每位同学的能力值。

输出格式

输出一个整数表示答案。

样例输入

5
1 1 2 2 3

样例输出

样例说明

对于样例，数对 (1,1),(1,2),(2,1),(2,2)(1,1),(1,2),(2,1),(2,2) 满足条件，所以答案为 44。

AC代码

import java.util.*;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int[] a=new int[n];for(int i=0;i<n;i++){a[i]=scan.nextInt();}HashMap<Integer,Integer> hp=new HashMap<>();for(int i=0;i<n;i++){hp.put(a[i],hp.getOrDefault(a[i],0)+1); //不是更新，而是每一个都放进去}int ans=0;//枚举hp里的每一个(HashMap的每一项)for(HashMap.Entry<Integer,Integer> e:hp.entrySet()){int x=e.getKey(); //值int hashX=e.getValue(); //次数for(int b=1;b<=hashX;b++){if(hp.containsKey(b) && hp.get(b)>=x)ans++;}}System.out.println(ans);scan.close();}
}

6.排列高手

问题描述

第十六届蓝桥杯即将来临，组委会的专家们希望此次比赛能够更好地考察选手们的思维能力，因此特邀著名的排列高手——小蓝参与助阵！希望他能为本届蓝桥杯设计一道富有创意的排列题。

小蓝接到任务后，立即动起脑筋，口中大喊：“题来！”于是，一道关于排列的问题浮现：

给定一个大小为 nn 的排列，你可以任意调整排列的顺序，以使调整后的排列所有非空子数组的 mexmex 之和最小，你需要求出这个最小的 mexmex 之和。

其中 mexmex 表示最小的不在集合中的正整数，例如 mex([1,3,4])=2,mex([2,3,4])=1mex([1,3,4])=2,mex([2,3,4])=1。

排列：一个由 11 到 nn 的所有整数组成的序列，其中每个数字恰好出现一次。

现在请你尝试解决小蓝给出的这道问题。

输入格式

输入一行包括一个整数 n(1≤n≤105)n(1≤n≤105) 表示排列的大小。

输出格式

输出一个整数表示答案。

样例输入

样例输出

样例说明

对于样例，一种可能的最优排列情况为 [1,3,2][1,3,2]，其所有子数组 mexmex 之和为 1111。

其中 mex([1])=2,mex([1,3])=2,mex([1,3,2])=4,mex([3])=1,mex([3,2])=1,mex([2])=1mex([1])=2,mex([1,3])=2,mex([1,3,2])=4,mex([3])=1,mex([3,2])=1,mex([2])=1。

AC代码

import java.util.*;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();//1  n  n-1 .... 2long ans = 0;for(int i = n;i>=2;i--){ans += i+1;}ans += n+1;System.out.println(ans);scan.close();}
}

7.美丽区间

问题描述

美丽区间是这样的一组区间：[L1,R1]、[L2,R2]、[L3,R3]... 构造美丽区间需要满足以下条件：

L1=1
Li≤Ri
Ri−Li≥K
对于任意的 i>1，有 Li=Ri−1 + 1
gcd(Li,Ri)=1，其中 gcd 指两个数的最大公约数
在满足上述条件的情况下，Li、Ri 之间的差尽可能的小。

输入格式

第一行输入一个整数 K。第二行输入一个整数 T，表示有 T 组测试用例。接下来 T 行，每行输入一个整数 n。

输出格式

对每个输入的整数 n，输出一行，包含一个整数，表示 n 属于第几个美丽区间。

样例输入

样例输出

11
3
1

样例说明

第 1 个美丽区间为：[1,11]。

第 2 个美丽区间为：[12,23]。

第 3 个美丽区间为：[24,35]。

⋯⋯

第 11 个美丽区间为：[120,131]。

评测用例规模与约定

对于 60% 的评测用例：1≤T≤10^3，1≤K≤10^6，1≤n≤10^6。

对于 100% 的评测用例：1≤T≤10^6，1≤K≤10^6，1≤n≤10^6。

AC代码

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static int gcd(int a,int b){return b==0?a:gcd(b,a%b);}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int k=scan.nextInt();HashMap<Integer,Integer> hp=new HashMap<>();int id=1;int l=1;int r=1;for(int i=1;i<=1000000+10;i++){l=i;i+=k;r=i;while(gcd(l,r)!=1)r++;i=r;hp.put(r,id);id++;}int t=scan.nextInt();for(int i=1;i<=t;i++){int n=scan.nextInt();while(!hp.containsKey(n))n++;System.out.println(hp.get(n));}scan.close();}
}

8.园丁

问题描述

小明是一位尽职尽责的园丁。这天他负责维护一棵树，树上有 n 个结点 1,2,…,n，根结点为 1，结点 i 的权值为 ai。

他需要更改一些结点的权值为任意正整数，使得对于任意一个至少有 2 个儿子结点的结点 i 满足：任意两个 i 的儿子结点的权值的乘积都不是完全平方数。

请问小明至少需要修改多少个结点的权值？

输入格式

输入共 n+1 行。第一行为一个正整数 n。第二行为 n 个由空格分开的正整数 a1,a2,…,an。后面 n−1 行，每行两个正整数表示树上的一条边。

输出格式

输出共 1 行，一个整数表示答案。

样例输入

6
1 2 9 8 4 4
1 2
1 3
1 4
2 5
2 6

样例输出

样例说明

其中一种方案：将结点 2,5 的权值分别修改为 3,2。

评测用例规模与约定

对于 20% 的评测用例，保证 n≤10^3。

对于 100% 的评测用例，保证 n≤10^5，1≤ai≤10^9。

9.分组

问题描述

小明班上有 n 名同学，老师准备按上一次考试的分数对同学们进行分组，第 i 名同学的分数为 ai。老师希望把同学们分为尽可能多的小组，且满足每个小组中的同学分数的最大值至少是最小值的两倍。请问最多能分出多少个小组？如果把所有人分到同一组都不能满足条件则输出 0。

输入格式

输入共 2 行。第一行为一个正整数 n。第二行为 n 个由空格分开的正整数表示 a1,a2,…,an。

输出格式

输出共 1 行，一个整数表示答案。

样例输入

6
3 5 2 1 4 2

样例输出

样例说明

其中一种分组方式：第一组 {a4,a1}={1,3}，第二组 {a3,a2}={2,5}，第三组 {a6,a5}={2,4}。

AC代码

贪心，由于最多可以有n / 2组（不可能1个人一组），所以可以先将数组排序，使用双指针匹配，左指针从0开始，右指针从n/2开始，贪心地选取最小的值与右半部分匹配。

import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int [] a=new int [n];for(int i=0;i<n;i++)a[i]=scan.nextInt();Arrays.sort(a);int ans=0;for(int l=0,r=n/2;r<n;r++){if(2*a[l]>a[r])continue;if(r>=n)break;l++;ans++;}System.out.println(ans);scan.close();}
}

10.喜糖摆放

问题描述

在过年时，蓝桥村的孩子们充满活力，他们化身为捣蛋鬼，挨家挨户寻讨喜糖。他们一共收到了 NN 颗糖，每颗糖的甜度各不相同，第 ii 颗糖的甜度为 AiAi。

然而，如何分配这些喜糖却成了一个令人困扰的问题，因为糖的数量不能完全平均分给孩子们。

蓝桥村的村长察觉到了这个困难，于是说道："我有一个问题，只要你们中有小朋友能解决，我就会提供足够的喜糖，使得你们可以均分。"

问题陈述如下：

每次可以选择将任意位置的糖果移到最后，求使得糖果按照升序排列所需的最小操作次数。

作为蓝桥村最聪明的孩子之一，你能否尝试解决这个问题呢？

输入格式

第一行输入一个整数 N(2≤N≤105)N(2≤N≤105) 表示糖果数量。

第二行输入 NN 个整数 A1,A2,⋯,AN(1≤Ai≤109)A1,A2,⋯,AN(1≤Ai≤109) 表示糖果的甜度，数据保证 A1,A2,⋯,ANA1,A2,⋯,AN 各不相同。

输出格式

输出一个整数表示答案。

样例输入

5
1 3 2 4 5

样例输出

AC代码

import java.util.*;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int[] a=new int[n];int[] b=new int[n];for(int i=0;i<n;i++){a[i]=scan.nextInt();b[i]=a[i];}Arrays.sort(b);int j=0;for(int i=0;i<n;i++){if(a[i]==b[j]){j++;}}System.out.println(n-j);scan.close();}
}

1. 路径

题目描述

解题要点

AC代码

2.排列字母

问题描述

AC代码

3.饮料换购

题目描述

输入描述

输出描述

输入输出样例

AC代码

4.七边形

问题描述

AC代码

5.完美数对

问题描述

输入格式

输出格式

样例输入

样例输出

样例说明

AC代码

6.排列高手

问题描述

输入格式

输出格式

样例输入

样例输出

样例说明

AC代码

7.美丽区间

问题描述

输入格式

输出格式

样例输入

样例输出

样例说明

评测用例规模与约定

AC代码

8.园丁

问题描述

输入格式

输出格式

样例输入

样例输出

样例说明

评测用例规模与约定

9.分组

问题描述

输入格式

输出格式

样例输入

样例输出

样例说明

AC代码

10.喜糖摆放

问题描述

输入格式

输出格式

样例输入

样例输出

AC代码

相关文章：