1.作弊

溪染：六王畢，四海一；蜀山兀，阿房出。覆壓三百余里，隔離天日。驪山北構而西折，直走咸陽。二川溶溶，流入宮墻。五步一樓，十步一閣；廊腰縵回，檐牙高啄；各抱地勢，鉤心斗角……

叁秋：還在背《阿房宮賦》啊。

溪染：（停下背書）明天就要測試了，難道不背？

叁秋：什么？明天要測試？我現在抱佛腳還來得及嘛？

溪染：也就十來篇文言文而已。哦，你比較笨，那估計來不及了

叁秋：（沉默幾秒）救救孩子吧！

溪染：我想想辦法，我把文言文先換成拼音，然后在考場用動作語言傳給你怎么樣？

叁秋：什么動作語言？

溪染：我們先規定一個規則好了，我用‘點頭’和‘搖頭’向你傳遞信息。

叁秋：然后呢?

溪染：比如用‘點頭-搖頭’代表‘a’，用‘點頭-點頭’代表‘b’。

叁秋：我知道了！‘c’就用‘點頭-點頭-點頭’表示

溪染：沒救了，你是真的傻！如果這樣，那我‘點頭-點頭-點頭-點頭-點頭-點頭’表示什么？

叁秋：‘bbb’可以，‘cc’也行！！

溪染：對的，這樣的規則就有歧義了，所以我們定義的任意2個規則，一個規則都不能是另一個的前綴，更不能相同！

叁秋：那這還不簡單！我‘a’用‘點頭-搖頭’表示，‘b’用‘點頭-點頭-搖頭’表示，‘c’用‘點頭-點頭-點頭-搖頭’表示，以此類推！

溪染：用你這個規則，我脖子可能就不在了！

溪染：我們應該找到一個規則，讓我‘點頭’and‘搖頭’的次數和最少，這樣的話即可以快速傳遞信息，被監考老師發現的幾率也小—些。

叁秋：那我們改怎么規定規則呢？

溪染：現在我們把文言文轉為拼音先

（過了一會兒）

溪染：我們已經知道到時候我該給你傳遞的信息了，我們稍加計算一下，就可以找到最好的規則了

叁秋：那怎么計算呢?

溪染：我都為你付出這么多了，怎么找到最好的規則就靠你自己了

（又過了一會兒）

叁秋實在不知道怎么計算，于是找到了你

輸入描述

一行字符串S，(1≤|S|≤5×10^6)，表示需要傳達的信息，有可能是文言文拼音，S中僅包含小寫英文字母。

輸出描述

僅一行一個正整數表示問題的答案ans，表示傳達信息所需最少的‘點頭’and‘搖頭’的次數之和。

示例1

輸入

aaaaaa

輸出

6

說明

‘a’用‘點頭’代表即可

示例2

輸入

abcabc

輸出

10

說明

‘a’用‘點頭’代表 ‘b’用‘搖頭-點頭’代表 ‘c’用‘搖頭-搖頭’代表

示例3

輸入

havefuninthegame

輸出

54

說明

解釋那么長，這點地方夠嗎？

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String s = sc.nextLine();int[] freq = new int[26]; // 統計每個小寫字母的頻率// 計算每個字符的出現頻率for (char c : s.toCharArray()) {freq[c - 'a']++;}// 收集所有非零頻率List<Integer> frequencies = new ArrayList<>();for (int count : freq) {if (count > 0) {frequencies.add(count);}}// 特殊情況：只有一種字符if (frequencies.size() == 1) {System.out.println(frequencies.get(0));return;}// 使用優先隊列（最小堆）構建哈夫曼樹PriorityQueue<Integer> minHeap = new PriorityQueue<>(frequencies);int totalActions = 0;// 合并節點直到堆中只剩一個節點while (minHeap.size() > 1) {int first = minHeap.poll();int second = minHeap.poll();int sum = first + second;totalActions += sum;minHeap.add(sum);}System.out.println(totalActions);}
}

