2025藍橋杯JAVA編程題練習Day8

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();}
}