十五屆藍橋杯省賽Java B組

第一題：報數

📚

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);long result = 202420242024L / 2 * 24;//思想：奇數位都是20的倍數，偶數位都是24的倍數，可知202420242024的一半為奇數，第202420242024位除以2乘以24就能得到答案//舉個例子：第4位是第2個24的倍數，第6位是第3個24的倍數......那第202420242024位就是第101210121012個24的倍數，//所以答案就是：202420242024 / 2 * 24System.out.println(result);scan.close();}
}

主要是找規律，硬解很難解出來。

第二題：類斐波那契數

因為是找最大，所以逆序遍歷會快點，第一個符合條件的數就是答案。

我的暴力解法，比賽不會那只能放在一邊讓他跑了，按道理來說是能跑出來的。

package test;import javax.swing.*;
import java.util.*;public class Main {static int N = 10000000;static int[] a = new int[20];static long[] b = new long[N];public static void main(String[] args) {Scanner sc = new Scanner(System.in);for (int i = N; i >= 197; i--) {if(check(i)){System.out.println(i);break;}else {System.out.println(i);}}}// 檢查是否是 類斐波那契 循環數static boolean check(int x) { // num是位數String str = x + "";int len = str.length();for (int i = 0; i < len; i++) {b[i + 1] = str.charAt(i) - '0';}for (int i = len + 1; b[i - 1] < x; i++) {b[i] = dfs(i);
//            System.out.println(" i:"+i);
//            System.out.println(b[i]);if( b[i] == x) return true;if( b[i] > x) return false;}return false;}// dfs遞歸static long dfs(int x){if(x == 1) return b[1];if(x == 2) return b[2];if(x == 3) return b[3];return dfs(x-1) + dfs(x - 2) + dfs(x - 3);}
}

📚法一

