16届JavaB组省赛暴力拆解
逃离高塔
解题思路
这道题是典型的**枚举（暴力）**题目。我们需要遍历 1 到 2025 的每一个数字，计算其立方值，并判断个位数是否为 3。
在编写代码时，需要注意数据溢出的问题：
- 2025^3 \approx 8,300,000,000（83亿）。
- Java 中
int类型的最大值约为 21 亿（2 \times 10^9）。 - 直接使用
int存储立方结果会导致溢出，算出负数或错误的值。
针对这个问题，我们有两种解决方案：
- 方案一（类型提升）：使用
long类型来存储立方结果，long的范围足够大。 - 方案二（取模性质）：根据数学性质，一个数的个位数只由它本身的个位数决定。我们可以只计算个位的立方，完全避免大数运算。
参考代码（Java）
方法一：直接计算（使用 long）
这是最直观的方法，适合比赛时快速编写。注意乘法前要强制转换。
public class Main {
public static void main(String[] args) {
int count = 0;
// 遍历 1 到 2025
for (int i = 1; i <= 2025; i++) {
// 关键点：强制转为 long，防止 int 溢出
long cube = (long) i * i * i;
// 判断个位是否为 3
if (cube % 10 == 3) {
count++;
}
}
System.out.println(count);
}
}
方法二：取模优化（只看个位）
不需要计算完整的立方值，只计算个位数的立方即可。这种方法不需要 long，计算量更小。
public class Main {
public static void main(String[] args) {
int count = 0;
for (int i = 1; i <= 2025; i++) {
// 取出当前数字的个位
int last = i % 10;
// 只计算个位的立方，最大也就 9^3 = 729，int 足够
int cubeTail = (last * last * last) % 10;
if (cubeTail == 3) {
count++;
}
}
System.out.println(count);
}
}
最终结果
程序运行输出：
202
消失的蓝宝
解题思路（数学推导 / 最小公倍数）
这是一道经典的数论构造题。我们要找一个最小正整数 N。
- 题目条件分析
令 A = 20250412，B = 20240413。
题目要求：
- (N + A) 能被 B 整除 \Rightarrow (N + A) 是 B 的倍数。
- (N + B) 能被 A 整除 \Rightarrow (N + B) 是 A 的倍数。
- 巧妙转化（填坑法）
我们观察这两个条件，试着给它们“补”上一点东西，让形式变得统一。
- 对于条件 1：如果 (N + A) 是 B 的倍数，那么我们再给它加上一个 B，结果 (N + A + B) 依然是 B 的倍数。
- 对于条件 2：如果 (N + B) 是 A 的倍数，那么我们再给它加上一个 A，结果 (N + B + A) 依然是 A 的倍数。
- 核心结论
经过上面的变形，我们发现一个共同的目标数 X = N + A + B。
- X 既是 B 的倍数，也是 A 的倍数。
- 也就是说，X 是 A 和 B 的公倍数。
- 题目要求 N 最小 \Rightarrow 要求 X 最小。
- 所以，X 应该是 A 和 B 的最小公倍数 (LCM)。
- 公式推导
N + A + B = \text{LCM}(A, B)
N = \text{LCM}(A, B) - A - B
5. 数据范围与计算
- A, B \approx 2 \times 10^7。
- 最小公倍数 \text{LCM}(A, B) = \frac{A \times B}{\text{GCD}(A, B)}。
- 两个 2000 万级别的数相乘，结果约为 4 \times 10^{14}，超过了
int的范围，必须使用long。
参考代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
long a = 20250412;
long b = 20240413;
// 1. 计算最大公约数 (GCD)
long gcdVal = gcd(a, b);
// 2. 计算最小公倍数 (LCM)
// 公式：LCM = (a * b) / GCD
// 注意：先除后乘防止中间过程溢出 (虽然这里用 long 不会溢出，但这是好习惯)
// 或者直接 a * b / gcd 也可以，因为 10^14 在 long 范围内
long lcmVal = (a / gcdVal) * b;
// 3. 反推 N
// N + A + B = LCM => N = LCM - A - B
long n = lcmVal - a - b;
System.out.println(n);
}
// 欧几里得算法求最大公约数
public static long gcd(long a, long b) {
return b == 0 ? a : gcd(b, a % b);
}
}
补充：关于“暴力枚举”的可行性
如果这道题你在考场上推不出最小公倍数的性质，能暴力做吗？
-
分析：条件 1 说 N = k \cdot B - A。由于 N > 0，且 A \approx B，所以 k 从 1 或 2 开始枚举即可。
-
复杂度：你需要枚举 k，直到 (N + B) \% A == 0。根据数论性质，这个循环的次数大约是 A / \text{GCD}(A, B) 次。由于 A \approx 2 \times 10^7，循环次数在千万级别。
-
结论：Java 1秒可以跑 1亿次运算，2000万次循环是可以暴力跑出来的！ * 暴力代码片段：
public class Main { public static void main(String[] args) { long a = 20250412; long b = 20240413; // 从 k=1 开始暴力尝试，直到找到满足第二个条件的数 for (long k = 1; ; k++) { long n = k * b - a; if (n > 0 && (n + b) % a == 0) { System.out.println(n); break; } } } }(两种方法结果一致，都能过)
电池分组
这道题是典型的**“披着狼皮的羊”**。
乍一看，你可能觉得需要用 DFS（深度优先搜索）去尝试每一种分组情况，或者用背包 DP 去凑数。
但实际上，这道题考察的是异或（XOR）运算的核心性质。只要你懂了这个性质，这道题的代码只有几行，连脑子都不用动。
解题思路一（数学性质巧解）
1. 异或的核心性质
- 性质一：归零律。任何数和自己异或，结果都是 0。即 A \oplus A = 0。
- 性质二：如果 A = B，那么 A \oplus B = 0。
- 题目翻译
题目要求把一堆数分成两组（记为 Group1 和 Group2），让它们的异或和相等。
设 X_1 为 Group1 的异或和，X_2 为 Group2 的异或和。
题目要求：X_1 = X_2。
- 逻辑推导
根据性质二，如果 X_1 = X_2，那么 X_1 \oplus X_2 必须等于 0。
而 X_1 \oplus X_2 其实就是所有数字加在一起的总异或和。
结论：
- 只要所有数字的总异或和为 0，就一定能分成两组相等的（比如把第一个数分一组，剩下的分一组，根据异或性质，它们一定相等）。
- 如果总异或和不为 0，神仙也分不出来。
- 为什么暴力搜索不行？
如果你尝试暴力枚举每一个电池属于第一组还是第二组，时间复杂度是 O(2^N)。
当 N=1000 时，2^{1000} 是个天文数字，绝对超时。
所以这道题必须用数学性质。
没问题！这正是我们“暴力拆解”专题的意义所在——如果我不懂那个数学巧劲儿，我能不能用最朴素的逻辑把这题做出来？
哪怕这道题的暴力法过不了 N=1000 的数据，但在考场上，把题目翻译成代码，写出一个**“搜索（DFS）”**，往往能帮你拿下前 20%~30% 的分数（取决于数据有多弱）。
对于这种“分成两组”的问题，最通用的暴力手段就是：深度优先搜索 (DFS)。
解题思路二（暴力 DFS 搜索）
1. 核心思想：枚举每一种分法
不想动脑子推公式？那就动动手，把所有可能性试一遍！
对于每一个电池，我们只有两个选择：
- 选择 A：把它扔进第一组。
- 选择 B：把它扔进第二组。
我们就写一个递归函数，模拟这个“分拣”的过程。一路分到底，分完 N 个电池后，看一眼：第一组的异或和，等不等于第二组？如果相等，就成功！
2. 状态定义
我们需要一个函数 dfs(index, xor1, xor2, cnt1, cnt2)：
index: 当前正在处理第几个电池。xor1: 第一组当前的异或和。xor2: 第二组当前的异或和。cnt1: 第一组现在有几个电池（题目要求每组至少 1 个，所以要记数）。cnt2: 第二组现在有几个电池。
3. 递归流程
- Base Case（终点）：当
index == n时，说明所有电池都分完了。- 检查
xor1 == xor2且cnt1 > 0且cnt2 > 0。 - 如果满足，返回
true。
- 检查
- 递归分支：
- 路 1：把当前电池给第一组，继续递归下一层。
- 路 2：把当前电池给第二组，继续递归下一层。
- 只要有一条路能通（返回 true），整个任务就算完成。
4. 为什么这是“笨”办法？
因为每个电池有 2 种选择，N 个电池就是 2^N 种情况。
- 如果 N=10，计算 2^{10} = 1024 次，很快。
- 如果 N=20，计算 2^{20} \approx 100 万次，勉强能过。
- 如果 N=100，计算机直接冒烟。
- 但在不知道数学解法时，这是唯一的救命稻草。
参考代码一（数学性质巧解）
代码简单到令人发指，只需要把所有数异或起来，看结果是不是 0 即可。
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 读取测试用例数量 T
int t = sc.nextInt();
// 处理每一组测试数据
while (t-- > 0) {
int n = sc.nextInt();
// 用来存储所有数字的异或和
// 初始化为 0，因为 0 异或任何数都等于那个数本身
int totalXor = 0;
for (int i = 0; i < n; i++) {
int val = sc.nextInt();
// 累积异或
totalXor ^= val;
}
// 核心判断：如果总异或和为 0，说明可以分组；否则不行。
if (totalXor == 0) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
}
一句话总结：
看到“分成两组异或和相等”，直接把所有数异或起来，等于 0 输出 YES，否则输出 NO。
参考代码二（暴力 DFS）
import java.util.Scanner;
public class Main {
static int n;
static int[] nums;
static boolean found; // 标记是否找到了解
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while (t-- > 0) {
n = sc.nextInt();
nums = new int[n];
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
// 重置标记
found = false;
// 开始暴力搜索
// 参数：第0个电池开始，组1异或值0，组2异或值0，组1数量0，组2数量0
dfs(0, 0, 0, 0, 0);
if (found) {
System.out.println("YES");
} else {
System.out.println("NO");
}
}
}
/**
* 暴力搜索函数
* @param idx 当前处理到第几个电池
* @param xor1 第一组的异或和
* @param xor2 第二组的异或和
* @param cnt1 第一组的元素个数
* @param cnt2 第二组的元素个数
*/
static void dfs(int idx, int xor1, int xor2, int cnt1, int cnt2) {
// 1. 如果已经找到了答案，就没必要继续搜了 (剪枝)
if (found) return;
// 2. 终点判断：所有电池都分完了
if (idx == n) {
// 必须满足：异或和相等，且两组都不为空
if (xor1 == xor2 && cnt1 > 0 && cnt2 > 0) {
found = true;
}
return;
}
// 3. 尝试分支一：把当前电池放入【第一组】
dfs(idx + 1, xor1 ^ nums[idx], xor2, cnt1 + 1, cnt2);
// 4. 尝试分支二：把当前电池放入【第二组】
// 如果分支一已经成功了(found=true)，这里就不需要跑了
if (!found) {
dfs(idx + 1, xor1, xor2 ^ nums[idx], cnt1, cnt2 + 1);
}
}
}
这个 dfs 写法是通用的。如果题目把“异或和”改成“累加和相等”（那就是经典的划分数问题），或者改成“乘积相等”，这套代码框架完全不用变，只需要改改计算符号就行。
暴力 DFS 是解决“分组”、“子集”类问题的万能钥匙，虽然慢，但逻辑绝对正确，适合拿小数据分。
魔法科考试
解题思路
本题的核心任务是寻找满足特定条件的组合 S = a_i + b_j。我们需要关注三个关键点：
- 有效范围：组合出的和 S 必须满足 S \le n + m。
- 质数判断：S 必须是质数。
- 去重计数：题目问的是“多少种不同的有效魔法”，这意味着如果不同的 a_i + b_j 算出了同一个 S，只能记 1 次。
针对数据范围（n, m \le 20000，即 S 最大约为 40000），我们有两种主要的解法：一种是适合比赛的标准“筛法”，另一种是适合小数据的“优化的暴力判定”。
方法一：线性筛 + 标记数组（标准正解）
思路解析：
由于 S 的上限已知且不大（n+m），我们可以先预处理出一张“质数表”。
- 预处理：使用埃氏筛或线性筛，找出 0 \sim n+m 范围内的所有质数。这样后续判断一个数是不是质数只需要 O(1) 的时间。
- 去重：为了统计不同的 S，我们可以开一个
boolean[]数组。如果算出一个合法的 S，先检查标记数组，没标记过就ans++并标记，标记过就跳过。这比使用HashSet效率高得多。
参考代码：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[n];
int[] b = new int[m];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
for (int i = 0; i < m; i++) b[i] = sc.nextInt();
// 1. 预处理质数表，范围最大到 n + m
// isPrime[x] 为 true 表示 x 是质数
boolean[] isPrime = sieve(n + m);
// 2. 用于去重的标记数组
boolean[] counted = new boolean[n + m + 1];
int ans = 0;
// 3. 双重循环枚举所有组合
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int sum = a[i] + b[j];
// 判定条件：
// 1. 不超过 n + m
// 2. 是质数
// 3. 之前没统计过
if (sum <= n + m && isPrime[sum] && !counted[sum]) {
counted[sum] = true;
ans++;
}
}
}
System.out.println(ans);
}
// 线性筛法：预处理质数
private static boolean[] sieve(int limit) {
boolean[] isPrime = new boolean[limit + 1];
Arrays.fill(isPrime, true);
if (limit >= 0) isPrime[0] = false;
if (limit >= 1) isPrime[1] = false;
List<Integer> primes = new ArrayList<>();
for (int i = 2; i <= limit; i++) {
if (isPrime[i]) {
primes.add(i);
}
// 筛掉倍数
for (int p : primes) {
if (i * p > limit) break;
isPrime[i * p] = false;
if (i % p == 0) break;
}
}
return isPrime;
}
}
方法二：朴素判定优化（6k \pm 1 法）
思路解析：
如果在考场上记不住筛法，或者数据范围较小，可以直接对每个生成的 S 进行质数判断。
普通的质数判断需要从 2 循环到 \sqrt{S}，效率一般。我们可以使用 6k \pm 1 优化法 来加速：
- 原理：大于 3 的质数一定分布在 6 的倍数的两侧（即 6k-1 或 6k+1）。
- 做法：先特判 2 和 3。然后循环步长设为 6，每次只判断 i 和 i+2。这能将判断速度提升约 3 倍。
参考代码：
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[n];
int[] b = new int[m];
for (int i = 0; i < n; i++) a[i] = sc.nextInt();
for (int i = 0; i < m; i++) b[i] = sc.nextInt();
// 标记数组，用于记录已经统计过的 S
boolean[] found = new boolean[n + m + 1];
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int s = a[i] + b[j];
// 1. 范围检查 & 去重检查
// 只有当 sum 还没被标记过时，我们才去进行昂贵的质数判断
if (s <= n + m && !found[s]) {
// 2. 质数检查
if (isPrime(s)) {
found[s] = true;
ans++;
}
}
}
}
System.out.println(ans);
}
// 优化的质数判断：6k +/- 1 法
public static boolean isPrime(int num) {
// 小于等于1不是质数
if (num <= 1) return false;
// 2 和 3 是质数
if (num <= 3) return true;
// 只有 6k-1 和 6k+1 的位置才可能是质数
// 排除掉所有 2 的倍数和 3 的倍数
if (num % 2 == 0 || num % 3 == 0) return false;
// 从 5 开始，步长为 6
int sqrt = (int) Math.sqrt(num);
for (int i = 5; i <= sqrt; i += 6) {
// 检查 6k-1 (i) 和 6k+1 (i+2)
if (num % i == 0 || num % (i + 2) == 0) {
return false;
}
}
return true;
}
}
爆破
解题思路（最小生成树 MST）
这道题本质上是一个图论问题。
-
抽象模型：
我们将每一个魔法阵看作图中的一个节点。
任意两个魔法阵之间都可以建立连接，因此这是一个完全图（稠密图）。
-
边权计算：
题目要求“总长度最小”，我们需要计算任意两个魔法阵 i 和 j 之间的连接代价（边权 w_{ij}）：
- 计算两圆圆心的欧几里得距离：d = \sqrt{(x_i-x_j)^2 + (y_i-y_j)^2}。
- 情况 A（相交或相切）：如果 d \le r_i + r_j，说明两个圆本身就是连通的，不需要额外的魔法回路，代价为 0。
- 情况 B（分离）：如果 d > r_i + r_j，需要连接两个圆的边缘，代价为 d - (r_i + r_j)。
- 综合公式：w_{ij} = \max(0, d - r_i - r_j)。
-
算法选择：
我们需要让所有点连通，且边权之和最小，这就是标准的 最小生成树（MST） 问题。
- Kruskal 算法：适合稀疏图。这里边数高达 N^2 \approx 2.5 \times 10^7，排序边的时间复杂度为 O(E \log E)，可能会超时。
- Prim 算法：适合稠密图。时间复杂度为 O(N^2)。对于 N=5000，运算量约为 2.5 \times 10^7，完全可以在 1 秒内通过。
-
内存优化（关键点）：
虽然 N=5000 的计算量能过，但在 Java 中开一个
double[5000][5000]的邻接矩阵需要约 200MB 内存，极易导致内存超限（MLE）。优化策略：不显式建立邻接矩阵。在 Prim 算法过程中，当我们需要用到 i 和 j 的距离时，现场计算。这样空间复杂度从 O(N^2) 降为 O(N)，非常安全。
参考代码（Prim 算法 + 空间优化）
import java.util.*;
import java.io.*;
public class Main {
// 使用静态内部类或数组存储数据，方便访问
static int n;
static double[] x, y, r;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
x = new double[n];
y = new double[n];
r = new double[n];
for(int i = 0; i < n; i++){
x[i] = sc.nextDouble();
y[i] = sc.nextDouble();
r[i] = sc.nextDouble();
}
// Prim 算法求解
System.out.printf("%.2f\n", prim());
}
// Prim 算法核心逻辑
static double prim() {
// minDist[i] 表示节点 i 距离当前生成树集合的最短距离
double[] minDist = new double[n];
// visited[i] 表示节点 i 是否已经加入了生成树
boolean[] visited = new boolean[n];
// 初始化：所有点距离无穷大，从第 0 个点开始
Arrays.fill(minDist, Double.MAX_VALUE);
minDist[0] = 0;
double totalWeight = 0;
// 循环 n 次，每次找一个点加入生成树
for(int i = 0; i < n; i++){
int u = -1;
double minVal = Double.MAX_VALUE;
// 1. 寻找未访问节点中 minDist 最小的节点 u
for(int j = 0; j < n; j++){
if(!visited[j] && minDist[j] < minVal){
minVal = minDist[j];
u = j;
}
}
// 如果找不到连通的点（本题是完全图，理论上不会发生）
if(u == -1) break;
// 2. 将 u 加入集合
visited[u] = true;
totalWeight += minVal;
// 3. 用 u 去更新其他未访问节点的 minDist
// 这里不查表，直接现场计算距离，省空间
for(int v = 0; v < n; v++){
if(!visited[v]){
double dist = getCost(u, v);
if(dist < minDist[v]){
minDist[v] = dist;
}
}
}
}
return totalWeight;
}
// 计算两点连接代价的辅助函数
static double getCost(int i, int j) {
double dx = x[i] - x[j];
double dy = y[i] - y[j];
// 圆心距离
double d = Math.sqrt(dx * dx + dy * dy);
// 代价 = max(0, 圆心距 - 半径和)
return Math.max(0, d - r[i] - r[j]);
}
}
代码解析
- 空间优化：可以看到代码中没有
double[][] graph数组。我们在 Prim 的松弛操作（更新minDist）时，直接调用getCost(u, v)计算权重。对于 N=5000，这节省了巨大的内存空间。 - Prim 流程：
- 找最近的点
u。 - 把
u标记为已访问。 - 根据
u刷新还没访问的点的最短距离minDist。
- 找最近的点
- 距离公式：严格遵循题目逻辑，相交则为 0，不相交则减去半径。
数组翻转
这是一道经典的数组与贪心算法问题。我们可以通过分析“翻转”操作的本质来找到最优解。
解题思路
-
翻转的作用：
在一个数组中，如果我们想让某个数值 V 的所有出现尽可能连在一起，一次翻转操作最多可以将两段原本分开的连续 V 拼接到一起。
- 例如：
3 3 3 ... 2 1 ... 3 3。 - 我们有两段
3。通过翻转中间的... 2 1 ...部分（连同其中一段3的边界），我们可以让这两段3变成相邻的。 - 一次翻转无法让三段或更多段分开的数值同时合并（除非中间的间隔恰好被消除，但在最坏和通用的情况下，我们只能保证合并两段）。
- 例如：
-
问题转化：
对于数组中的每一个数值 x（比如 1, 2, 3...），我们只关心：
- 它在数组中构成的最长连续段的长度（记为
max1）。 - 它在数组中构成的第二长连续段的长度（记为
max2）。
翻转后的最大长度即为
max1 + max2。- 如果该数值只有一段，那么
max2为 0，结果就是max1（不进行有效翻转或翻转无关区域）。 - 如果有多段，通过翻转可以将最长的两段合并。
- 它在数组中构成的最长连续段的长度（记为
-
计算公式：
对于每个数值 i，其最大得分 = i \times (\text{最长连续长度} + \text{次长连续长度})。
最终答案是所有数值中计算出的最大得分。
算法步骤
- 遍历输入数组，找出每个数值的所有连续段长度。
- 对于每个数值，维护其最长和次长的长度记录。
- 遍历所有出现过的数值，计算得分并取最大值。
- 时间复杂度为 O(N)，空间复杂度取决于数值的范围（本题中 a_i \le 10^6，可以使用数组直接存）。
参考代码 (Java)
为了应对 N \le 10^6 的数据量，建议使用快速 I/O（这里还是用Scanner方便阅读）。
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
// 读取 n
int n = sc.nextInt();
// 数组最大值为 10^6，定义数组来存储状态
// maxLen[v] 存储数值 v 的最长连续段长度
// secondMaxLen[v] 存储数值 v 的次长连续段长度
int MAX_VAL = 1000005;
int[] maxLen = new int[MAX_VAL];
int[] secondMaxLen = new int[MAX_VAL];
// 读取第一个数，初始化当前段
int lastVal = sc.nextInt();
int currentLen = 1;
// 标记出现过的最大数值，减少最后遍历范围
int maxInputVal = lastVal;
for (int i = 1; i < n; i++) {
int val = sc.nextInt();
maxInputVal = Math.max(maxInputVal, val);
if (val == lastVal) {
currentLen++;
} else {
// 结算上一段 lastVal 的长度
updateLen(maxLen, secondMaxLen, lastVal, currentLen);
// 重置当前段
lastVal = val;
currentLen = 1;
}
}
// 结算最后一段
updateLen(maxLen, secondMaxLen, lastVal, currentLen);
// 计算最大分数
long maxScore = 0;
// 只需要遍历到输入中出现过的最大值即可
for (int i = 1; i <= maxInputVal; i++) {
if (maxLen[i] > 0) {
// 合并最长和次长的两段
long totalLen = maxLen[i] + secondMaxLen[i];
long score = totalLen * i;
if (score > maxScore) {
maxScore = score;
}
}
}
System.out.println(maxScore);
}
// 辅助方法：更新最长和次长记录
private static void updateLen(int[] maxLen, int[] secondMaxLen, int val, int len) {
if (len >= maxLen[val]) {
// 新长度比原来的最长还长（或相等）
secondMaxLen[val] = maxLen[val]; // 原最长变为次长
maxLen[val] = len; // 更新最长
} else if (len > secondMaxLen[val]) {
// 新长度介于最长和次长之间
secondMaxLen[val] = len;
}
}
}
用Java Map + List：
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
// 快速输入模板
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
st.nextToken();
int n = (int) st.nval;
// 用 Map 存储：Key 是数值，Value 是这个数值所有连续段长度的列表
// 比如：数值 3 出现了三次，长度分别为 [2, 1, 5]，这就存进 List 里
Map<Integer, List<Integer>> map = new HashMap<>();
// 读取第一个数
st.nextToken();
int lastVal = (int) st.nval;
int currentLen = 1;
for (int i = 1; i < n; i++) {
st.nextToken();
int val = (int) st.nval;
if (val == lastVal) {
currentLen++; // 还是同一个数，长度+1
} else {
// 换数了，把上一段的长度记账
if (!map.containsKey(lastVal)) {
map.put(lastVal, new ArrayList<>());
}
map.get(lastVal).add(currentLen);
// 重置
lastVal = val;
currentLen = 1;
}
}
// 别忘了把最后一段也没收
if (!map.containsKey(lastVal)) {
map.put(lastVal, new ArrayList<>());
}
map.get(lastVal).add(currentLen);
// --- 暴力计算开始 ---
long maxScore = 0;
// 遍历 Map 中记录的每一个数字
for (int val : map.keySet()) {
List<Integer> lengths = map.get(val);
// 给长度排个序，倒序（从大到小）
// 注意：Collections.sort 默认是升序，我们用 reverseOrder
Collections.sort(lengths, Collections.reverseOrder());
long totalLen = 0;
if (lengths.size() >= 2) {
// 如果至少有两段，取最大的两段
totalLen = lengths.get(0) + lengths.get(1);
} else {
// 如果只有一段，就取这一段
totalLen = lengths.get(0);
}
// 计算分数
long score = totalLen * val;
if (score > maxScore) {
maxScore = score;
}
}
System.out.println(maxScore);
}
}
2 的幂
解题思路一（动态规划 分组背包)
这道题本质上是一个 “分组背包问题” (Group Knapsack Problem) 的变种。为了理解这个晦涩的术语，我们先用“商店凑单”的逻辑来看，再对应到算法模型中。
1. 直观理解：商店凑单模型（套餐逻辑）
目标：你要收集 K 个“因子 2”。
规则：
- 你手里有 N 个数字（比如
19, 10, 3）。 - 每个数字就像一个**“商店”**。
- 在每个商店里，你可以花钱（加数）把这个数字改造成各种“套餐”。
- 互斥规则：每个商店你只能买一种套餐（或者不买）。你不能既把 19 变成 20，又把 19 变成 24，数字只能变一次。
- 问题：怎么花最少的钱，凑够 K 个积分（因子 2）？
套餐菜单（预处理）：
拿数字 19 举例，它的“菜单”是这样的：
- 套餐 A（不变）：
- 变成 19。含 0 个 2。花费 0 元。
- 套餐 B（变成 2 的倍数）：
- 最近的是 20 (20=4\times5=2^2\times5)。含 2 个 2。花费 20-19= 1 元。
- 套餐 C（变成 8 的倍数）：
- 最近的是 24 (24=8\times3=2^3\times3)。含 3 个 2。花费 24-19= 5 元。
- ...以此类推，直到变成 2^{16} 的倍数。
我们对这 N 个数字，每一个都列出这样一张菜单。
2. 深度转换：如何映射为“背包问题”？
为什么说它是背包问题？请看下表的对应关系：
| 凑单原本的概念 | 背包问题的术语 | 解释 |
|---|---|---|
| 我们要凑齐 K 个因子 | 背包容量 (Capacity) | 背包总共能装重K 的东西。 |
| 每个数字 (商店) | 物品组 (Group) | 这是一个“分组背包”，每一组代表一个原始数字。 |
| 套餐 (如变成24) | 组内物品 (Item) | 在这一组里，我们有多个选择（变2倍数、变4倍数...）。 |
| 套餐提供的因子数 | 物品重量 (Weight) | 这个选择占用了背包多少容量（贡献了多少因子）。 |
| 套餐的花费 | 物品价值 (Cost) | 这里比较特殊，通常背包是求最大价值，这里是求最小代价。 |
| 每家店只能选一种 | 分组互斥约束 | 分组背包的特性：每组最多选一个。 |
状态定义 (DP 数组)：
dp[j]：表示当背包里已经装了 j 个因子 2 时，我们付出的最小代价（花费）。
状态转移方程：
当我们处理第 i 个数字（第 i 组）时：
dp_{new}[j + \text{gain}] = \min(dp_{new}[j + \text{gain}], \ dp_{old}[j] + \text{cost})
- 意思就是：如果不买这个套餐，代价是旧的；如果买这个套餐，代价是“旧代价 + 当前花费”。我们选便宜的那个。
如果觉得 “分组背包 DP” 那种填表的方式太抽象、太难想，我们完全可以用 “递归搜索（DFS）+ 记事本（记忆化）” 的方式来写。
这种思路更符合人类的直觉：“对于第 1 个数，我试一下变 2^1；然后去处理第 2 个数……哎呀这条路太贵了，回得去换个试法。”
这就是标准的 暴力搜索，只要加上一行代码（记事本），就能拿满分！
解题思路二（暴力搜索 DFS + 记忆化）
1. 核心逻辑：闯关游戏
把这道题想象成闯关：
- 关卡：一共有 N 关（对应 N 个数字）。
- 目标：通关时，身上收集的“因子 2”必须达到 K 个。
- 决策：在每一关（面对每一个数字），你有一张“菜单”（就是刚才说的 2^0 \dots 2^{16} 的倍数）。你必须选一项，付钱，拿积分，然后进入下一关。
- 问题：怎么选，总花费最少？
2. 递归函数设计
我们需要写一个函数 dfs(index, currentK)：
index：当前来到第几关（处理第几个数字）。currentK：目前还需要凑多少个因子 2。- 返回值：从这一关开始，凑齐剩下的因子，最少还要花多少钱。
3. 为什么加“记事本”？
如果不加记事本，这就是纯暴力，会超时。
比如：
- 方案 A：前 5 个数凑了 10 分。
- 方案 B：前 5 个数通过别的花样也凑了 10 分。
- 对于第 6 个数来说，它根本不在乎你前面怎么凑的，它只知道“现在缺口还剩 K-10”。
- 如果不记录，方案 A 算一遍后面，方案 B 又算一遍后面，重复劳动。
- 解决：用一个数组
memo[index][currentK]记录下来。如果算过，直接返回。
参考代码一（动态规划 分组背包)
代码完全对应上述逻辑。
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(); // 商店数量
int k = sc.nextInt(); // 目标积分 (背包容量)
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
// 1. 初始化 DP
// dp[j] 表示凑齐 j 个因子 2 至少花多少钱
long[] dp = new long[k + 1];
// 初始化：除了凑 0 个需要 0 元外，凑其他数量在没开始前都是不可能的（无穷大）
Arrays.fill(dp, Long.MAX_VALUE / 2); // 除以2是为了防止加法溢出
dp[0] = 0;
// 2. 逛每一家商店 (遍历每一个数字，即遍历每一个“物品组”)
for (int i = 0; i < n; i++) {
int currentVal = a[i];
// 准备一张新纸 nextDp，基于上一轮的结果来更新
// 为什么要新纸？因为这是分组背包，这一组里的套餐是互斥的。
// 必须基于“还没进这家店之前”的状态来计算，防止自己在同一家店买了两次。
long[] nextDp = new long[k + 1];
Arrays.fill(nextDp, Long.MAX_VALUE / 2);
// 3. 看这家店的菜单 (尝试各种套餐：变成 2^0, 2^1 ... 2^16 的倍数)
// p 代表套餐能提供的因子数量 (物品重量)
for (int p = 0; p <= 17; p++) {
// powerOf2 就是目标倍数：1, 2, 4, 8, 16...
int powerOf2 = 1 << p;
// --- 计算代价 (Cost) ---
// 算出要把 currentVal 变成 powerOf2 的倍数，最近的目标是谁
// 比如 currentVal=19, powerOf2=4，最近的是 20
int target = currentVal;
int rem = currentVal % powerOf2;
if (rem != 0) {
target = currentVal + (powerOf2 - rem);
}
// 题目限制修改后的数字不能超过 10万，超过了就说明这个套餐不合法
if (target > 100000) break; // 剪枝，后面的 2^p 更大，肯定也不行
int cost = target - currentVal; // 花了多少钱 (代价)
int gain = p; // 赚了几个因子 (重量)
// --- 4. 状态转移 (填表) ---
// 遍历上一轮所有的状态 j (背包已有的容量)
for (int j = 0; j <= k; j++) {
// 如果上一轮凑 j 个是可能的 (不是无穷大)
if (dp[j] < Long.MAX_VALUE / 2) {
// 现在手里有 j 个，又买了 gain 个
// 总共就是 j + gain 个。如果超过 k，就当做 k 处理（因为题目只要求至少 k）
int total = Math.min(k, j + gain);
// 比较一下：是保留之前的方案便宜，还是“旧方案 + 买当前套餐”便宜？
nextDp[total] = Math.min(nextDp[total], dp[j] + cost);
}
}
}
// 这一家店逛完了，更新 DP 状态，准备去下一家
dp = nextDp;
}
// 输出结果：凑够 k 个因子的最小花费
if (dp[k] >= Long.MAX_VALUE / 2) {
System.out.println(-1); // 怎么凑都凑不齐
} else {
System.out.println(dp[k]);
}
}
}
参考代码二（DFS + 记忆化）
这份代码非常好理解，逻辑就是“遍历菜单 -> 递归下一层 -> 取最小值”。
import java.util.*;
import java.io.*;
public class Main {
static int n, k;
static int[] a;
// 记事本：memo[i][j] 表示处理第 i 个数时，还缺 j 个因子，此时的最小花费
static long[][] memo;
static final long INF = Long.MAX_VALUE / 2;
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
k = sc.nextInt();
a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
// 初始化记事本，-1 表示没算过
memo = new long[n][k + 1];
for (int i = 0; i < n; i++) {
Arrays.fill(memo[i], -1);
}
// 从第 0 个数开始搜，还需要凑 k 个
long ans = dfs(0, k);
if (ans >= INF) {
System.out.println(-1);
} else {
System.out.println(ans);
}
}
/**
* 递归函数
* @param idx 当前处理到第几个数字
* @param need 还需要凑多少个因子 2
* @return 满足条件所需的最小花费
*/
static long dfs(int idx, int need) {
// 1. Base Case (终点)
if (need <= 0) {
return 0; // 不需要再凑了，后面的花费可以是 0 (都不改)
}
if (idx == n) {
// 数字用完了，但 need 还是 > 0，说明凑不齐，返回无穷大
return INF;
}
// 2. 查记事本
if (memo[idx][need] != -1) {
return memo[idx][need];
}
long minCost = INF;
int currentVal = a[idx];
// 3. 遍历菜单：尝试把当前数字变成 2^p 的倍数
for (int p = 0; p <= 17; p++) {
int powerOf2 = 1 << p;
// 计算要把 currentVal 改成 powerOf2 的倍数，目标是多少
int target = currentVal;
int rem = currentVal % powerOf2;
if (rem != 0) {
target = currentVal + (powerOf2 - rem);
}
// 题目限制，改完不能超过 10万
if (target > 100000) break;
int cost = target - currentVal; // 本次花费
int gain = p; // 本次获得的因子数
// 递归去算后面的：
// 当前花了 cost，后面还需要凑 (need - gain)
long remainCost = dfs(idx + 1, need - gain);
// 如果后面的有解，就更新最小值
if (remainCost != INF) {
minCost = Math.min(minCost, cost + remainCost);
}
}
// 4. 记入记事本并返回
memo[idx][need] = minCost;
return minCost;
}
}
两种方法的比较
| 特性 | 方法一：迭代 DP (填表) | 方法二：递归 DFS (搜索) |
|---|---|---|
| 思维难度 | 较难，需要明白 nextDp 的滚动数组逻辑 |
简单，符合直觉的“尝试-下一步”逻辑 |
| 代码结构 | 双层循环，显式状态转移 | 递归函数，查表 |
| 运行效率 | 极高，没有递归开销 | 略慢，有递归栈开销，但同样能过 100% 数据 |
| 适用场景 | 追求极致性能 | 比赛时快速解题，不易写错 |
如果你在考场上遇到这种“凑数”或“背包”问题，但是推不出 DP 方程，直接写带 memo 的 DFS，效果是一模一样的！这就是拿满分的“暴力”解法。
这是为您整理的独立题解，包含优化的贪心算法（正解）以及适合骗取部分分的暴力全排列解法。
研发资源分配
解题思路一（正解：枚举分割点 + 贪心策略）
这道题本质上是一个博弈策略问题。我们需要为 A 部门构造一个排列，使得 (A得分 - B得分) 最大。
1. 策略分析：田忌赛马的变种
为了让 A 赢，最优的策略是用 A 手中刚好比 B 大一点点的牌去赢 B。
例如：B 出 3，A 如果用 10 去赢就太浪费了，最好用 4 去赢，把大牌留给后面。
根据这个直觉，我们可以构造一种极端的“错位压制”策略：
我们把 B 的需求等级从小到大排列：1, 2, 3, \dots, N。
A 想要尽可能多赢，可以尝试从最小的等级开始赢起。
2. 构造“链式获胜”
假设我们要赢下 B 的前 k 小的等级（即 1 \sim k）：
- A 的出牌：A 使用 2, 3, \dots, k+1 分别去赢 B 的 1, 2, \dots, k。
- 代价：A 手里剩下的最小牌是 1，而 B 剩下的最小牌是 k+1。此时 A 的 1 必输给 B 的 k+1。
- 剩余处理：对于 k+2 \dots N，A 和 B 手里剩下的牌都是一样的（都是 k+2 \dots N）。与其冒险输掉，不如直接“兑子”打平，互不得分。
3. 唯一的变量：分割点 k
基于上述策略，A 的得失情况完全由 k 决定：
- A 赢的部分：击败 B 的等级 1 \sim k。A 获得的资源量为这些等级对应的天数之和。
- B 赢的部分：B 的等级 k+1 击败 A 的 1。B 获得的资源量为等级 k+1 对应的天数。
- 平局部分：等级 > k+1 的部分全部打平，得分为 0。
4. 算法流程
- 预处理映射：我们需要快速知道“等级 x 是在第几天提交的”。构建一个数组
dayOfRank[]，其中dayOfRank[v]表示等级 v 对应的天数（也就是那天的资源价值）。 - 枚举 k：k 可以取 1 到 N-1 的所有值。
- 计算当前的收益：
A的总分(等级 1 \sim k 的天数和) -B的总分(等级 k+1 的天数)。
- 计算当前的收益：
- 取最大值：在所有可能的 k 中取最大差值。
此方法只需遍历一次 k，时间复杂度为 O(N)，可以完美通过 10^5 的数据。
参考代码一（Java）
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
// dayOfRank[v] 存储的是：等级 v 出现在第几天（即价值）
// 数组大小开 N+2 是为了防止 k+1 越界
int[] dayOfRank = new int[n + 2];
for (int day = 1; day <= n; day++) {
int rank = sc.nextInt();
dayOfRank[rank] = day;
}
long maxDiff = Long.MIN_VALUE;
long sumA = 0;
// 枚举分割点 k
// 策略：A 赢下 B 的等级 1~k，输掉等级 k+1
// k 代表 A 赢下的数量
for (int k = 1; k < n; k++) {
// A 赢下等级 k (累加对应的天数价值)
sumA += dayOfRank[k];
// B 赢下等级 k+1 (获取对应的天数价值)
long valB = dayOfRank[k + 1];
// 计算差值
long currentDiff = sumA - valB;
if (currentDiff > maxDiff) {
maxDiff = currentDiff;
}
}
System.out.println(maxDiff);
}
}
解题思路二（暴力全排列 DFS）
如果在考场上想不到上述的贪心规律，或者数据规模较小（N \le 11，对应 20% 的分数），我们可以使用暴力搜索。
1. 核心思想
直接枚举 A 部门所有可能的出牌顺序（全排列）。
对于 A 的每一种排列方案，模拟 N 天的比赛过程，计算 (A得分 - B得分)，最后取最大值。
2. 复杂度分析
N 的全排列数量是 N!。
- 当 N=10 时，10! \approx 3.6 \times 10^6，计算机可以在 1 秒内算完。
- 当 N > 12 时，会超时。
此方法适合拿保底分。
参考代码二（Java 暴力 DFS）
import java.util.Scanner;
public class Main {
static int n;
static int[] bSeq; // B 的出牌顺序
static int[] aSeq; // A 的出牌顺序（搜索中生成）
static boolean[] used; // 标记 A 的数字是否用过
static long maxResult = Long.MIN_VALUE;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
bSeq = new int[n + 1];
for (int i = 1; i <= n; i++) {
bSeq[i] = sc.nextInt();
}
aSeq = new int[n + 1];
used = new boolean[n + 1];
// 开始暴力搜索 A 的排列
dfs(1);
System.out.println(maxResult);
}
// 搜索第 step 天 A 应该出什么牌
static void dfs(int step) {
// 边界：N 天都安排好了
if (step > n) {
calculateScore();
return;
}
// 尝试 A 在第 step 天出 1~N 中的某一张牌
for (int i = 1; i <= n; i++) {
if (!used[i]) {
used[i] = true;
aSeq[step] = i;
dfs(step + 1);
used[i] = false; // 回溯
}
}
}
// 计算当前 A 的排列方案下的最终得分差
static void calculateScore() {
long scoreA = 0;
long scoreB = 0;
for (int day = 1; day <= n; day++) {
int valA = aSeq[day];
int valB = bSeq[day];
if (valA > valB) {
scoreA += day;
} else if (valA < valB) {
scoreB += day;
}
// valA == valB 时作废，都不加分
}
maxResult = Math.max(maxResult, scoreA - scoreB);
}
}
