2025藍橋杯JAVA編程題練習Day2

1.大衣構造字符串

問題描述

已知對于一個由小寫字母構成的字符串，每次操作可以選擇一個索引，將該索引處的字符用三個相同的字符副本替換。

現有一長度為?NN?的字符串?UU，請幫助大衣構造一個最小長度的字符串?SS，使得經過任意次數操作后該字符串能轉換為字符串?UU。

保證存在唯一滿足條件的字符串。

輸入格式

第一行輸入一個正整數?NN?表示字符串的長度。

第二行輸入一個長度為?NN?的字符串?U?U?。

輸出格式

輸出一個最小長度的字符串?SS，使得經過任意次數操作后該字符串能轉換為字符串?UU。

樣例輸入1

6
aaabbb

樣例輸出1

ab

樣例輸入2

7
abbbbbc

樣例輸出2

abc

樣例輸入3

4
abcd

樣例輸出3

abcd

AC代碼?

import java.util.*;
public class exercise1{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();scan.nextLine();String u=scan.nextLine();String ans="";for(int i=0;i<n;i++) {if(i+1<n&&i+2<n&&u.charAt(i)==u.charAt(i+1)&&u.charAt(i)==u.charAt(i+2)) {ans=ans+u.charAt(i);i+=2;}else {ans=ans+u.charAt(i);}}System.out.println(ans);scan.close();}
}

2.大衣的異或回文對

問題描述

大衣有一個長度為?NN?的數組?AA，大衣想知道數組中有多少對?(i,j)(1≤i≤j≤N)(i,j)(1≤i≤j≤N)?滿足?Ai⊕AjAi?⊕Aj??的十進制數是回文的，⊕⊕?表示按位異或。

你能回答大衣嗎的問題嗎？

輸入格式

第一行輸入一個正整數?NN?表示數組的長度。

第二行輸入?NN?個整數?A1,A2,?,AN?A1?,A2?,?,AN???表示數組中的元素。

輸出格式

輸出一個數字表示答案。

樣例輸入1

4
13 27 12 26

樣例輸出1

樣例輸入2

3
2 2 2

樣例輸出2

AC代碼

import java.util.*;
public class exercise1{private static boolean pd(String s) {for(int i=0;i<s.length()/2;i++) {if(s.charAt(i)!=s.charAt(s.length()-i-1))return false;}return true;}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();}int ans=0;for(int i=0;i<n;i++) {for(int j=i;j<n;j++) {int temp=a[i]^a[j];String st=String.valueOf(temp);if(pd(st))ans++;}}System.out.println(ans);scan.close();}
}

?3.金蘋果群島的建設

問題描述

探險家們發現了一片由?nn?個島嶼組成的群島，命名為金蘋果群島。這些島嶼之間通過地脈相連，每一對相連的島嶼都可以通過地脈通往其他相連的島嶼。現在，探險家們計劃在某些島嶼之間建設橋梁，以便每個島嶼都能夠相互到達。橋梁是雙向通行的。

已知有?mm?條地脈，每條地脈都連接了兩個島嶼。你的任務是計算至少需要建設多少座橋梁，才能實現探險家們的計劃。

輸入格式

第一行包含兩個整數?nn?和?mm?，分別表示島嶼的數量和地脈的數量。

接下來的?mm?行，每行包含兩個整數?aa?和?bb，表示第?aa?個島嶼和第?bb?個島嶼之間有一條地脈。

輸出格式

輸出一個整數，表示至少需要建設的橋梁數量。

樣例輸入

樣例輸出

評測數據范圍

1≤n≤1051≤n≤105?，0≤m≤1050≤m≤105?，1≤a,b≤n1≤a,b≤n?，a≠ba=b。

AC代碼

（1）通過80%

import java.util.*;
public class exercise1{static int[] f;private static int find(int x) {if(f[x]==x)return x;else return f[x]=find(f[x]);}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();f=new int[n+1];for(int i=1;i<=n;i++) {f[i]=i;}for(int i=0;i<m;i++) {int a=scan.nextInt();int b=scan.nextInt();int fa=find(a);int fb=find(b);if(fa!=fb)f[fa]=fb;}int ans=0;for(int i=1;i<=n;i++) {for(int j=i+1;j<=n;j++) {int fi=find(i);int fj=find(j);if(fi!=fj) {ans++;f[fi]=fj;}}}System.out.println(ans);scan.close();}
}

