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;
}
}