[第十六屆藍橋杯 JavaB 組] 真題 + 經驗分享

A：逃離高塔(AC)

這題就是簡單的簽到題，按照題意枚舉即可。需要注意的是不要忘記用long，用int的話會爆。

📖 代碼示例：

import java.io.*;
import java.util.*;
public class Main {public static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in = new Read();public static void main(String[] args) throws IOException{long sum = 0;for(long i = 1;i <= 2025;i++){long num = i * i * i;if(num % 10 == 3){sum++;}}System.out.println(sum);}
}
//快讀模板不必在意
class Read{StringTokenizer st = new StringTokenizer("");BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException{while(!st.hasMoreTokens()){st = new StringTokenizer(br.readLine());}return st.nextToken();}int nextInt() throws IOException{return Integer.parseInt(next());}long nextLong() throws IOException{return Long.parseLong(next());}double nextDouble() throws IOException{return Double.parseDouble(next());}
}

📕 答案：202

B：消失的藍寶(AC)

這題最開始嘗試用暴力枚舉，但后來跑了好長時間，又擴大了好多次范圍，還是沒能出結果，硬想了半天，覺得應該和最小公倍數有關：

要知道，要找到一個最小數，使得同時能被 a 和 b 整除，那么這個數就是 a 和?b 的最小公倍數。

題目中要求找到一個 n，滿足(n + a) % b == 0 && (n + b) % a == 0，那么只要我們找到 a 和 b 的最小公倍數 c，此時c滿足 c % a == c % b == 0。

那么因為 c % a == 0 可以知道 (c - a) % a == 0。
同理因為 c % b == 0 可以知道 (c - b) % b == 0。

假設現在我們有一個 n 滿足?(n + a) % b == 0 那么 (n + a) = (c - b)
同理 (n + b) % a == 0 那么 (n + b) = (c - a)

最終得到 n = c - a - b

📖 代碼示例：

import java.io.*;
import java.util.*;
public class Main {public static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in = new Read();public static void main(String[] args) throws IOException{long a = 20250412;long b = 20240413;System.out.println((a * b / gcd(a,b)) - a - b);}public static long gcd(long a,long b){return b == 0 ? a : gcd(b,a % b);}
}
class Read{StringTokenizer st = new StringTokenizer("");BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException{while(!st.hasMoreTokens()){st = new StringTokenizer(br.readLine());}return st.nextToken();}int nextInt() throws IOException{return Integer.parseInt(next());}long nextLong() throws IOException{return Long.parseLong(next());}double nextDouble() throws IOException{return Double.parseDouble(next());}
}

📕 答案：409876661809331

C：電池分組(AC)

該題考察的是對異或操作符的理解，題中的要求是給定一個數組，讓我們判斷，這個數組是否能夠分成兩部分，使得"兩部分的異或和相等"。

異或操作符：兩個數字，二進制位相同為0，否則為1。

我們得清楚，不管如何劃分數組，整個數組的"異或和"都是不變的，而如果數組能夠分成"兩個異或和相等的部分"，也就意味著，最后再將這兩部分的異或和進行異或，結果必然是等于0的。(數字相等，所有二進制位相同)

那么這兩部分異或和的異或，所得到的結果，代表什么呢？沒錯，代表整個數組的異或和。

那么也就是說：如果能找到這樣的兩部分，則代表整個數組的異或和一定為0。

反過來想，如果一個數組的異或和為0，是否就能代表一定存在這樣的兩部分呢？

是一定的。因為如果一個數組異或和為0，則代表最后的一步異或和，一定會是"兩部分數組的異或和"進行異或，并且"這兩部分的異或和一定相等"，否則就違背了"整個數組異或和為0"的前提了。

所以：如果整個數組異或和為0，則輸出"YES"，否則，輸出"NO"。

📖 代碼示例：

import java.io.*;
import java.util.*;public class Main {public static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in = new Read();public static void main(String[] args) throws IOException {int t = in.nextInt();while(t-- > 0){int n = in.nextInt();int[] arr = new int[n];for(int i = 0;i < n;i++){arr[i] = in.nextInt();}long sum = arr[0];for(int i = 1;i < n;i++){sum = arr[i] ^ sum;}System.out.println(sum == 0 ? "YES" : "NO");}}
}
class Read{StringTokenizer st = new StringTokenizer("");BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException{while(!st.hasMoreTokens()){st = new StringTokenizer(br.readLine());}return st.nextToken();}int nextInt() throws IOException{return Integer.parseInt(next());}long nextLong() throws IOException{return Long.parseLong(next());}double nextDouble() throws IOException{return Double.parseDouble(next());}
}

D：魔法科考試(AC)

該題考察的是"素數篩法"，這邊我采用的是最常用的"埃氏篩"，這題的數據范圍是：

所以說我們只需要篩到大于40000的范圍就好了，當然，即使這個范圍不大，不使用優化篩法的話肯定也還是會超時的。因為使用雙重for循環去檢查所有魔法組合就已經有O(n^2)了~