import java.util.*;public class Main {static int N = 10000000;public static void main(String[] args) {Scanner sc = new Scanner(System.in);for (int i = N; i >= 197; i--) {if(check(i)){System.out.println(i);break;}}}static boolean check(int x){String str = x + "";// 獲取位數int len = str.length();// 數組大小為len就夠用了int[] dp = new int[len];// 將 x 每一位都拆出來for (int i = 0; i < len; i++) {dp[i] = str.charAt(i) - '0';}// 數組求和int sum = 0;for (int i = len; sum < x ; i++) {sum = Arrays.stream(dp).sum(); // 數組求和，注意語法dp[i % len] = sum; // 后面用不到的下標元素 進行替換}return sum == x;  // 兩種結果：=x返回true，>x返回false}
}

每次求和其實只用到len個元素，所以可以對后續用不到的元素進行替換。

📚法二：

import java.util.*;public class Main {static int N = 10000000;public static void main(String[] args) {Scanner sc = new Scanner(System.in);for (int i = N; i >= 197; i--) {if(check(i)){System.out.println(i); // 7913837break;}}}// 檢查是否是 類斐波那契 循環數static boolean check(int x) { // num是位數String str = x + "";int len = str.length();int sum = 0;ArrayList<Integer> a = new ArrayList<>();for (int i = 0; i < len; i++) {int num = str.charAt(i) - '0';a.add(num);   // [1,9,7]sum += num;}//上面的這個循環究竟是在干什么事情：下面的這個以1234為例子說明，方便理解//列表 a 存儲了整數 1234 的各個數位數字 [1, 2, 3, 4]，// 變量 sum 的值為 10，即整數 1234 各個數位數字的總和。a.add(sum);// 此時變成了[1, 2, 3, 4，10]if(sum == x) return true;while(sum < x){//乘以2減去這個里面的第一個元素就是這個類斐波那契數列的規律，避免使用純粹的數學方法計算sum = sum * 2 - a.get(0); a.remove(0);a.add(sum);if(sum == x) return true;}return false;}
}

思想：要求第k+1位以后的數只需將k乘以2減去這個里面的第一個元素就是這個類斐波那契數列的規律，避免使用純粹的數學方法計算。

第三題：分布式隊列

👇寫成這樣有9個樣例過不了，因為沒有考慮副隊列不超過主隊列。

import java.util.*;public class Main {static int N = 2010;static int INF = 100005;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int[] a = new int[n];while(sc.hasNext()){String str = sc.next();if(str.equals("add")){int num = sc.nextInt();a[0] ++;}else if (str.equals("sync")){int num = sc.nextInt();a[num] ++;} else if (str.equals("query")) {int ans = INF;for (int i = 0; i < n; i++) {ans = Math.min(ans,a[i]);}System.out.println(ans);}}}
}

📚分布式隊列

第四題：食堂

import java.util.*;public class Main {static int N = 2010;static int INF = 100005;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int q = sc.nextInt();while(q-->0) {int a2 = sc.nextInt();int a3 = sc.nextInt();int a4 = sc.nextInt();int b4 = sc.nextInt();int b6 = sc.nextInt();int sum = 0;// 滿座 匹配4人寢坐4人桌while(a4 != 0 && b4 != 0){a4 --;b4 --;sum += 4;}// 滿座 匹配2x2人寢坐4人桌while(a2 != 0 && b4 != 0){a2 = a2 - 2;b4 --;sum += 4;}// 滿座 匹配2+4人寢坐6人桌while(a2 != 0 && a4 != 0 && b6 != 0){a2 --;a4 --;b6 --;sum += 6;}// 滿座 匹配2x3人寢坐6人桌while(a3 != 0 && b6 != 0){a3 = a3 - 2;b6--;sum += 6;}// 滿座 匹配3x2人寢坐6人桌while(a2 != 0 && b6 != 0){a2 = a2 - 3;b6 --;sum += 6;}// 空1座 匹配3人寢坐4人桌while(a3 != 0 && b4 != 0){a3--;b4--;sum += 3;}// 空1座 匹配3+2人寢坐6人桌while(a3 != 0 && a2 != 0 && b6 != 0){a3--;a2--;b6--;sum += 5;}// 空2座 匹配2人寢坐4人桌while(a2 != 0 && b4 != 0){a2--;b4--;sum += 2;}// 空2座 匹配4人寢坐6人桌while(a4 != 0 && b6 != 0){a4--;b6--;sum += 4;}// 空2座 匹配2x2人寢坐6人桌while(a2 != 0 && b6 != 0){a2 = a2 - 2;b6--;sum += 4;}// 空3座 匹配3人寢坐6人桌while(a3 != 0 && b6 != 0){a3--;b6--;sum += 3;}// 空4座 匹配2人寢坐6人桌while(a2 != 0 && b6 != 0){a2--;b6--;sum += 2;}System.out.println(sum);}}
}

??以上寫法還有點小錯誤，b!=0是可以的，但是a不能寫成a!=0。例如滿座 匹配2x2人寢坐4人桌，要確保a2宿舍有兩個，所以不能寫成a2!=0，要寫成a2 >= 2。

📚

import java.util.*;public class Main {static int N = 2010;static int INF = 100005;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int q = sc.nextInt();while(q-->0) {int a2 = sc.nextInt();int a3 = sc.nextInt();int a4 = sc.nextInt();int b4 = sc.nextInt();int b6 = sc.nextInt();int sum = 0;// 滿座 匹配4人寢坐4人桌while(a4 >= 1 && b4 > 0){a4 --;b4 --;sum += 4;}// 滿座 匹配2x2人寢坐4人桌while(a2 >= 2 && b4 > 0){a2 = a2 - 2;b4 --;sum += 4;}// 滿座 匹配2+4人寢坐6人桌while(a2 >= 1 && a4 >= 1 && b6 > 0){a2 --;a4 --;b6 --;sum += 6;}// 滿座 匹配2x3人寢坐6人桌while(a3 >= 2 && b6 > 0){a3 = a3 - 2;b6--;sum += 6;}// 滿座 匹配3x2人寢坐6人桌while(a2 >= 3 && b6 > 0){a2 = a2 - 3;b6 --;sum += 6;}// 空1座 匹配3人寢坐4人桌while(a3 >= 1 && b4 > 0){a3--;b4--;sum += 3;}// 空1座 匹配3+2人寢坐6人桌while(a3 >= 1  && a2 >= 1 && b6 > 0){a3--;a2--;b6--;sum += 5;}// 空2座 匹配2人寢坐4人桌while(a2 >= 1 && b4 > 0){a2--;b4--;sum += 2;}// 空2座 匹配4人寢坐6人桌while(a4 >= 1 && b6 > 0){a4--;b6--;sum += 4;}// 空2座 匹配2x2人寢坐6人桌while(a2 >= 2 && b6 > 0){a2 = a2 - 2;b6--;sum += 4;}// 空3座 匹配3人寢坐6人桌while(a3 >= 1 && b6 > 0){a3--;b6--;sum += 3;}// 空4座 匹配2人寢坐6人桌while(a2 >= 1 && b6 > 0){a2--;b6--;sum += 2;}System.out.println(sum);}}
}

🍎

能想出來貪心策略就不難。想不出來可以試著騙分👇

if(sum1 > sum2){sout(sum2)
}else if(sum1 <= sum2){sout(sum1)
}

第五題：最優分組

📚最優分組

思路是：要求 使用試劑最少 情況下的分組策略k -> 最少試劑是x -> 對每組k個寵物消耗試劑的情況分類 -> 求出期望公式 -> 特殊情況 k=1

關鍵是要求出期望公式，這題就好做了。另外還要想到k=1這個特殊情況，進行特判。所以這題難度挺大的。

第六題：星際旅行

📚星際旅行

第七題：LITS游戲

第八題：拼十字

📚拼十字
??考點總結：

1.數學+1
2.暴力 構造 枚舉 +1
3.模擬+1
4.貪心+1
5.數學 概率 期望 +1
6.Dijkstra 最短路問題 期望 +1
7.
8.樹狀數組 + 1