31.牛牛與切割機
有一個序列 a1,a2,...,ana_1,a_2,...,a_na1?,a2?,...,an? ， 牛牛將對這個序列切割一刀（劃分分成兩個不相交的非空序列，一個序列為 a1,...,apa_1,...,a_pa1?,...,ap?，另一個序列為 ap+1,...,ana_{p+1},...,a_nap+1?,...,an?），牛牛切割的代價為兩個序列元素和的乘積。牛牛想知道切割代價最小是多少。
時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 256M，其他語言512M
輸入描述：
輸出描述：
輸出一個整數表示切割代價最小是多少。
示例1
輸入例子：
5
1 2 3 4 5
輸出例子：
14
例子說明：
序列被劃分為1 和 2 3 4 5，右邊和為 14。
示例2
輸入例子：
4
2 1 3 4
輸出例子：
16
例子說明：
序列被劃分為 2 和 1 3 4。
解決方法
讀題后發現應該使用前綴和來解決。
-
預處理：計算前綴和與后綴和
- 前綴和數組
L：L[i]表示數組前i+1個元素的和（即nums[0] + nums[1] + ... + nums[i]）。 - 后綴和數組
R：R[i]表示數組從i到末尾的元素和（即nums[i] + nums[i+1] + ... + nums[n-1]）。
通過預處理，可在
O(1)時間內獲取任意分割點的兩部分元素和。 - 前綴和數組
-
遍歷所有分割點，計算最小乘積
對于每個可能的分割點i（將數組分為[0, i]和[i+1, n-1]），兩部分的和分別為L[i]和R[i+1]，乘積為L[i] * R[i+1]。遍歷所有分割點，記錄最小乘積即可。
import java.util.Scanner;// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int[] nums = new int[n];for(int i = 0;i<n;i++){nums[i] = in.nextInt();}long[] L = new long[n];long[] R = new long[n];L[0] = nums[0];R[n-1]=nums[n-1];for(int i = 1;i<n;i++){L[i] = L[i-1]+nums[i];}for(int i = n-2;i>=0;i--){R[i] = R[i+1]+nums[i];}long res = Long.MAX_VALUE;for(int i = 0;i<n-1;i++){long curres = L[i]*R[i+1];res= Math.min(res,curres);}System.out.println(res);}
}
32.字符串排序
給定 nnn 個字符串，請你對這 nnn個字符串按照以下規則從小到大排序。
對于任意兩個字符串 sss 和 ttt ，在排序后應當滿足：
- 若 s是 t 的一個前綴，則 s 在排序后的下標小于等于 t的在排序后的下標。
- 若存在整數 i ，使得 s 的前 i?1 個字符和 t 的前 i?1 個字符相同，且s 和 t 的第 i個字符不同，則比較第 i個字符的大小關系（字符的大小關系順序由輸入數據給出）。若 s 的第i個字符小于等于 t的第 i個字符，則 s 在排序后的下標小于等于 t 的在排序后的下標。
容易發現，上述排序方法的排序結果是唯一的。
時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 256M，其他語言512M
輸入描述：
第一行輸入一個字符串，包含 26 個互不相同的小寫字母。記 rank(c) 表示字母c 是該字符串的第rank(c)個字符，則字母 a小于等于字母b當且僅當rank(a)≤rank(b) 。第二行輸入一個整數(1≤n≤1000) ，表示待排序字符串的數量。接下來n行，每行一個僅包含小寫字母的字符串si(|si|≤1000)，表示一個待排序的字符串。
輸出描述：
按照排序后字符串位置下標從小到大的順序輸出n 行，每行一個字符串，表示排序的結果。
示例1
輸入例子：
abcdefghijklmnopqrstuvwxyz
3
aaa
aac
aaaa
輸出例子：
aaa
aaaa
aac
示例2
輸入例子：
zyxwvutsrqponmlkjihgfedcba
3
aaa
aac
aaaa
輸出例子：
aac
aaa
aaaa
解決方法
-
建立優先級映射：用哈希表
mp存儲每個字符對應的優先級（索引值），索引越小優先級越高（例如priorityStr為"bac"時，'b'優先級為 0，'a'為 1，'c'為 2）。 -
自定義排序規則：通過Collections.sort
結合比較器，按照以下邏輯排序字符串：
- 逐字符比較兩個字符串，找到第一個不同的字符，根據它們在哈希表中的優先級值決定順序（優先級高的字符所在字符串排前面）。
- 若較短字符串是較長字符串的前綴（如
"abc"和"abcd"），則較短字符串排前面。
import java.util.Scanner;
import java.util.*;// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String priorityStr = sc.nextLine();int n = Integer.parseInt(sc.nextLine());Map<Character,Integer> mp = new HashMap<>();for(int i = 0;i<priorityStr.length();i++){mp.put(priorityStr.charAt(i),i);}List<String> strs = new ArrayList<>();for(int i = 0;i<n;i++){strs.add(sc.nextLine());}Collections.sort(strs,(a,b)->{int an = a.length();int bn = b.length();int minLen = Math.min(an,bn);for(int i = 0;i<minLen;i++){char cA = a.charAt(i);char cB = b.charAt(i);if(cA != cB){return mp.get(cA)-mp.get(cB);}}return a.length()-b.length();});for(String str: strs){System.out.println(str);}}
}33.牛牛的糖果樹
牛牛的朋友送了她一棵節點數為 nn的糖果樹（1號點為根節點），樹上的每個糖果都有一個顏色。
牛牛吃糖果有一個習慣，她每次都會吃掉一整個子樹的糖果，她喜歡與眾不同，所以每次吃之前她都會把出現次數最多的顏色的糖果扔掉（可能有多個出現次數最多的顏色，此時要全部扔掉），她可以選擇任意一棵子樹吃掉，但她只能吃一次，因此他想知道她一次能吃到的所有糖果的顏色的異或和最大是多少（如果吃到了多個顏色相同的糖果，也需要做多次異或），你能幫幫她嗎？
時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 256M，其他語言512M
輸入描述：
第一行一個整數n(1≤n≤1000)。表示樹的節點數量。
第二行個整數ai(1≤ai≤1000)，表示節點i的顏色。
接下來n-1行，每行兩個整數u,v,表示節點u和節點v之間有一條邊。
輸出描述：
輸出僅有一行，一個整數表示她一次能吃到的糖果的顏色的異或和最大值。
示例1
輸入例子：
4
1 2 3 4
1 2
2 3
2 4
輸出例子：
0
例子說明：
四個節點顏色各不相同。吃掉任意子樹都會在吃之前把所有糖果扔掉，因此結果為0。
示例2
輸入例子：
4
1 1 2 2
1 2
2 3
2 4
輸出例子：
1
例子說明：
吃掉以節點3或節點4為根的子樹都只有一個節點，結果都為0，以1為根節點時顏色為1和顏色為2的節點數量都為2，因此結果也為0。吃掉以2為根的子樹時節點3和節點4顏色都為2被刪除，結果為節點2的顏色1。
解決方法
-
樹結構構建：將輸入的無向邊轉換為有明確父子關系的樹結構（通過 DFS 確定每個節點的子節點）。
-
子樹遍歷與統計
：對每個節點為根的子樹，通過 DFS 統計：
- 子樹中每種顏色的出現次數；
- 子樹所有顏色的總異或和。
-
計算有效異或和：對每個子樹，找出出現次數最多的顏色，排除它們的異或貢獻后，得到剩余顏色的異或和，記錄最大值。
import java.util.Scanner;
import java.util.*;
import java.io.*;// 注意類名必須為 Main, 不要有任何 package xxx 信息
public class Main {static List<List<Integer>> children ;static int[] colors;public static void main(String[] args) throws IOException{// 1. 讀取顏色，各邊構成無向圖/鄰接表BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int n = Integer.parseInt(br.readLine());colors = new int[n+1];StringTokenizer st = new StringTokenizer(br.readLine());for(int i = 1;i<=n;i++){colors[i] = Integer.parseInt(st.nextToken());}List<List<Integer>> adj = new ArrayList<>();for(int i = 0;i<=n;i++){adj.add(new ArrayList<>());}for(int i = 0;i<n-1;i++){st = new StringTokenizer(br.readLine());int u = Integer.parseInt(st.nextToken());int v = Integer.parseInt(st.nextToken());adj.get(u).add(v);adj.get(v).add(u);}// 2. 建樹children = new ArrayList<>();for(int i = 0;i<=n;i++){children.add(new ArrayList<>());}boolean[] visited = new boolean[n+1];buildTree(1,-1,adj,visited);// 3. 遍歷每個子節點，統計最大異或數int res = 0;for(int i = 1;i<=n;i++){int[] colorCount = new int[1001];int curXor = dfs(i,colorCount);// 計算要排除的顏色int maxCount = 0;for(int j = 1;j<=1000;j++){maxCount = Math.max(maxCount,colorCount[j]);}int exclueXor = 0;for(int c = 1;c<=1000;c++){if(colorCount[c]==maxCount){if(colorCount[c]%2==1){exclueXor^=c;}}}res = Math.max(res,curXor^exclueXor);}System.out.println(res);}static void buildTree(int node,int parent,List<List<Integer>> adj,boolean[] visited){visited[node] = true;for(int neighbor: adj.get(node)){if(!visited[neighbor]&&neighbor != parent){children.get(node).add(neighbor);buildTree(neighbor,node,adj,visited);}}}static int dfs(int i,int[] colorsCount){int color = colors[i];colorsCount[color]++;int curXor = color;for(int child:children.get(i)){curXor ^= dfs(child,colorsCount);}return curXor;}}