（2）通過100%。

優化部分：避免雙重循環合并集合。在原始代碼里的?for 循環中 find(i) 和 find(j) 的操作可能會導致重復查詢，應該只統計連通塊的數量，而不再二次合并。先統計不同連通塊數量（只有根節點才計數），最終答案就是連通塊數量-1。

import java.util.*;
public class exercise1{static int[] f;private static int find(int x) {if(f[x]==x)return x;else return f[x]=find(f[x]);}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();f=new int[n+1];for(int i=1;i<=n;i++) {f[i]=i;}for(int i=0;i<m;i++) {int a=scan.nextInt();int b=scan.nextInt();int fa=find(a);int fb=find(b);if(fa!=fb)f[fa]=fb;}int ans=0;for(int i=1;i<=n;i++) {if(f[i]==i)ans++;}System.out.println(ans-1);scan.close();}
}

4.大衣的飛機場

問題描述

大衣有?NN?臺飛機，第?ii?臺飛機在?AiAi??時間降落，在?Bi?Bi???時間起飛。

由于降落和起飛都需要占用軌道，每條軌道在某一時間只能被一臺飛機使用，請問最少需要多少條軌道才能讓所有飛機正常起降。

輸入格式

第一行輸入一個正整數?NN?表示飛機的數量。

第二行輸入?NN?個整數?A1,A2,?,ANA1?,A2?,?,AN??表示每臺飛機降落的時間。

第三行輸入?NN?個整數?B1,B2,?,BN?B1?,B2?,?,BN???表示每臺飛機起飛的時間。

輸出格式

輸出一個數字表示能讓所有飛機正常起降需要的最少軌道數。

樣例輸入1

3
1 1 2
2 2 3

樣例輸出1

樣例輸入2

4
1 5 4 3
4 6 10 4

樣例輸出2

樣例輸入3

3
1 4 3
2 6 5

樣例輸出3

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+1];int[] b=new int[n+1];Map<Integer,Integer> M=new HashMap<>();int ans=0;//每個數字的最大數量for(int i=1;i<=n;i++) {a[i]=scan.nextInt();if(M.get(a[i])==null) {M.put(a[i], 1);}else {M.put(a[i], M.get(a[i])+1);ans=Math.max(ans,M.get(a[i]));}}for(int i=1;i<=n;i++) {b[i]=scan.nextInt();if(M.get(b[i])==null) {M.put(b[i], 1);}else {M.put(b[i], M.get(b[i])+1);ans=Math.max(ans,M.get(b[i]));}}System.out.println(ans);scan.close();}
}

?5.回文字符串

問題描述

小藍最近迷上了回文字符串，他有一個只包含小寫字母的字符串?SS，小藍可以往字符串?SS?的開頭處加入任意數目個指定字符：?l、q、bl、q、b（ASCIIASCII?碼分別為：?108、113、98108、113、98）。小藍想要知道他是否能通過這種方式把字符串?SS?轉化為一個回文字符串。

輸入格式

輸入的第一行包含一個整數?TT，表示每次輸入包含?TT?組數據。

接下來依次描述?TT?組數據。

每組數據一行包含一個字符串?SS?。

輸出格式

輸出?TT?行，每行包含一個字符串，依次表示每組數據的答案。如果可以將?SS?轉化為一個回文字符串輸出?Yes，否則輸出?No。

樣例輸入

3
gmgqlq
pdlbll
aaa

樣例輸出

Yes
No
Yes

AC代碼

