指导老师：毛明松
编撰：衷铭川（大数据 231 班，程设协会负责人）
友链：其实连按部就班也比想象中难
江西财经大学信息管理与数学学院编程会、计算机与人工智能学院程序设计竞赛协会

# 搜索训练的意义

在蓝桥杯竞赛中，搜索是一种强大的工具，解决诸如路径查找、排列组合、状态转移的问题，遍历图或树的所有可能路径。
有时，暴力搜索会直接爆炸 $TLE$，剪枝也是搜索中不可或缺的一环。

# 题目

题目集链接：https://vjudge.net/contest/700913#overview
题目集密码：$duoxichangan$
$VJ$ 比较抽象，可能需要～～ 魔法～～科学上网
排行榜链接：https://vjudge.net/contest/700913#rank

# 全排列问题

# 题目背景

按照字典序输出自然数 $1$ 到 $n$ 所有不重复的排列，即 $n$ 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。

# 输入格式

一个整数 $n$.

# 输出格式

由 $1 \sim n$ 组成的所有不重复的数字序列，每行一个序列。
每个数字保留 $5$ 个场宽。

# 数据范围

$1 \leq n \leq 9$。

# 解题思路

观察可知，题目数据范围及小，就算暴力枚举所有情况，情况数也才 $9!$ 种，故考虑暴力搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

int n, a[10], num[10];
bool st[10];

void dfs(int u) {
    if (u == n + 1) {
        for (int i = 1; i <= n; i++)
            printf("%5d", num[i]);
        puts("");
        return;
    }

    for (int i = 1; i <= n; i++)
        if (!st[i])
            num[u] = i, st[i] = 1, dfs(u + 1), st[i] = 0;
}

void solve () {
    cin >> n;
    dfs(1);
}

# Count Simple Paths

# 题目背景

有一个由 $H \times W$ 个单元格组成的网格。让 $(i, j)$ 表示从上往下第 $i$ 行，从左往上第 $j$ 列的单元格。
如果 $S_{i,j}$ 是 . ，则单元格 $(i, j)$ 为空；如果是 # ，则单元格 $(i, j)$ 被阻塞。
计算从一个空单元格开始，向相邻单元格（向上、向下、向左或向右）进行 $K$ 移动，而不经过被阻塞的方格，也不多次访问同一单元格的方法的数目。
具体地说，计算满足以下条件的长度为 $K+1$ , $((i_0, j_0), (i_1, j_1), \dots, (i_K, j_K))$ 的序列的个数。

• $1 \leq i_k \leq H$ 、 $1 \leq j_k \leq W$ 和 $S_{i_k, j_k}$ 为 "."，每个 $0 \leq k \leq K$ 为 .
• $|i_{k+1} - i_k| + |j_{k+1} - j_k| = 1$ 为每个 $0 \leq k \leq K-1$。
• 每个 $0 \leq k < l \leq K$ 的 $(i_k, j_k) \neq (i_l, j_l)$.

# 数据范围

• $1 \leq H, W \leq 10$.
• $1 \leq K \leq 11$.
• $H$, $W$, and $K$ are integers.
• Each $S_{i,j}$ is . or # .

# 解题思路

枚举每一个出发点，向四个方向中可以走的方向搜索，只要步数到达 $k$ 次，那么 $ans$ 就加上 $1$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

s = ['' for _ in range(20)]
flag = [[0 for _ in range(11)] for _ in range(11)]
res = 0

(h, w, k) = map(int, input().split())

def dfs(x, y, t):
    global res
    if t == k:
        res += 1
        return
    
    for i in range(4):
        xx = x + dx[i]
        yy = y + dy[i]

        if (xx >= 0 and xx < h and yy >= 0 and yy < w and s[xx][yy] == '.' and flag[xx][yy] == 0):
            flag[xx][yy] = 1
            dfs(xx, yy, t + 1)
            flag[xx][yy] = 0

for i in range(h):
    s[i] = input()

for i in range(h):
    for j in range(w):
        if s[i][j] == '.':
            flag[i][j] = 1
            dfs(i, j, 0)
            flag[i][j] = 0
    
print(res, end = '')

# Keep Distance

# 题目背景

给你整数 $N$ 和 $M$.
请按词序打印所有长度为 $N$ 的整数序列 $(A_1, A_2, \ldots, A_N)$.

• $1 \leq A_i$.
• 从 $2$ 到 $N$ 的每个整数 $i$ 的 $A_{i - 1} + 10 \leq A_i$.
• $A_N \leq M$.

什么是词典顺序？
长度为 $N$ 的序列 $S = (S_1, S_2, \ldots, S_N)$ 在词典顺序上小于长度为 $N$ 的序列 $T = (T_1, T_2, \ldots, T_N)$ ，当且仅当存在一个整数 $1 \leq i \leq N$ 使得以下两个条件都成立：

1. $(S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1})$.
2. $S_i$ 小于 $T_i$ （数字）.

# 数据范围

