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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
|
---
marp: true
theme: default
math: mathjax
---
# 2026/02/13 搜索 & 字符串
---
# 1. 搜索
+ 剪枝
+ A*
+ 迭代加深
---
# 剪枝
(搜索的复杂度很高，因此很少作为正解出现，绝大多数情况下还是一种骗分的方法。我们要尽可能的优化，才能骗到更多的分)
常见经典剪枝方法：
+ a. 记忆化搜索
+ b. 最优性剪枝
+ c. 可行性剪枝
许多题目都需要同时用多种剪枝优化。
---
# a. 记忆化搜索
可以看做递归版的 DP
**例题：[P1434 [SHOI2002] 滑雪](https:
---
# b. 最优性剪枝
最优性剪枝：当前已不可能优于已知最优解
if (当前价值 + 最优估计 <= 当前最优解) return;
---
# c. 可行性剪枝
if (剩余的资源在最优利用情况下仍不能满足条件) return;
**例题：[P2329 [SCOI2005] 栅栏](https:
---
上述几种只是通用的套路，而往往最关键的优化是根据题目具体情境产生的。
**例题：[P1731 [NOI1999] 生日蛋糕](https:
1. 搜索方向
2. 最优性剪枝（预估最优答案）
3. 可行性剪枝（剩余体积过多）
数据加强版还需要其他具体的优化。
---
# A*
A* 是一种在带权有向图上，找到从起点到终点最短路径的算法。
核心：$f(x) = g(x) + h(x)$
即假设我们要从点 $s$ 走到点 $t$，当前处于点 $x$。
$g_{s\rightarrow x}$ 是已知代价，而关键在于设置预估函数 $h_{x\rightarrow t}$
---
我们维护一个优先队列，每次取出 $f$ 最小的位置进行扩展。（详细演示）
若 $h\equiv h'$，即估计是完全精确的，那么我们就会严格按照最优路径行进。
若 $h\equiv 0$，那么就退化成了 $\text{Dijkstra}$ 算法。
若 $h\equiv 0$ 且边权为 $1$，那么就是 $\text{BFS}$
---
$h(x)$ 需要满足的两个基本条件：
+ 可采纳性：$h(x)\leq h'(x)$，即从 $x$ 出发的后续预估代价不超过从 $x$ 出发的实际最优后续代价。
+ 证明：汇点的处理。
+ 其可以推导出 $\Rightarrow f(x)=g(x)+h(x)\leq ans$（并非等价条件）
+ 一致性：$h(x)\leq h(y)+d(x,y)$
+ 这使得 $f$ 是非降的。
**例题：[P1379 八数码难题](https:
---
**迭代加深$(\text{IDS})$**
应用场景：$\text{DFS}$ 可能会陷入错解，而 $\text{BFS}$ 空间过大。
即答案深度未知，相对来说时间充足但内存有限的情况。
重复的都是浅层路径，因此实际复杂度与 $\text{BFS}$ 相差不会过大
在一些用搜索骗分的情况下，$\text{IDS}$ 往往能搜索到较深的层级（多一层），增大找到正解的概率。
而在 $\text{IDS}$ 能保证正确性的题目中，$\text{BFS}$ 一般也可以。
**[例题：P10494 [USACO02FEB] Power Hungry Cows](https:
---
+ $\text{IDA*}=\text{IDS}+\text{A*}$
**[例题：P2324 [SCOI2005] 骑士精神](https:
---
# 2. 字符串
+ $\text{Hash}$
+ $\text{KMP}$
+ $\text{Trie}$
---
# Hash / 哈希
**（基础知识）**
字符串中，我们可以让每一个字符串对应一个值，将所有串映射到一个较小的值域中，从而可以便捷地进行比较操作。
考虑一个多位数字的组成，有进制和位数两个关键元素。类似的，我们也可以设置能包含所有字符的进制，每位即是一个字符。
但这样的数字通常不小，我们可以再添加一个模数，将哈希值限制在一个可以接受的区间内。
---
比如说一个小写字母的字符串，我们可以将 $a$ 到 $z$ 分别对应到 $1$ 至 $26$，进制为 $114$，模数为 $514$：
abcd -> (1 * 114^3 + 2 * 114^2 + 3 * 114^1 + 4 * 114^0) % 514
+ 以类似数的形式设置哈希值，可以让我们 $O(1)$ 直接计算字符串的结合 / 分割。
**（哈希冲突）**
显然，由于模的存在，存在两个字符串的哈希值相等的情况难以避免，我们将其称为哈希冲突。
好的进制 & 模数可以降低哈希冲突出现的概率：
+ 一般选取质数，因为如果存在公因子，可能出现规律的哈希冲突。
+ 模数要适当的增大，从而增大值域。
---
**（多哈希）**
更进一步，我们也可以设置多个映射函数。不同的字符串，对于两种映射方式，冲突的概率会大大降低。
**（哈希表）**
对于某个哈希值可能出现的冲突，我们可以直接将所有哈希值等于此的原串以链表的形式存储下来（当然，原串数量需要可接受），单次查询的复杂度接近 $O(1)$。
+ $\text{STL}$ unordered_map 便是基于此实现的。
[P3370 【模板】字符串哈希](https:
[U461211 字符串 Hash（数据加强）](https:
---
## T1. [CF1200E Compress Words](https:
---
## T2. [P4824 [USACO15FEB] Censoring S](https:
相似题
---
## T3. [P3498 [POI 2010] KOR-Beads](https:
---
## T4. [P4503 [CTSC2014] 企鹅 QQ](https:
+ 可错配问题
---
本题为一次错配，只需要逐一枚举可能的错配点判断即可。
对于 $k$ 次错配的问题，可以先选取两个要比较的字符串，二分从开始能匹配的最长距离，再暴力走错配点，复杂度 $O(m+kn\log m)$，其中 $n$ 为字符串数量，$m$ 为所有字符串总长。
---
# KMP
$\text{KMP}$ 算法可以通过线性预处理，解决字符串匹配的问题。
+ $\text{border}$：一个子串即是前缀也是后缀。
如 abc*!@&%~abc
abc 就是原串的一个 border。
（如果你想在目标串上对模式串尝试匹配，可以在目标串前加一模式串，这样能匹配的位置就是一个 $\text{border}$。
+ $\text{next}$ 数组：对于当前选定字符串 $s$，最长的既是真前缀也是真后缀的子串长度，即小于 $|s|$ 的最长的 $\text{border}$ 长。
$\text{KMP}$ 的最直接目的是在线性的时间下处理出 $\text{next}$ 数组：
---
重要性质：下一个 $\text{next}$ 数组的值最多增加 1。
+ 反证法：若 $\text{next}[i+1]-\text{next}[i]=a-b>1$，则在位置 $i+1$ 基础上两个 $\text{border}$ 同时在末端除去一个元素，可得 $i$ 处的一个 $\text{border}$ 长度为 $a-1(>b)$。
---
for(int i = 1, j = 0; i < n; ++ i ){
while(j && s[i] != s[j]) j = next[j];
if(s[i] == s[j]) ++j;
next[i] = j;
}
for(int i = 2, j = 0; i <= n; ++ i ){
while(j && s[i] != s[j + 1]) j = next[j];
if(s[i] == s[j + 1]) ++j;
next[i] = j;
}
补充：$\text{next}$ 数组与树的联系。
**[P3375 【模板】KMP](https:
---
## T1. **[P4391 [BalticOI 2009] Radio Transmission 无线传输](https:
---
## T2. **[P3435 [POI 2006] OKR-Periods of Words](https:
+ 弄清题意与 $\text{border}$ 的确切关系。
（注意：周期的定义以题干为准）
---
答案求的是：每个位置结束的子串，总长减去最小的 $\text{border}$ 长度，所有位置的总和。（如果没有 $\text{border}$ 则没有贡献）
---
## T3. **[P4824 [USACO15FEB] Censoring S](https:
+ 对于一个无序或任意的问题，可以先定序
+ KMP 是一个在线算法。
---
## T4. **[P2375 [NOI2014] 动物园](https:
---
题意转化：对每个位置结束的子串 $s[1,k]$，对所有长度小于 $\lfloor\frac{|s|}{2}\rfloor$ 的 $\text{border}$ 计数。
但是直接将 $1/2$ 的限制放到 KMP 过程中是不可行的，为什么？
……
所以需要二次计数。
---
## 选做：
**[P3426 [POI 2005] SZA-Template](https:
+ 最好不要盲目抄代码，可以尝试了解多个题解的思路。
---
# Trie / 字典树
Trie 可以用于维护字符串，进行匹配操作等。
**[P8306 【模板】字典树](https:
---
## T1. **[P4407 [JSOI2009] 电子字典](https:
---
虽然字符串总长 $N\times L=2e5$，但要考虑到每层只有 26 个分支，因而实际遍历的数量级要低一些。这样就可以放心暴力了……
---
Trie 也可以用来维护 01 串（广义上也算是字符串，但这部分与数学关联更多）：
## T2. **[P4551 最长异或路径](https:
---
用 $v_{x,y}$ 代表 $x$ 与 $y$ 之间简单路径的异或和，那么对于任意节点 $a,b,c$，可知有 $v_{a,b}=v_{a,c}\space \text{xor}\space v_{b,c}$。
那么不妨选中一个节点作为根，逐一查询最大异或和后插入 Trie 树中（在线）。
---
## T3. **[CF1416C XOR Inverse](https:
---
每一位的计算都是独立的。
一个数从高到低插入，对于某一个分岔点来说，每个数异或 $x$ 的可能影响是交换两个 Trie 树的子节点。如果 $x$ 的当前位选择了 $1$，那么本层所有节点都要转换，所有要按层整体计算答案。
|