import java.util.*;
public class exercise1{private static boolean pd(String s) {int l=0,r=s.length()-1;while(l<=r) {char L=s.charAt(l);char R=s.charAt(r);if(L==R) {l++;r--;}else { //S的開頭處可加（左邊可加，右邊不可以）if(R=='l'||R=='q'||R=='b') {r--;}else {return false;}}}return true;}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int t=scan.nextInt();scan.nextLine();for(int i=1;i<=t;i++) {String s=scan.nextLine();if(pd(s))System.out.println("Yes");else System.out.println("No");}scan.close();}
}

6.七夕節之通訊

問題描述

小藍需要通過每個地區的通信裝置才能與其他地區聯系。現在每個地區被抽象為一個點，按照?1,2,...,n1,2,...,n?標號。在線路完好的情況下，小藍可以從第一個點按順序依次聯系到第?nn?個點，即?[1?2?...?n][1?2?...?n]。但是由于地震、暴雨等自然災害的影響，可能部分點的通信裝置被破壞。

例如當小藍處在?55?號點時，如果僅有?33?號點被破壞，其他點正常，那么小藍只能聯絡到?[4,n][4,n]?號點，即?[1?2,4?5?n][1?2,4?5?n]。當某個地區的通信裝置被自然災害破壞時，工作人員也會盡力搶修。

現在給定?qq?次操作，每次操作為破壞點、恢復點和查詢當前點可以聯絡多少個點（包括自身在內）進行通訊，請你輸出對應的查詢結果。

注意：初始狀態時，所有通訊點均為正常通訊點。

輸入格式

輸入共?q+1q+1?行：

第一行為兩個正整數?n,qn,q，依次表示通訊點數量和操作次數。

接下來?qq?行，每行兩個正整數?ins、xins、x。當?ins==0ins==0?時，若點?xx?為正常通訊點，則破壞該點為中斷點；若?xx?為中斷點，則恢復該點為正常通訊點。當?ins==1ins==1?時，查詢點?xx?可以至多通訊多少個點。

輸出格式

輸出所有?ins==1ins==1?時的查詢結果，結果按查詢先后順序依次輸出，結果僅包含一個整數且獨占一行。

樣例輸入

樣例輸出

AC代碼

import java.util.*;
public class exercise1{private static void update(int x) {}public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int q=scan.nextInt();Set<Integer>s =new TreeSet<>();//TreeSet自動升序，去重復元素for(int i=1;i<=q;i++) {int ins=scan.nextInt();int x=scan.nextInt();if(ins==0) {if(s.contains(x))s.remove(x);else s.add(x);}else {if(s.contains(x)) {System.out.println(0);continue;}else {int last=0,next=0;for(int u:s) {if(x<u) {next=u;//只要找到離x最近的nextbreak;}last=u;}if(next==0) {System.out.println(n-last);}else {System.out.println(next-last-1);}}}}scan.close();}
}

7.蛋糕盛宴

問題描述

在一個奇幻的游戲世界中，你作為勇敢的冒險者，來到了一個神秘的蛋糕王國。這個王國以美味的蛋糕聞名于世，而你正準備挑戰一個有趣的任務。

在王國的宮殿里，有一個特殊的矩形蛋糕盤子，它的大小為?n×mn×m。你的任務是在這個盤子里放置盡可能多的半徑為?rr?的圓形蛋糕，但是要注意，蛋糕的每一部分都不能超出盤子的邊界。

現在，請你告訴我，在這個挑戰中，你能最多放置多少個圓形蛋糕？

輸入格式

第一行輸入三個整數?n,m,rn,m,r，表示蛋糕盤子的大小和圓形蛋糕的半徑，其中?1≤n,m,r≤1001≤n,m,r≤100。

輸出格式

輸出僅一行，包含一個整數，表示你能放置的蛋糕的最大數量。

樣例輸入

1 2 3

樣例輸出

AC代碼

import java.util.*;
public class exercise1{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int r=scan.nextInt();System.out.println((n/(2*r))*(m/(2*r)));scan.close();}
}

?8.藍橋商場【算法賽】

問題描述

隨著雙十一的來臨，藍橋商場迎來了一場狂歡，共有?nn?家店鋪開展了免費試吃活動。

活動結束后，每家店鋪都還剩下一些試吃食物，第?ii?家店鋪剩下?aiai??份食物未被消耗完。

商場保安小藍接到指令要處理這些剩余食物，但他覺得浪費太可惜。因此，他決定親自吃完這些食物。每分鐘，小藍可以選擇以下操作之一：

選擇一家仍有剩余食物的店鋪，吃掉其中的一份食物。在下一分鐘，小藍不能再選擇同一家店鋪的食物。
休息，不吃任何食物。

請問，小藍需要多少分鐘才能吃完所有店鋪剩余的食物呢？

輸入格式

第一行輸入一個整數?n(1≤n≤105)n(1≤n≤105)?表示店鋪的數量。

第二行輸入?nn?個整數?a1,a2,a3,?,an(1≤ai≤105)a1?,a2?,a3?,?,an?(1≤ai?≤105)?表示每家店鋪剩余的食物數量。

輸出格式

輸出一個整數表示答案。

樣例輸入

3
1 1 3

樣例輸出

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+1];int maxx=0;int sum=0;for(int i=1;i<=n;i++) {a[i]=scan.nextInt();sum+=a[i];maxx=Math.max(a[i],maxx);}int num=maxx-(sum-maxx);if(num>1) {sum+=num-1;}System.out.println(sum);scan.close();}
}