• $2 \leq N \leq 12$.
• $10N - 9 \leq M \leq 10N$.

# 解题思路

若第 $i$ 层时的 $A_i$​ 值为 $d$，那么下一层的可能取 $[d+10,~M-10(n-i)]$.
我们将这些可能性枚举深搜下一层，用一个 $k$ 数组来存当前的状态。
当搜到 $N$ 层时，如果满足题目条件，则就将 $k$ 的 N 个元素存入答案，否则直接返回，下一次的搜索会覆盖原先的 $k_i$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

int n, m, sum, ans[1000000][13], k[13];

void dfs(int i, int d) {
    if (i > n) {
        sum++; // 存数量
        for (int j = 1; j <= n; j++)
            ans[sum][j] = k[j];
    }
    else {
        for (int j = d; j + (n - i) * 10 <= m; j++) { // 条件枚举
            k[i] = j; // 存状态
            dfs(i + 1, j + 10); // 搜索下一层
        }
    }
}

void solve() {
    cin >> n >> m;
    dfs(1, 1);
    for (int i = 1; i <= sum; i++) {
        for (int j = 1; j <= n; j++)
            cout << ans[i][j] << " ";
        cout << endl;
    }
}

# 八皇后

# 题目背景

一个如下的 $6 \times 6$ 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 $2\ 4\ 6\ 1\ 3\ 5$ 来描述，第 $i$ 个数字表示在第 $i$ 行的相应位置有一个棋子，如下：
行号 $1\ 2\ 3\ 4\ 5\ 6$
列号 $2\ 4\ 6\ 1\ 3\ 5$
这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 $3$ 个解。最后一行是解的总个数。

# 输入格式

一行一个正整数 $n$，表示棋盘是 $n \times n$ 大小的。

# 输出格式

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

# 数据范围

对于 $100\%$ 的数据，$6 \le n \le 13$.

# 解题思路

题目有以下要求:

1. 每行只能有一个
2. 每列只能有一个
3. 每条对角线（包括两条主对角线的所有平行线）上至多（可以没有）有一个棋子

前两个要求很容易就达成了，只需要从第 $1$ 行开始，搜到第 $n$ 行（显然行不会重复）。
枚举 a[i] （代表在第 $i$ 行放在第 $a_i$ 列）， a[i] 需要是之前没被枚举过的（显然列也不会重复）。
因为要放的棋子是 $n$ 个，所以前两个要求便被满足了。

那么第三个要求要怎么满足呢？我们不妨把行列坐标画一下：

观察有，同一条正对角线（左上到右下）的行列之和相等，反对角线（右上到左下）的行列数满足：总行数 - 行 + 列 + $i$（第 $i$ 列）相等，故由此衍生出代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

int n, a[14], hang[14], dg[27], udg[27], cnt = 0;
bool st[14];

void dfs(int u) {
    if (u == n + 1) {
        cnt++;
        if (cnt <= 3) {
            for (int i = 1; i <= n; i++)
                cout << a[i] << " ";
            cout << endl;
        }
    }

    for (int i = 1; i <= n; i++) {
        if (!st[i] && !dg[u + i] && !udg[n - u + i]) {
            st[i] = dg[u + i] = udg[n - u + i] = 1, a[u] = i;
            dfs(u + 1);
            st[i] = dg[u + i] = udg[n - u + i] = 0;
        }
    }
}

void solve () {
    cin >> n;
    dfs(1);
    cout << cnt << endl;
}

# Minimum XOR Path

# 题目背景

给你一个简单相连的无向图，图中有 $N$ 个顶点，编号为 $1$ 到 $N$，有 $M$ 条边，编号为 $1$ 到 $M$ 。边 $i$ 连接顶点 $u_i$ 和 $v_i$ ，其标签为 $w_i$.
在从顶点 $1$ 到顶点 $N$ 的所有简单路径（不经过同一顶点多次的路径）中，求路径上边的标签的最小异或值。

关于位向 XOR 对于非负整数 $a$ 和 $b$，$a \oplus b$ 的定义如下：
在 $a \oplus b$ 的二进制表示中，当且仅当 $a$ 和 $b$ 的 $2^k$ 位上的数字中正好有一位是 $1$ 时， $2^k$ 位（ $k \ge 0$ ）上的数字是 $1$ ；否则，它是 $0$.
例如， $3 \oplus 5 = 6$ （二进制为 $011 \oplus 101 = 110$ ）。
一般来说，对于 $k$ 非负整数 $x_1, x_2, \ldots, x_k$ ，它们的比特 XOR $x_1 \oplus x_2 \oplus \cdots \oplus x_k$ 定义为 $(\cdots((x_1 \oplus x_2) \oplus x_3) \oplus \cdots) \oplus x_k$ ，这与 $x_1, x_2, \ldots, x_k$ 的阶数无关。
可以证明，在这个问题的约束条件下，可能的值是有限的。

# 数据范围

