题目
找倍数（BFS + 同余剪枝）
解题思路
题目关键特征
给定正整数 n（1 ≤ n ≤ 200），要求找到一个最短的正整数 m，满足：
m是n的倍数；m的十进制表示仅由数字 '0' 和 '1' 构成；m不能以 '0' 开头（隐含第一位为 '1'）。
由于答案可能长达上百位，无法用 long 或 BigInteger 暴力枚举倍数，必须避免显式构造大整数。
算法适用条件
问题本质是在无限状态空间中搜索满足整除条件的最短字符串。BFS 天然适用于“最短路径”类问题，而本题的状态可压缩为当前构造数字对 n 的余数，状态总数不超过 n（即 0 到 n-1），因此 BFS 在有限步内必终止。
BFS搜索步骤演示动图
问题转化思路
将“构造只含 0/1 的数字”转化为从字符串 "1" 出发，每次在末尾追加 '0' 或 '1' 的状态扩展过程。关键洞察在于：
若两个不同数字
a和b满足a % n == b % n，则它们后续添加相同后缀产生的新数对n的余数也相同。因此，每个余数只需保留首次出现的最短路径。
由此，搜索空间从指数级字符串集合压缩为最多 n 个余数状态。
有效剪枝手段
使用 visited 集合记录已出现的余数。若某余数 r 已被访问，则跳过所有后续产生 r 的更长字符串。此剪枝保证：
- 每个余数仅入队一次；
- BFS 首次到达余数
0时对应的字符串即为最短解； - 时间复杂度为 O(n)，空间复杂度为 O(n)。
若不剪枝，队列将无限增长（如 "10", "100", "1000", ... 均余 4 mod 6），导致超时或内存溢出。
余数递推机制
为避免大数运算，采用逐位取模计算余数：
remainder = (remainder * 10 + digit) % n
该公式基于模运算分配律：(a * 10 + d) % n = ((a % n) * 10 + d) % n。由此可在 O(len(s)) 时间内计算任意长度字符串的余数，且中间值始终小于 n。
参考代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String m = bfs(n);
System.out.println(m);
}
private static String bfs(int n) {
Queue<String> queue = new LinkedList<>();
// 记录已经出现过的余数: 每个余数只需处理一次, 保证最短路径
Set<Integer> visited = new HashSet<>();
// 起始状态: 第一位必须是 '1', 不能以 '0' 开头
queue.offer("1");
// 初始余数为 1 % n, 但暂不加入 visited (在扩展时统一处理)
while (!queue.isEmpty()) {
String s = queue.poll();
// 逐位计算 s 对 n 的余数, 避免大数溢出
int remainder = 0;
for (char c : s.toCharArray()) {
remainder = (remainder * 10 + (c - '0')) % n;
}
// 终止条件: 余数为 0 表示 s 是 n 的倍数
if (remainder == 0) {
return s;
}
// 尝试在当前字符串末尾追加 '0' 和 '1'
String s0 = s + "0";
String s1 = s + "1";
// 利用余数递推公式快速计算新余数, 无需重新遍历整个字符串
int r0 = (remainder * 10 + 0) % n;
int r1 = (remainder * 10 + 1) % n;
// 剪枝: 若余数未出现过, 则加入队列并标记
if (!visited.contains(r0)) {
visited.add(r0);
queue.offer(s0);
}
if (!visited.contains(r1)) {
visited.add(r1);
queue.offer(s1);
}
}
// 根据鸽巢原理, 解必然存在, 此处不会执行
return "";
}
}
八数码（BFS状态搜索）
解题思路
题目关键特征
本题是经典的八数码问题（8-puzzle），目标是通过移动空格（x）与相邻数字交换，将初始 3×3 网格变换为目标状态 12345678x。每一步操作只能交换 x 与其上下左右的数字，求最少步数。
算法适用条件
- 状态空间有限：3×3 网格共有 9! / 2 = 181440 个可达状态（因奇偶性限制），适合 BFS 枚举
- 最短路径要求：BFS 天然保证首次到达目标状态时步数最少
- 状态可编码：将 3×3 网格压缩为长度为 9 的字符串（如
"1234x6758"），便于哈希存储和比较
有效剪枝手段
- 全局状态去重：使用
Set<String> visited记录所有已访问的完整棋盘布局，避免重复搜索- ❌ 错误做法：仅记录
x的位置（不同布局下x可在同一位置） - ✅ 正确做法：整个字符串作为状态唯一标识
- ❌ 错误做法：仅记录
- 边界检查：交换前验证新坐标
(nx, ny)是否在[0, 2]范围内
问题转化思路
将网格操作转化为状态图搜索：
- 节点 = 一种棋盘布局（字符串）
- 边 = 一次合法的
x与邻居交换 - 起点 = 输入字符串，终点 =
"12345678x" - 搜索策略 = BFS（逐层扩展，首次命中即最优）
💡 类比：迷宫中状态是坐标
(x,y)，而八数码中状态是整个棋盘——因为“怎么来的”会影响后续可能性。
参考代码
import java.util.*;
public class Main {
static int n = 3;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
StringBuilder sb = new StringBuilder();
// 读取9个字符（含'x'），拼接成初始状态字符串
for (int i = 1; i <= n * n; i++) {
sb.append(sc.next());
}
String start = sb.toString();
// 目标状态固定为"12345678x"
int result = bfs(start, "12345678x");
System.out.println(result);
}
// 四个移动方向：上、下、左、右
static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
/**
* 使用BFS搜索从start到target的最少步数
* @param start 初始棋盘状态（长度为9的字符串）
* @param target 目标状态 "12345678x"
* @return 最少交换次数，若不可达返回-1
*/
private static int bfs(String start, String target) {
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.offer(start);
visited.add(start);
int step = 0;
while (!queue.isEmpty()) {
int size = queue.size();
// 处理当前层的所有状态（步数相同）
for (int i = 0; i < size; i++) {
String state = queue.poll();
// 检查是否达到目标
if (state.equals(target)) {
return step;
}
// 定位空格'x'的位置
int index = state.indexOf('x');
int x = index / n, y = index % n;
// 尝试四个方向的移动
for (int[] dir : dirs) {
int nx = x + dir[0], ny = y + dir[1];
// 检查新位置是否在棋盘内
if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
int newIndex = nx * n + ny;
char[] chars = state.toCharArray();
// 交换空格与相邻数字
char temp = chars[index];
chars[index] = chars[newIndex];
chars[newIndex] = temp;
String newState = new String(chars);
// 若新状态未访问过，则加入队列
if (!visited.contains(newState)) {
queue.offer(newState);
visited.add(newState);
}
}
}
}
// 当前层处理完毕，步数加1
step++;
}
// 队列空仍未找到目标，说明不可达
return -1;
}
}
djwcb
解题思路（循环节发现与快速幂）
题目关键特征
给定极大指数 p（可能长达 20 万位），求 x^p mod 10。由于 p 远超任何整型范围，不能直接计算幂，必须寻找规律或数学性质。
从实验出发：观察个位数的幂次规律
结果仅依赖个位：x^p mod 10 等价于 (x mod 10)^p mod 10，所以我们只需要关注个位数的 p次幂是什么样的
我们先写一个小程序，打印 0~9 每个数字的前若干次幂的个位数：
public static void main(String[] args) {
for (int i = 0; i <= 9; i++) {
test(i);
}
}
private static void test(long num) {
System.out.print(num + ":\t");
long base = num;
for (int i = 1; i <= 12; i++) {
base %= 10;
System.out.print(base + "\t");
base *= num;
}
System.out.println();
}
运行结果如下：
0: 0 0 0 0 0 0 0 0 0 0 0 0
1: 1 1 1 1 1 1 1 1 1 1 1 1
2: 2 4 8 6 2 4 8 6 2 4 8 6
3: 3 9 7 1 3 9 7 1 3 9 7 1
4: 4 6 4 6 4 6 4 6 4 6 4 6
5: 5 5 5 5 5 5 5 5 5 5 5 5
6: 6 6 6 6 6 6 6 6 6 6 6 6
7: 7 9 3 1 7 9 3 1 7 9 3 1
8: 8 4 2 6 8 4 2 6 8 4 2 6
9: 9 1 9 1 9 1 9 1 9 1 9 1
关键发现：
- 所有个位数的幂次个位都会进入循环
- 最长循环节长度为 4（如 2、3、7、8）
- 其余要么是 1（如 0、1、5、6），要么是 2（如 4、9）
这意味着：只要知道 p 对 4 取余的结果，就能确定最终个位数！
📌 注意：如果
p % 4 == 0，说明刚好走完若干个完整循环，应取第 4 项（而不是第 0 项）。
如何对超大指数 p 取模 4？
题目中 p 是一个可能长达 20 万位的字符串。但我们知道：
- 一个数是否能被 4 整除，只看最后两位（因为 100 是 4 的倍数）
- 例如：
123456→ 看56，56 % 4 = 0→ 整个数能被 4 整除
因此，只需提取 p 的最后 1~2 位转成整数，再对 4 取模即可。
特殊情况处理
- 若
x % 10 == 0（即个位是 0），则无论多少次幂（只要 p ≥ 1），结果都是 0
额外知识点：快速幂思想简介（了解即可）
虽然本题因模 10 的特殊性不需要复杂算法，但快速幂是处理大指数幂取模的通用技巧，值得了解。
什么是快速幂？
快速幂是一种用 O(log p) 时间计算 a^p mod m 的方法，核心思想是二进制拆分指数。
例如：
a^13 = a^(8+4+1) = a^8 * a^4 * a^1
而 a^2 = a*a, a^4 = (a^2)^2, a^8 = (a^4)^2……每次平方即可得到更高次幂。
为什么本题不用标准快速幂？
因为 p 是字符串形式，做“除以 2”或“判断奇偶”需要高精度操作，代码复杂。
但我们可以用十进制快速幂：从低位到高位处理每一位数字，并利用 x^10 ≡ x^2 (mod 10) 的性质简化计算（见方法三）。
💡 建议：先掌握循环节法（方法二），它是本题最直观、高效且易懂的解法。快速幂可后续在处理一般模数（如 mod 1e9+7）时深入学习。
参考代码
方法一：BigInteger 直接计算（Java 特供）
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
BigInteger x = sc.nextBigInteger();
BigInteger p = sc.nextBigInteger();
// 使用BigInteger内置的模幂运算: x^p mod 10
BigInteger result = x.modPow(p, BigInteger.valueOf(10));
System.out.println(result);
}
}
}
方法二：循环节 + 大数取模（推荐）
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int x = sc.nextInt();
String p = sc.next();
int base = x % 10;
if (base == 0) {
System.out.println(0);
continue;
}
int cnt = getMod4(p);
long result = pow(base, cnt);
System.out.println(result);
}
}
/**
* 计算超长数字字符串 p 对 4 取模的结果
* @param p 指数字符串（可能长达200000位）
* @return p mod 4, 若结果为0则返回4（对应循环节最后一项）
*/
private static int getMod4(String p) {
int num;
if (p.length() == 1) {
num = p.charAt(0) - '0';
} else {
// 取末两位（因100是4的倍数，高位不影响mod4）
num = Integer.parseInt(p.substring(p.length() - 2));
}
int mod = num % 4;
return mod == 0 ? 4 : mod;
}
/**
* 计算 base^cnt mod 10（cnt ∈ {1,2,3,4}，直接循环即可）
* @param base 底数个位 (0~9)
* @param cnt 指数 (1~4)
* @return 结果
*/
public static long pow(int base, int cnt) {
long result = 1;
for (int i = 0; i < cnt; i++) {
result = (result * base) % 10;
}
return result;
}
}
方法三：十进制快速幂（扩展）
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int x = sc.nextInt();
String p = sc.next();
long result = modPow(x, p, 10);
System.out.println(result);
}
}
/**
* 十进制快速幂：从低位到高位处理指数字符串
* 利用 mod 10 下 x^10 ≡ x^2 的性质简化倍增步骤
* @param x 底数
* @param p 指数字符串
* @param mod 模数 (此处为10)
* @return x^p mod mod
*/
private static long modPow(int x, String p, int mod) {
x %= mod;
if (x == 0) return 0;
long result = 1;
// 从个位开始逐位处理
for (int i = p.length() - 1; i >= 0; i--) {
int digit = p.charAt(i) - '0';
// 计算当前位贡献: (current_base)^digit
long contrib = 1;
for (int j = 0; j < digit; j++) {
contrib = (contrib * x) % mod;
}
result = (result * contrib) % mod;
// 为下一位准备：x = x^10 mod 10 → 实际只需 x = x^2 mod 10
// 在 mod 10 下, x^10 ≡ x^2 (由循环节性质决定)
x = (x * x) % mod;
}
return result;
}
}
循环逆序对
解题思路(从手算每一块到公式归纳的完整推导)
题目关键特征
给定一个数组，例如 [1, 3, 2]，将其重复 k 次得到新序列，求其中逆序对总数。
由于 k 可达 10^9，不能显式构造序列，必须通过分析每一块的贡献规律求解。
从最小例子开始：原数组 [1, 3, 2]
先看它自己有多少逆序对：
1后面没有比它小的3后面有2→ 1 个2后面没了
✅ 内部逆序对数 intra = 1
再统计每个元素在整个数组中“比它大的数”的个数：
| 元素 | 值 | 比它大的数 | 个数 |
|---|---|---|---|
| a[0] | 1 | 3, 2 | 2 |
| a[1] | 3 | — | 0 |
| a[2] | 2 | 3 | 1 |
总和：2 + 0 + 1 = 3，记作 sumGt = 3
手动计算 k = 1, 2, 3 的总逆序对
k = 1：只有第 0 块
序列：[1,3,2]
逆序对：1 个 → 总数 = 1
k = 2：第 0 块 + 第 1 块
第 1 块每个元素 vs 第 0 块：
| 元素 | 值 | 第0块中比它大的个数 | 跨块贡献 |
|---|---|---|---|
| 1 | 1 | 2 | 2 |
| 3 | 3 | 0 | 0 |
| 2 | 2 | 1 | 1 |
→ 跨块新增：2+0+1 = 3
块内新增：1（第1块内部）
总计：1（原） + 1（新块内） + 3（跨块） = 5
k = 3：三块
第2块前面有两整块，每个元素的跨块贡献翻倍：
| 元素 | 单块比它大的个数 | 两块中比它大的个数 | 贡献 |
|---|---|---|---|
| 1 | 2 | 4 | 4 |
| 3 | 0 | 0 | 0 |
| 2 | 1 | 2 | 2 |
→ 第2块跨块贡献：6块内贡献：1累计：
- 块内：
1×3 = 3 - 跨块：
3（第1块） + 6（第2块） = 9 - 总计：
12
归纳规律
- 块内总贡献 =
k * intra - 跨块总贡献 =
sumGt * (0 + 1 + 2 + ... + (k-1)) = sumGt * k * (k - 1) / 2
因为 k 和 k-1 是连续整数，乘积必为偶数，/2 无精度损失。
参考代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
int MOD = 998244353;
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long k = sc.nextLong();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextInt();
}
// 计算原数组内部逆序对数 intra
long intra = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (a[j] > a[i]) {
intra++;
}
}
}
// 计算每个元素在整个数组中比它大的总数 sumGt
long sumGt = 0;
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < n; j++) {
if (a[j] > a[i]) {
cnt++;
}
}
sumGt += cnt;
}
// 总答案 = k * intra + sumGt * k * (k - 1) / 2
long res = (k % MOD) * (intra % MOD) % MOD;
long t = k * (k - 1) / 2 % MOD; // 安全整除
res = (res + (sumGt % MOD) * t) % MOD;
System.out.println(res);
}
}
旅行II
解题思路(连续区间贪心)
题意
- 有
n个国家，位置是a[0]到a[n-1]（可正可负，可能有 0） - 小蓝从 0 出发，每次走 1 单位距离
- 他要访问 恰好 k 个国家（从这 n 个里选）
- 求最小总移动距离
关键结论
最优方案一定是：
- 选排序后连续的 k 个点
- 路线只有两种：
0 → 最左 → 最右0 → 最右 → 最左
中间的点顺路就走完了，不用额外绕
所以访问区间 [L, R] 的最小代价是：cost = (R - L) + min(|L|, |R|)
💡 为什么必须连续？
假设你跳着选点，比如选了 -10、-5、5、10，但跳过了 0。那换成 -10、-5、0、5 肯定更近——因为区间长度变短了，而且离 0 更近。所以“挤在一起”的连续 k 个点一定更优。
做法
- 把
a数组排序 - 枚举所有长度为
k的连续子数组（i从0到n-k）L = a[i]R = a[i + k - 1]- 算
cost = (R - L) + Math.min(Math.abs(L), Math.abs(R))
- 所有
cost取最小值，输出
时间复杂度 O(n log n)，完全满足 n ≤ 1e5。
参考代码
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) {
a[i] = sc.nextLong();
}
// 按坐标从小到大排序
Arrays.sort(a);
long ans = Long.MAX_VALUE;
// 枚举所有长度为k的连续区间
for (int i = 0; i <= n - k; i++) {
long L = a[i]; // 当前区间的最左端
long R = a[i + k - 1]; // 当前区间的最右端
// 总距离 = 区间长度 + 从0到较近端点的距离
long cost = (R - L) + Math.min(Math.abs(L), Math.abs(R));
if (cost < ans) {
ans = cost;
}
}
System.out.println(ans);
}
}