注意：1 + 6 和 3 + 4 和 4 + 3，這種結果相同的"魔法口訣"，算是同一個，不能重復計數，所以應該去重。

📖 代碼示例：

import java.io.*;
import java.util.*;public class Main {public static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in = new Read();public static int[] zhi = new int[50100];public static boolean[] check = new boolean[50100];public static HashSet<Integer> set = new HashSet<>();public static void main(String[] args) throws IOException {shai();int a = in.nextInt();int b = in.nextInt();int[] arr1 = new int[a + 1];int[] arr2 = new int[b + 1];for(int i = 0;i < a;i++){arr1[i] = in.nextInt();}for(int i = 0;i < b;i++){arr2[i] = in.nextInt();}int max = 0;for(int i = 0;i < a;i++){for(int j = 0;j < b;j++){int num = arr1[i] + arr2[j];if(num <= a + b && zhi[num] == 1){if(!set.contains(num)){set.add(num);max++;}}}}System.out.println(max);}public static void shai(){for(int i = 2;i < 50049;i++){//未被篩出if(!check[i]){//標記為質數zhi[i] = 1;//將i的倍數都篩出for(int j = i;j < 50049;j += i){check[j] = true;}}}}
}
class Read{StringTokenizer st = new StringTokenizer("");BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException{while(!st.hasMoreTokens()){st = new StringTokenizer(br.readLine());}return st.nextToken();}int nextInt() throws IOException{return Integer.parseInt(next());}long nextLong() throws IOException{return Long.parseLong(next());}double nextDouble() throws IOException{return Double.parseDouble(next());}
}

E：爆破

這題考察的應該是最小生成樹...俺不會，寫的dijkstra，運氣好的話希望能騙個一兩分吧...

F：數組翻轉(AC)

數據范圍：

我們先考慮暴力解法：

其實就是將所有可能的翻轉都嘗試一遍，這樣就能找到所有的情況，并且找出最大的。

但翻轉這個操作本身就是O(n)的，再加上嘗試所有范圍翻轉，就達到了O(n^3)，這是非常可怕的

(即使如此也能暴力掉20%，也就是3分，接近一道填空題的分數了~)

但實際上，我們并不需要進行"翻轉"這個操作，因為：

翻轉數組的目的是：得到可通過拼接得到的最長目標值。
而我們再想一下，如何能知道"可拼接得到的最長目標值串"呢？其實，就是找到整個數組中，"等于目標值的最長子串"和"等于目標值的第二長子串"進行拼接即可。

如何證明？其實很好想，不管如何選取范圍翻轉，我們都沒法改變范圍內數組的本質順序，也就是說，我們只能"選取部分進行拼接"，而每次拼接，肯定只能選到兩個子串拼接，如果想選三個，那么勢必會有兩個子串中有間隔。

所以，我們只需要找到"每個值對應數組中的第一長與第二長子串"，將長度相加后，進行求分數即可，最后找到"子串拼接后分數最高的值"，輸出即可。

import java.util.*;
import java.io.*;public class Main {public static PrintWriter pr = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in = new Read();public static void main(String[] args) throws IOException{int n = in.nextInt();int[] arr = new int[n + 1];HashSet<Integer> set = new HashSet<>();for(int i = 1;i <= n;i++){arr[i] = in.nextInt();set.add(arr[i]);}arr[0] = Integer.MAX_VALUE;HashMap<Integer,Integer> map1 = new HashMap<>();HashMap<Integer,int[]> map2 = new HashMap<>();int l = 1;int r = 1;while(r <= n){int len = map1.getOrDefault(arr[l],0);int newlen = 0;while(r <= n && arr[l] == arr[r]){newlen++;r++;}if(len < newlen){len = newlen;map1.put(arr[l],len);map2.put(arr[l],new int[]{l,r});}l = r;}HashMap<Integer,Integer> map3 = new HashMap<>();l = r = 1;//再次進行查找數組中的[第二長子串],跳過第一長子串即可while(r <= n){//為val = arr[l]的最長字串if(map2.get(arr[l])[0] == l){l = map2.get(arr[l])[1];r = l;continue;}int len = map3.getOrDefault(arr[l],0);int newlen = 0;while(r <= n && arr[l] == arr[r]){newlen++;r++;}if(len < newlen){len = newlen;map3.put(arr[l],len);}l = r;}long max = 0;for(int a:set){//有可能不存在第二長子串int len = map1.get(a) + map3.getOrDefault(a,0);long num = len * 1l * a;max = Math.max(max,num);}System.out.println(max);}
}
class Read{StringTokenizer st = new StringTokenizer("");BufferedReader br = new BufferedReader(new InputStreamReader(System.in));String next() throws IOException{while(!st.hasMoreTokens()) {st = new StringTokenizer(br.readLine());}return st.nextToken();}String nextLine() throws IOException{return br.readLine();}int nextInt() throws IOException{return Integer.parseInt(next());}long nextLong() throws IOException{return Long.parseLong(next());}double nextDouble() throws IOException{return Double.parseDouble(next());}
}