?9.最優操作

問題描述

有一個包含?nn?個元素的數組?aa?，我們將對其進行?mm?次操作。mm?次操作可以按任意順序執行。每次操作給你兩個整數?xx?和?yy，你需要在數組中選擇?0～x0～x?個數，將它們永久變成?yy?。完成所有操作后，請問數組的元素和最大可能是多少。

輸入格式

第一行包含兩個整數?nn?和?mm?，表示數組的元素個數和操作次數。

第二行包含?nn?個整數，表示數組?aa?的元素。

接下來?mm?行，每行兩個整數，表示操作中的?xx?和?yy?。

輸出格式

輸出一個整數，表示操作完成后，數組的最大元素和。

樣例輸入

樣例輸出

AC代碼

import java.util.*;
public class exercise1{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[] a=new int[n];//優先隊列默認最小堆，堆頂為最小值PriorityQueue<Integer>q =new PriorityQueue<>();//最大堆PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());long sum=0;for(int i=0;i<n;i++) {a[i]=scan.nextInt();sum+=a[i];q.add(a[i]);}for(int i=0;i<m;i++) {int x=scan.nextInt();int y=scan.nextInt();while(x>0) {if(q.peek()<y) {sum-=q.poll();q.add(y);sum+=y;}else {break;}x--;}}System.out.println(sum);scan.close();}
}

10.神秘括號匹配之謎

問題描述

在神奇的魔法大陸中，勇敢的冒險者小藍和他的伙伴們進入了一座神秘的迷失森林。這個森林被古老的魔法所籠罩，隱藏著許多謎題和危險。小藍希望通過解決這些謎題，找到通往寶藏的路徑。

在迷失森林的某個地方，小藍發現了一塊神秘的石碑。石碑上刻有一串由括號組成的神秘字符串，只包含?(?和?)?兩種字符。小藍相信這個字符串中蘊含著通往寶藏的線索。他發現，只有當括號字符能夠正確匹配時，才能解開謎題。

括號的匹配定義如下：對于每個?(，必須找到與之對應的?)。例如，對于字符串?(())?和?()()，都具有匹配的括號對，數量均為?22。

小藍希望知道在這串神秘字符串中，最多能夠匹配多少個括號對。請你幫助小藍解決這個謎題。

輸入格式

第一行輸入一個整數?nn（1≤n≤1041≤n≤104），表示字符串的長度。

第二行輸入一個長度為?nn?的字符串?ss，字符串中只包含?(?和?)?兩種字符。

輸出格式

輸出僅一行，包含一個整數，表示在字符串中最多能夠匹配的括號對數量。

樣例輸入

5
(()))

樣例輸出

AC代碼

import java.util.*;
public class exercise1{public static void main(String[] args) {Scanner scan = new Scanner(System.in);int n=scan.nextInt();scan.nextLine();String s=scan.nextLine();//new Queue<>()不行，Queue是一個接口Queue<Character>q=new LinkedList<>();int ans=0;for(int i=0;i<s.length();i++) {if(s.charAt(i)=='(') {q.add('(');}else {if(q.size()>0) {q.poll();ans++;}}}System.out.println(ans);scan.close();}
}