${2} \le {N} \le {10}$
${N-1} \le {M} \le {\frac{N(N-1)}{2}}$
${1} \le {u_i} \le {v_i} \le {N}$
${0} \le {w_i} < {2^{60}}$

# 解题思路

看起来这题好像是最短路？其实不然。
观察到，数据范围极小，为什么不用搜索呢？
其实这题就是一道套了层图论皮的搜索水题，维护当前搜到的所有边的异或值，继续往当前点能走到的点继续搜即可。
有一个细节需要注意，初始化时 $1e18$ 还是太小了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

int n, m;
bool st[20];
vector<PII> graph[14];
int ans = LONG_LONG_MAX;

void dfs(int u, int res) {
    if (u == n) {
        ans = min(ans, res);
        return;
    }

    for (auto t : graph[u]) {
        int v = t.first, w = t.second;

        if (st[v])
            continue;

        st[v] = 1;
        dfs(v, res ^ w);
        st[v] = 0;
    }
}

# 数的划分

# 题目背景

将整数 $n$ 分成 $k$ 份，且每份不能为空，任意两个方案不相同（不考虑顺序）。
例如：$n=7$，$k=3$，下面三种分法被认为是相同的。
$1,1,5$;
$1,5,1$;
$5,1,1$.
问有多少种不同的分法。

# 输入格式

$n,k$ （$6<n \le 200$，$2 \le k \le 6$）

# 输出格式

$1$ 个整数，即不同的分法。

# 解题思路

题目要求：方案必须不相同。
可以发现，答案一定是一个单调不减序列，则我们在搜索的时候可以有以下规律：

$$a_{j-1} \le {a_j} \le \lfloor\frac{n-\sum\limits_{i=1}^{j-1} a_i}{k-j-1}\rfloor$$

则由此可以得出以下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

int n, k;

// n 还有多少个数可以被分
// k 当前枚举到第几个数
// u 当前的数最小可以划分为多少（上一个数是多少）
int dfs(int n, int k, int u) {
    if (k == 1)
        return 1;
    int sum = 0;
    for (int i = u; i <= n / k; i++)
        sum += dfs(n - i, k - 1, i);
    return sum;
}

void solve () {
    cin >> n >> k;
    cout << dfs(n, k, 1);
}

# Stone XOR

# 题目描述

# 问题陈述

有 $N$ 个袋子，分别标有袋子 $1$ 、袋子 $2$ 、 $\ldots$ 、袋子 $N$.
袋子 $i$ （ $1 \leq i \leq N$ ）装有 $A_i$ 颗石子。
高桥可以进行以下任意次数的操作，可能为零：

选择两个袋子 $A$ 和 $B$，将 $A$ 袋的所有棋子移入 $B$ 袋。

问：在重复操作后，求以下不同可能值的个数。

• $B_1 \oplus B_2 \oplus \cdots \oplus B_N$ ，其中 $B_i$ 是袋子 $i$ 中石头的最终数量。
  • 这里， $\oplus$ 表示异或。

关于位向 XOR 对于非负整数 $a$ 和 $b$，$a \oplus b$ 的定义如下：
在 $a \oplus b$ 的二进制表示中，当且仅当 $a$ 和 $b$ 的 $2^k$ 位上的数字中正好有一位是 $1$ 时， $2^k$ 位（ $k \ge 0$ ）上的数字是 $1$ ；否则，它是 $0$.
例如， $3 \oplus 5 = 6$ （二进制为 $011 \oplus 101 = 110$ ）。
一般来说，对于 $k$ 非负整数 $x_1, x_2, \ldots, x_k$ ，它们的比特 XOR $x_1 \oplus x_2 \oplus \cdots \oplus x_k$ 定义为 $(\cdots((x_1 \oplus x_2) \oplus x_3) \oplus \cdots) \oplus x_k$ ，这与 $x_1, x_2, \ldots, x_k$ 的阶数无关。
可以证明，在这个问题的约束条件下，可能的值是有限的。

# 数据范围

• ${2} \le {N} \le {12}$.
• ${1} \le {A_i} \le {10^{17}}$

# 解题思路

在解这题的之前你需要知道

1. 异或概念（题目中有描述，此处不再赘述）
2. 这个公式： a ^ b ^ b = a

接下来就可以开始写代码了.

• 对于第 $i$ 个盒子，你可以在前 $i-1$ 个盒子中，任选盒子进行操作。
  注意，此题用 map 会被卡成 $TLE$，应该用 unordered_map
  （可自行了解二区别）
  

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  int n, a[13], ans = 0; unordered_map<int, int> mp; void dfs(int u, int res) { if (u == n + 1) { if (!mp[res]) ans++; mp[res] = 1; return; } dfs(u + 1, res ^ a[u]); for (int i = 1; i < u; i++) if (a[i] != 0) { int x = a[i]; a[i] = 0, a[u] += x; dfs(u + 1, res ^ a[u] ^ x); a[i] = x, a[u] -= x; } }