第十五届蓝桥杯大赛软件赛省赛Java研究生组
·
考点总结
填空题 1：劲舞团
- 考点：字符串处理、时间戳计算、连续匹配计数。
- 解题思路：通过比较输入的字符串和时间戳，判断连续匹配的次数，并更新最大匹配次数。
填空题 2：召唤数学精灵
- 考点：数学规律、因子分解、循环逻辑。
- 解题思路：通过去除数字中的所有2因子，判断最终是否为1来统计满足条件的数字数量。
大题 1：封闭图形个数（快速排序）
- 考点：快速排序算法、数组操作、权重计算。
- 解题思路：计算每个数字的权重，然后通过快速排序对数组进行排序。
大题 2：吊坠（最小生成树）
- 考点：最小生成树（贪心算法）、字符串处理、权重计算。
- 解题思路：将问题转化为最小生成树问题，通过贪心算法构建最小生成树，并计算总权重。
大题 3：挖矿（数轴问题）
- 考点：数轴上的动态规划、前缀和、贪心算法。
- 解题思路：通过维护正负轴的矿洞位置，利用前缀和快速计算矿石数量，并通过贪心算法枚举四种情况求解最大值。
大题 6：智力测试（组合数学）
- 考点：组合数学、前缀积、模逆元、二分查找。
- 解题思路：通过组合数学公式和模逆元优化计算，利用前缀积快速计算区间贡献，并通过二分查找定位权值。
最大异或节点（字典树 + 图论）
- 考点：字典树（Trie）、图论、异或操作。
- 解题思路：利用字典树存储权值，通过图的遍历动态维护邻接节点的权值，计算最大异或值。
植物生命力（树状数组 + DFS）
- 考点：树状数组、深度优先搜索（DFS）、区间统计。
- 解题思路：通过树状数组高效统计区间内的节点数量，结合DFS遍历树结构，统计满足条件的节点对数量。
填空 1 劲舞团
import java.util.Scanner; // 导入 Scanner 类，用于从控制台读取输入
import java.io.File; // 导入 File 类，虽然在这段代码中没有使用到，可能是多余的导入
import java.io.FileNotFoundException; // 导入 FileNotFoundException 类，用于处理文件未找到的异常，但在这段代码中未使用
public class Main {
public static void main(String[] args) {
String a1, a2; // 用于存储前一次和当前次输入的字符串 a
String b1, b2; // 用于存储前一次和当前次输入的字符串 b
long t1, t2; // 用于存储前一次和当前次输入的时间戳
int k = 0, max = 0; // k 用于记录当前连续匹配的次数，max 用于记录最大连续匹配次数
Scanner sc = new Scanner(System.in); // 创建 Scanner 对象，从控制台读取输入
// 先处理第一行输入
a1 = sc.next(); // 读取第一个字符串 a1
b1 = sc.next(); // 读取第一个字符串 b1
t1 = sc.nextLong(); // 读取第一个时间戳 t1
if (a1.equals(b1)) // 如果 a1 和 b1 相等
k++; // 增加连续匹配次数
// 如果还有输入，继续处理后续行
while (sc.hasNext()) { // 判断是否还有输入
a2 = sc.next(); // 读取当前行的字符串 a2
b2 = sc.next(); // 读取当前行的字符串 b2
t2 = sc.nextLong(); // 读取当前行的时间戳 t2
// 判断当前行是否满足条件
if (a2.equals(b2) && t2 - t1 < 1000) { // 如果 a2 和 b2 相等，并且时间差小于 1000 毫秒
k++; // 增加连续匹配次数
} else {
max = Math.max(max, k); // 更新最大连续匹配次数
k = a2.equals(b2) ? 1 : 0; // 如果 a2 和 b2 相等，重新开始计数，否则重置为 0
}
// 更新前一次的值为当前次的值，为下一次迭代做准备
a1 = a2;
b1 = b2;
t1 = t2;
}
// 输出最大连续匹配次数
System.out.println(max);
}
}
填空 2 召唤数学精灵
找规律
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
/*规律题思路：
1.除了1以外的奇数都符合 1=0+1但0不是正整数 3=1+2 5=2+3 规律明显
2.6=1+2+3 规律 6//2=3(奇数) 那么对于一个偶数除以2以后是奇数的也可以成立
(对除后的奇数加减一，得到连续的正整数相加 8//2=4就不行)
对于8：8//2=4 4//2=2 2//2=1；对于6：6//2=3 3%2!=0*/
Scanner scan=new Scanner(System.in);
int n=scan.nextInt(); // 读取测试用例的数量
int ans=0; // 初始化答案计数器
for(int i=1;i<=n;i++) {
Long j=scan.nextLong(); // 读取每个测试用例的数字
while(j%2==0&&j>1) { // 去除数字中的所有2因子
j/=2;
}
if(j==1) { // 如果去除所有2因子后，数字为1，则计数器加1
ans++;
}
}
System.out.println(ans); // 输出满足条件的数字的数量
}
}
大题 1 封闭图形个数 快速排序
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int a = sc.nextInt(); // 输入数组的大小
int[] sz1 = new int[a]; // 存储输入的整数
int[] sz2 = new int[a]; // 存储计算后的值，用于排序依据
int[] sz3 = {1, 0, 0, 0, 1, 0, 1, 0, 2, 1}; // 固定数组，用于计算每个数字的权重
// 读取输入的整数并存入 sz1
for (int i = 0; i < a; i++) {
sz1[i] = sc.nextInt();
}
// 计算 sz2 的值
for (int i = 0; i < a; i++) {
int c = 0; // 用于累加权重
// 遍历数字的每一位
for (int b = 1; b <= sz1[i]; b *= 10) {
// 根据 sz3 数组计算当前位的权重，并累加到 c
c = c + sz3[sz1[i] / b % 10];
}
sz2[i] = c; // 将计算结果存入 sz2
}
// 调用快速排序函数
dfs(0, a - 1, sz1, sz2);
// 输出排序后的 sz1 数组
for (int j = 0; j < a; j++) {
System.out.print(sz1[j] + " ");
}
}
// 快速排序函数
public static void dfs(int low, int high, int[] sz1, int[] sz2) {
if (low < high) { // 如果区间内有多个元素
int d = 0; // 用于记录分区点的位置
int a = low, b = high - 1; // 初始化左右指针
// 快速排序的分区过程
while (a < b) {
// 如果左指针的值大于基准值（sz2[high]），需要交换
if (sz2[a] > sz2[high] || (sz2[a] == sz2[high] && sz1[a] > sz1[high])) {
while (a < b) { // 在右指针找到合适的值进行交换
if (sz2[b] < sz2[high] || (sz2[b] == sz2[high] && sz1[b] < sz1[high])) {
// 交换 sz2 和 sz1 中的值
int c = sz2[b];
sz2[b] = sz2[a];
sz2[a] = c;
c = sz1[b];
sz1[b] = sz1[a];
sz1[a] = c;
a++; // 左指针右移
b--; // 右指针左移
break;
} else {
b--; // 右指针左移
}
}
} else {
a++; // 左指针右移
}
}
// 处理最后一个分区点
if (sz2[a] < sz2[high] || (sz2[a] == sz2[high] && sz1[a] < sz1[high])) {
// 如果左指针的值小于基准值，交换 a+1 和 high
int w = sz2[a + 1];
sz2[a + 1] = sz2[high];
sz2[high] = w;
w = sz1[a + 1];
sz1[a + 1] = sz1[high];
sz1[high] = w;
d = a + 1; // 分区点为 a+1
} else if (sz2[a] > sz2[high] || (sz2[a] == sz2[high] && sz1[a] > sz1[high])) {
// 如果左指针的值大于基准值，交换 a 和 high
int w = sz2[a];
sz2[a] = sz2[high];
sz2[high] = w;
w = sz1[a];
sz1[a] = sz1[high];
sz1[high] = w;
d = a; // 分区点为 a
} else {
d = a; // 如果相等，分区点为 a
}
// 递归处理左右子区间
dfs(low, d - 1, sz1, sz2);
dfs(d + 1, high, sz1, sz2);
}
}
}
大题 2 吊坠
转换为最小生成树问题
import java.util.ArrayList; // 导入ArrayList类，用于存储动态数组
import java.util.Scanner; // 导入Scanner类，用于从标准输入读取数据
// 1: 无需使用package声明包名
// 2: 类名必须为Main，不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in); // 创建Scanner对象，用于读取用户输入
// 读取输入数据
int n = scan.nextInt(); // 读取字符串的数量n
int m = scan.nextInt(); // 读取另一个参数m（未在代码中使用）
scan.nextLine(); // 跳过当前行的换行符
// 创建一个字符串数组，用于存储输入的n个字符串
String[] a = new String[n];
for (int i = 0; i < n; i++) {
String s = scan.nextLine(); // 逐行读取字符串
a[i] = s; // 将读取的字符串存入数组
}
// 创建一个二维数组，用于记录每对字符串之间的权重
int[][] weight = new int[n][n];
// 计算每对字符串之间的权重
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int k = weightCount(a[i], a[j]); // 调用weightCount函数计算权重
weight[i][j] = k; // 存储权重
weight[j][i] = k; // 由于权重是双向的，同时存储对称位置的权重
}
}
// 使用贪心算法构建最小生成树
int result = 0; // 初始化最小生成树的总权重为0
ArrayList<Integer> tree = new ArrayList<>(); // 用于存储已经加入树的节点
tree.add(0); // 将第一个节点（索引为0）加入树
ArrayList<Integer> node = new ArrayList<>(); // 用于存储尚未加入树的节点
// 将所有其他节点加入node列表
for (int i = 1; i < n; i++) {
node.add(i);
}
// 构建最小生成树的过程
while (node.size() != 0) { // 当还有未加入树的节点时，继续循环
int maxNode = 0; // 用于记录当前找到的最大权重边的节点
int maxEdge = 0; // 用于记录当前找到的最大权重边的权重
// 遍历未加入树的节点
for (int i : node) {
// 遍历已加入树的节点
for (int j : tree) {
if (weight[i][j] >= maxEdge) { // 如果找到更大的权重边
maxEdge = weight[i][j]; // 更新最大权重
maxNode = i; // 更新最大权重边对应的节点
}
}
}
// 将找到的最大权重边的节点加入树
node.remove((Integer) maxNode); // 从未加入树的节点列表中移除该节点
tree.add(maxNode); // 将该节点加入树
result = result + maxEdge; // 累加最大权重到总权重
}
// 输出最小生成树的总权重
System.out.print(result);
// 关闭Scanner对象
scan.close();
}
// 定义权重计算函数
public static int weightCount(String a, String b) {
// 将两个字符串各自拼接一次，用于后续查找子串
StringBuilder A = new StringBuilder(a + a);
StringBuilder B = new StringBuilder(b + b);
int k = a.length(); // 初始化最长公共子串长度为字符串长度
int len = k; // 用于记录当前查找的子串长度
while (k > 0) { // 从最长可能的子串长度开始递减查找
boolean flag = false; // 标志位，用于标记是否找到公共子串
for (int i = 0; i < len; i++) { // 遍历拼接后的字符串A
String s = A.substring(i, i + k); // 截取长度为k的子串
if (B.indexOf(s) != -1) { // 如果子串在B中存在
flag = true; // 设置标志位为true
break; // 跳出循环
}
}
if (flag) { // 如果找到公共子串
break; // 停止查找，返回当前子串长度
}
k--; // 如果未找到公共子串，递减子串长度
}
return k; // 返回最长公共子串的长度作为权重
}
}
大题 3 挖矿
矿洞位置是在数轴上且有正负之分，所以就要维护两个数组，下标表示位置，一个存储正轴位置的矿洞，一个存储负轴位置的矿洞，大小为10的6次方+1。 然后就是获取走过位置的矿石数，可以用前缀和进行求解，sum数组存放的就是从0走到该位置获取的矿石总数 知道走到哪个位置能获取的矿石总数后，就要考虑如何使挖矿数量最大化（是本题的难点），这题给了一个限定就是走m步能获取的最大矿石数量，同时由于每个矿洞只能挖一次，比如当你到-5的位置并且要返回到0点时消耗的步数为5 * 2 = 10得到的矿石数为sum2[5] 剩余的步数为m - 10。所以后面只需枚举四种情况并取最大值就行了。 1.一直往正轴方向走不回头 2,一直往负轴方向走不回头 3..先往正轴方向走然后回头 4.先往负轴方向走然后回头
import java.util.Scanner;
// 1: 无需package声明
// 2: 类名必须为Main，不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
// 定义数轴的长度为10^6（正方向和负方向的最大范围）
double length = Math.pow(10, 6);
// 创建两个数组，分别记录正方向和负方向的矿洞位置的矿石数量
int[] arr1 = new int[(int) (length + 1)]; // 正轴方向矿洞位置
int[] arr2 = new int[(int) (length + 1)]; // 负轴方向矿洞位置
// 读取输入
int n = scan.nextInt(); // 矿洞的数量
int m = scan.nextInt(); // 行走的最大距离
// 创建两个前缀和数组，分别用于记录正方向和负方向的矿石数量的前缀和
int[] sum1 = new int[m + 1]; // 正轴方向矿数前缀和数组
int[] sum2 = new int[m + 2]; // 负轴方向矿数前缀和数组
// 记录在位置0处的矿石数量
int place0 = 0;
// 遍历所有矿洞，根据位置更新矿石数量
for (int i = 0; i < n; i++) {
int place = scan.nextInt(); // 读取矿洞的位置
if (place > 0) { // 如果位置为正数
arr1[place]++; // 在正方向数组中对应的索引位置加1
} else if (place < 0) { // 如果位置为负数
arr2[-place]++; // 在负方向数组中对应的索引位置加1（取绝对值）
} else {
place0++; // 如果位置为0，则增加位置0的矿石数量
}
}
// 计算正方向和负方向的矿石数量的前缀和
for (int j = 1; j <= m; j++) {
sum1[j] = arr1[j] + sum1[j - 1]; // 正方向前缀和
sum2[j] = arr2[j] + sum2[j - 1]; // 负方向前缀和
}
// 初始化最大矿石数量
int maxNum = Math.max(sum1[m], sum2[m]); // 先求单向行走的最大矿石数量
// 枚举往返行走的情况
for (int k = 1; k * 2 <= m && k <= m; k++) {
// 枚举先向正方向走k步，再返回并走负方向m-2k步的情况
maxNum = Math.max(sum1[k] + sum2[m - k * 2], maxNum);
// 枚举先向负方向走k步，再返回并走正方向m-2k步的情况
maxNum = Math.max(sum2[k] + sum1[m - k * 2], maxNum);
}
// 输出最终的最大矿石数量，加上位置0的矿石数量
System.out.println(maxNum + place0);
// 关闭Scanner对象
scan.close();
}
}
大题 6 智力测试
解题思路
题目要求计算在给定的行和列的权值序列中，满足特定条件的路径数量。具体思路如下：
- 组合数学的应用：
-
- 行和列的权值序列是独立的，因此可以分别处理行和列的贡献，最后通过乘法原理合并结果。
- 对于每个查询，需要计算在行和列的权值序列中满足条件的路径数量。
- 处理相同权值的情况：
-
- 如果行或列的权值相同，但索引不同，说明路径无效，直接返回0。
- 如果权值相同且索引相同，则路径有效，但需要特殊处理。
- 利用前缀积快速计算区间贡献：
-
- 使用前缀积数组快速计算某个区间内权值的乘积。
- 通过模逆元计算区间乘积的逆元，从而得到区间内权值的组合贡献。
- 组合数的计算：
-
- 使用组合数公式 ( C(n, m) = \frac{n!}{m! \times (n - m)!} )。
- 通过模逆元优化计算，避免大数除法。
- 二分查找定位权值：
-
- 使用二分查找快速定位权值在有序序列中的位置。
- 计算行和列的区间长度，进而计算组合数。
完整代码
import java.util.*;
public class Main {
public static final int M = 1_000_000_007;
public static long[] f = new long[200005];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt(); // 行的数量
int m = scanner.nextInt(); // 列的数量
int t = scanner.nextInt(); // 查询次数
// 初始化阶乘数组
f[0] = 1;
for (int i = 1; i <= n + m; i++) {
f[i] = f[i - 1] * i % M;
}
// 读取输入并统计频率
Map<Integer, Integer> mpa = new TreeMap<>(); // 行权值频率
Map<Integer, Integer> mpb = new TreeMap<>(); // 列权值频率
int[] a = new int[n + 1]; // 行权值数组
int[] b = new int[m + 1]; // 列权值数组
for (int i = 1; i <= n; i++) {
a[i] = scanner.nextInt();
mpa.put(a[i], mpa.getOrDefault(a[i], 0) + 1);
}
for (int i = 1; i <= m; i++) {
b[i] = scanner.nextInt();
mpb.put(b[i], mpb.getOrDefault(b[i], 0) + 1);
}
// 添加0作为边界
mpa.put(0, 0);
mpb.put(0, 0);
// 将map转换为列表
List<Map.Entry<Integer, Integer>> va = new ArrayList<>(mpa.entrySet());
List<Map.Entry<Integer, Integer>> vb = new ArrayList<>(mpb.entrySet());
// 计算前缀积
long[] sa = new long[va.size()];
long[] sb = new long[vb.size()];
sa[0] = 1;
sb[0] = 1;
for (int i = 1; i < va.size(); i++) {
sa[i] = sa[i - 1] * va.get(i).getValue() % M;
}
for (int i = 1; i < vb.size(); i++) {
sb[i] = sb[i - 1] * vb.get(i).getValue() % M;
}
// 处理查询
while (t-- > 0) {
int x1 = scanner.nextInt();
int y1 = scanner.nextInt();
int x2 = scanner.nextInt();
int y2 = scanner.nextInt();
// 检查无效路径
if (a[x2] < a[x1] || b[y2] < b[y1] ||
(a[x2] == a[x1] && x2 != x1) ||
(b[y2] == b[y1] && y2 != y1)) {
System.out.println(0);
continue;
}
// 使用二分查找找到区间
int p = lowerBound(va, a[x2]);
int q = lowerBound(va, a[x1]);
int r = lowerBound(vb, b[y2]);
int s = lowerBound(vb, b[y1]);
// 计算区间乘积
long rowProduct = (p == q) ? 1 : sa[p - 1] * pow(sa[q], M - 2) % M;
long colProduct = (r == s) ? 1 : sb[r - 1] * pow(sb[s], M - 2) % M;
// 计算组合数
long comb = C(p - q + r - s, p - q);
// 最终结果
long result = rowProduct * colProduct % M * comb % M;
System.out.println(result);
}
scanner.close();
}
// 快速幂
public static long pow(long a, int k) {
if (k == 0) return 1;
return pow(a * a % M, k / 2) * (k % 2 == 1 ? a : 1) % M;
}
// 组合数计算
public static long C(int n, int m) {
if (m > n) return 0;
return f[n] * pow(f[m] * f[n - m] % M, M - 2) % M;
}
// 二分查找
public static int lowerBound(List<Map.Entry<Integer, Integer>> list, int key) {
int low = 0, high = list.size();
while (low < high) {
int mid = (low + high) / 2;
if (list.get(mid).getKey() < key) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}
代码补充说明
- 二分查找：
-
- 使用
lowerBound方法找到目标权值在有序列表中的位置。 - 如果目标权值不存在，则返回其插入位置。
- 使用
- 前缀积与逆元：
-
- 前缀积数组
sa和sb用于快速计算区间乘积。 - 使用模逆元计算区间乘积的逆元，从而得到区间内权值的组合贡献。
- 前缀积数组
- 组合数计算：
-
- 使用预处理的阶乘数组
f和模逆元计算组合数。 - 公式为 ( C(n, m) = \frac{n!}{m! \times (n - m)!} )，通过模逆元优化计算。
- 使用预处理的阶乘数组
- 查询处理：
-
- 对每个查询，检查路径是否有效。
- 如果路径有效，计算行和列的区间贡献，并通过组合数公式计算最终结果。
输入输出示例
输入：
4 3 2
1 2 3 4
1 2 3
1 1 2 2
2 2 3 3
输出：
1
6
最大异或节点 字典树（Trie）和图论的算法问题
字典树（Trie）和图论的算法问题
解题思路
1. 问题背景
题目要求在一个图中，通过某种方式最大化某个值。具体来说：
- 输入一个包含
n个节点的图，每个节点有一个权值a[i]。 - 图是通过邻接表
g表示的，节点之间有边连接。 - 目标是通过某种策略最大化某个节点的权值。
2. 核心思想
- 字典树（Trie）：
-
- 使用字典树存储所有节点的权值，以便快速查找和更新。
- 字典树的每个节点表示一个二进制位，通过遍历字典树可以找到与某个权值异或（XOR）最大的值。
- 图的遍历：
-
- 遍历图的每个节点，对于每个节点，暂时移除其邻接节点的权值，计算当前节点的最大异或值，然后再恢复这些权值。
- 这种策略类似于“动态维护”，通过局部调整来寻找全局最优解。
- 异或操作：
-
- 异或操作有一个重要性质：
a ^ b的结果最大时，a和b的二进制表示在每一位上尽量不同。 - 通过字典树，可以高效地找到与某个权值异或最大的值。
- 异或操作有一个重要性质：
3. 算法步骤
- 初始化：
-
- 读取每个节点的权值
a[i]，并将其插入字典树。 - 构建图的邻接表
g。
- 读取每个节点的权值
- 遍历图：
-
- 对于每个节点
i，暂时移除其邻接节点的权值（通过字典树的del方法）。 - 使用字典树的
find方法找到与当前节点权值异或最大的值。 - 更新全局最大值
ans。 - 恢复邻接节点的权值（通过字典树的
add方法）。
- 对于每个节点
- 输出结果：
-
- 输出全局最大值
ans。
- 输出全局最大值
代码详细注释
import java.util.*;
import java.io.*;
import java.math.*;
public class Main {
static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
static int n, m, maxn = 200005, inf = 0x3f3f3f3f; // 常量定义
static long ans = 0, mod = (int) 1e9 + 7, INF = (long) 2e18; // 常量定义
public static void main(String[] args) throws IOException {
new Task().main(); // 调用主逻辑
pw.flush(); // 刷新输出流
}
static class Task {
void main() throws IOException {
int t = 1; // 测试用例数量（这里固定为1）
while (t-- > 0) {
solve(); // 解决每个测试用例
}
}
int[] a = new int[maxn]; // 存储每个节点的权值
List<Integer>[] g = new List[maxn]; // 图的邻接表
int[][] ch = new int[maxn << 4][2]; // 字典树的子节点数组
int[] cnt = new int[maxn << 4]; // 字典树每个节点的计数
int tot = 0; // 字典树的节点总数
void solve() throws IOException {
n = sc.nextI(); // 读取节点数量
for (int i = 1; i <= n; i++) {
a[i] = sc.nextI(); // 读取每个节点的权值
add(a[i]); // 将权值插入字典树
}
// 初始化图的邻接表
for (int i = 0; i <= n; i++) {
g[i] = new ArrayList<>();
}
// 构建图
int s = 0; // 特殊节点（起点）
for (int i = 1; i <= n; i++) {
int x = sc.nextI() + 1; // 读取邻接节点
if (x == 0) {
s = i; // 特殊节点
} else {
g[i].add(x); // 添加边
g[x].add(i); // 添加反向边（无向图）
}
}
// 遍历每个节点
for (int i = 1; i <= n; i++) {
// 暂时移除邻接节点的权值
for (int x : g[i]) {
del(a[x]);
}
// 计算当前节点的最大异或值
ans = Math.max(ans, find(a[i]));
// 恢复邻接节点的权值
for (int x : g[i]) {
add(a[x]);
}
}
// 输出结果
pw.println(ans);
}
// 字典树查找最大异或值
private long find(int w) {
int p = 0; // 当前节点
int res = 0; // 最大异或值
for (int i = 30; i >= 0; i--) { // 从最高位到最低位
int x = (w >> i) % 2; // 当前位的值
if (cnt[ch[p][0]] == 0 && cnt[ch[p][1]] == 0) break; // 如果当前节点没有子节点，退出
if (ch[p][1 - x] != 0 && cnt[ch[p][1 - x]] > 0) { // 如果存在与当前位相反的子节点
res |= 1 << i; // 更新异或值
p = ch[p][1 - x]; // 移动到相反的子节点
} else {
p = ch[p][x]; // 移动到相同的子节点
}
}
return res;
}
// 从字典树中删除一个权值
private void del(int w) {
int p = 0; // 当前节点
for (int i = 30; i >= 0; i--) { // 从最高位到最低位
int x = (w >> i) % 2; // 当前位的值
p = ch[p][x]; // 移动到对应的子节点
cnt[p]--; // 减少计数
}
}
// 向字典树中添加一个权值
private void add(int w) {
int p = 0; // 当前节点
for (int i = 30; i >= 0; i--) { // 从最高位到最低位
int x = (w >> i) % 2; // 当前位的值
if (ch[p][x] == 0) ch[p][x] = ++tot; // 如果子节点不存在，创建新节点
p = ch[p][x]; // 移动到子节点
cnt[p]++; // 增加计数
}
}
}
// 快速输入类
static class Input {
Input(InputStream in) {
this.in = in;
}
InputStream in;
byte[] bb = new byte[1 << 15]; // 输入缓冲区
int i, n;
byte getc() {
if (i == n) { // 如果缓冲区为空
i = n = 0;
try {
n = in.read(bb); // 重新读取数据
} catch (IOException e) {
}
}
return i < n ? bb[i++] : 0; // 返回下一个字节
}
int nextI() {
byte c = 0;
while (c <= ' ') c = getc(); // 跳过空白字符
int f = 1; // 符号标志
int a = 0; // 结果
while (c > ' ') {
if (c == '-') {
f = -1;
c = getc();
continue;
}
a = a * 10 + c - '0'; // 构造整数
c = getc();
}
return a * f; // 返回结果
}
long nextL() {
byte c = 0;
while (c <= ' ') c = getc(); // 跳过空白字符
int f = 1; // 符号标志
long a = 0; // 结果
while (c > ' ') {
if (c == '-') {
f = -1;
c = getc();
continue;
}
a = a * 10 + c - '0'; // 构造长整数
c = getc();
}
return a * f; // 返回结果
}
byte[] cc = new byte[1 << 7]; // 字符串缓冲区
String next() {
byte c = 0;
while (c <= ' ') c = getc(); // 跳过空白字符
int k = 0;
while (c > ' ') {
if (k == cc.length) cc = Arrays.copyOf(cc, cc.length << 1); // 扩容
cc[k++] = c; // 保存字符
c = getc();
}
return new String(cc, 0, k); // 返回字符串
}
}
static Input sc = new Input(System.in); // 创建输入对象
}
代码功能模块解析
1. 字典树（Trie）
字典树用于高效地存储和查找二进制表示的权值。每个节点表示一个二进制位，通过遍历字典树可以找到与某个权值异或最大的值。
add方法：
-
- 将一个权值插入字典树。
- 从最高位到最低位，逐位构建路径，并更新计数。
del方法：
-
- 从字典树中移除一个权值。
- 逐位减少计数。
find方法：
-
- 查找与某个权值异或最大的值。
- 从最高位到最低位，优先选择与当前位相反的子节点，从而最大化异或结果。
2. 图的遍历
图通过邻接表 g 表示，每个节点的邻接节点存储在列表中。
- 动态维护：
-
- 对于每个节点，暂时移除其邻接节点的权值，计算当前节点的最大异或值，然后再恢复这些权值。
- 这种策略确保在计算当前节点时，邻接节点的权值不会影响结果。
3. 输入输出
- 使用自定义的
Input类实现快速输入。 - 使用
PrintWriter实现快速输出。
代码优化点
- 字典树的高效性：
-
- 字典树的深度为 31（31 位整数），查找和插入操作的时间复杂度为 ( O(31) )。
- 动态维护：
-
- 通过暂时移除和恢复邻接节点的权值，避免了全局修改对后续计算的影响。
- 快速输入输出：
-
- 使用自定义的输入输出类，避免了标准输入输出的性能瓶颈。
植物生命力
import java.util.*;
import java.io.*;
public class Main {
static int N = 200010; // 节点数量上限
static int n, s; // n是节点数量，s是根节点编号
static int[] a = new int[N]; // 存储每个节点的生命力
static long res = 0; // 存储结果
static List<Integer>[] g = new List[N]; // 存储图的邻接表
static int[] tr = new int[N]; // 树状数组
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken()); // 读取节点数量
s = Integer.parseInt(st.nextToken()); // 读取根节点编号
// 初始化邻接表
for (int i = 1; i <= n; i++) {
g[i] = new ArrayList<>();
}
// 读取每个节点的生命力
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= n; i++) {
a[i] = Integer.parseInt(st.nextToken());
}
// 构建图的邻接表
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());
g[u].add(v);
g[v].add(u);
}
// 从根节点开始深度优先搜索
dfs(s, -1);
// 输出结果
System.out.println(res);
}
// 深度优先搜索函数
static void dfs(int u, int fa) {
modify(a[u], 1); // 在树状数组中标记当前节点的生命力
// 遍历当前节点的所有子节点
for (int v : g[u]) {
if (v != fa) { // 避免回溯到父节点
dfs(v, u); // 递归遍历子节点
}
}
// 计算当前节点的子树中满足条件的节点数量
for (int k = 2; k * a[u] <= n; k++) {
int t = k * a[u];
res -= query(t) - query(t - 1); // 减去生命力为 k * a[u] 的节点数量
}
res += query(n) - query(a[u]); // 加上生命力小于 a[u] 的节点数量
modify(a[u], -1); // 取消标记
}
// 修改树状数组的函数
static void modify(int idx, int val) {
while (idx <= n) {
tr[idx] += val; // 更新树状数组的值
idx += idx & -idx; // 跳到下一个区间
}
}
// 查询树状数组的函数
static int query(int idx) {
int sum = 0;
while (idx > 0) {
sum += tr[idx]; // 累加区间值
idx -= idx & -idx; // 跳到上一个区间
}
return sum;
}
}
代码解析
1. 数据结构
a数组：存储每个节点的生命力。g邻接表：存储树的结构。tr树状数组：用于高效统计区间内的节点数量。res：全局变量，用于存储最终结果。
2. 树状数组的实现
modify方法：
-
- 用于在树状数组中标记或取消标记某个值。
- 时间复杂度为 (O(\log n))。
query方法：
-
- 用于查询某个区间内的累加值。
- 时间复杂度为 (O(\log n))。
3. DFS 的递归逻辑
- 在进入节点
u时，标记其生命力值a[u]。 - 递归处理所有子节点。
- 在离开节点
u时，取消标记其生命力值。
4. 统计满足条件的节点对
- 对于每个节点
u，统计其子树中满足条件的节点数量：
-
- 生命力是当前节点的整数倍：通过树状数组查询
[k * a[u], k * a[u]]的数量。 - 生命力小于当前节点：通过树状数组查询
[1, a[u] - 1]的数量。
- 生命力是当前节点的整数倍：通过树状数组查询
5. 结果更新
- 使用全局变量
res累加满足条件的节点对数量。
复杂度分析
- 时间复杂度：
-
- 每个节点的 DFS 遍历：(O(n))。
- 每个节点的树状数组操作：(O(\log n))。
- 总时间复杂度：(O(n \log n))。
- 空间复杂度：
-
- 树状数组和邻接表：(O(n))。
更多推荐
28
0- 0
已为社区贡献5条内容
所有评论(0)