2.牛牛的數組匹配

牛牛剛學會數組不久，他拿到兩個數組a和b，詢問b的哪一段連續子數組之和與數組a之和最接近。如果有多個子數組之和同樣接近，輸出起始點最靠左的數組。

輸入描述

第一行輸入兩個正整數n和m，表示數組a和b的長度。第二第三行輸入n個和m個正整數，表示數組中a和b的值。

輸出描述

輸出子數組之和最接近a的子數組。

示例1

輸入

2 6

30 39

15 29 42 1 44 1

輸出

29 42

示例 2

輸入

6 1

50 47 24 19 46 47

2

輸出

2

import java.util.*;public class Main{public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 讀取數組a和b的長度int n = scanner.nextInt();int m = scanner.nextInt();// 讀取數組a并計算其總和int[] a = new int[n];int sumA = 0;for (int i = 0; i < n; i++) {a[i] = scanner.nextInt();sumA += a[i];}// 讀取數組b并計算前綴和int[] b = new int[m];for (int i = 0; i < m; i++) {b[i] = scanner.nextInt();}// 計算前綴和，prefixSum[0] = 0, prefixSum[1] = b[0], prefixSum[2] = b[0]+b[1], etc.long[] prefixSum = new long[m + 1];for (int i = 0; i < m; i++) {prefixSum[i + 1] = prefixSum[i] + b[i];}int bestStart = 0;int bestEnd = 0;long minDiff = Long.MAX_VALUE;// 遍歷所有可能的起始位置for (int i = 0; i < m; i++) {// 目標值：sumA + prefixSum[i]long target = sumA + prefixSum[i];// 二分查找最接近目標值的結束位置int left = i + 1;int right = m;int j = i + 1;  // 默認結束位置while (left <= right) {int mid = left + (right - left) / 2;if (prefixSum[mid] == target) {j = mid;break;} else if (prefixSum[mid] < target) {j = mid;left = mid + 1;} else {right = mid - 1;}}// 檢查j和j+1兩個位置，找到更接近目標值的int candidates[] = {j, j + 1};for (int k : candidates) {if (k > m) continue;long currentSum = prefixSum[k] - prefixSum[i];long currentDiff = Math.abs(currentSum - sumA);// 更新最佳子數組if (currentDiff < minDiff ||(currentDiff == minDiff && i < bestStart)) {minDiff = currentDiff;bestStart = i;bestEnd = k - 1;  // 轉換為數組b的索引}}}// 輸出最佳子數組for (int i = bestStart; i <= bestEnd; i++) {System.out.print(b[i]);if (i < bestEnd) {System.out.print(" ");}}System.out.println();}
}

3.牛牛的四葉玫瑰數

牛牛最近學了水仙花數，但是他并不喜歡水仙花，因此他準備算出[l,r]區間內的四葉玫瑰數。

四葉玫瑰數：一個數的四個位置的數字的四次方加起來等于這個四位數本身的數。

輸入描述

第一行輸入兩個正整數l，r，表示閉區間的兩頭r<=10000

輸出描述

輸出區間內的四葉玫瑰數，保證至少有一個

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);// 讀取區間范圍int l = scanner.nextInt();int r = scanner.nextInt();scanner.close();// 遍歷區間內的每個數，檢查是否為四葉玫瑰數for (int num = l; num <= r; num++) {// 四葉玫瑰數一定是四位數if (num < 1000 || num > 9999) {continue;}// 分解數字的四個位int thousands = num / 1000;int hundreds = (num % 1000) / 100;int tens = (num % 100) / 10;int units = num % 10;// 計算四個位的四次方之和int sum = (int)(Math.pow(thousands, 4) + Math.pow(hundreds, 4) +Math.pow(tens, 4) + Math.pow(units, 4));// 檢查是否等于原數if (sum == num) {System.out.println(num);}}}
}