-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.toc
executable file
·255 lines (255 loc) · 23 KB
/
main.toc
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
\contentsline {section}{\numberline {1}模拟}{7}{section.1}%
\contentsline {subsection}{\numberline {1.1}进制转换}{7}{subsection.1.1}%
\contentsline {section}{\numberline {2}搜索}{7}{section.2}%
\contentsline {subsection}{\numberline {2.1}总结}{7}{subsection.2.1}%
\contentsline {subsection}{\numberline {2.2}三分}{7}{subsection.2.2}%
\contentsline {subsubsection}{\numberline {2.2.1}整数、浮点数}{7}{subsubsection.2.2.1}%
\contentsline {subsubsection}{\numberline {2.2.2}求极大值}{8}{subsubsection.2.2.2}%
\contentsline {subsection}{\numberline {2.3}折半搜索}{8}{subsection.2.3}%
\contentsline {subsubsection}{\numberline {2.3.1}总结}{8}{subsubsection.2.3.1}%
\contentsline {subsection}{\numberline {2.4}模拟退火}{8}{subsection.2.4}%
\contentsline {section}{\numberline {3}贪心}{9}{section.3}%
\contentsline {subsection}{\numberline {3.1}加工生产调度}{9}{subsection.3.1}%
\contentsline {subsection}{\numberline {3.2}反悔贪心}{10}{subsection.3.2}%
\contentsline {section}{\numberline {4}数论}{11}{section.4}%
\contentsline {subsection}{\numberline {4.1}小经验}{11}{subsection.4.1}%
\contentsline {subsection}{\numberline {4.2}FWT}{12}{subsection.4.2}%
\contentsline {subsubsection}{\numberline {4.2.1}序列中选 1,2,...,n 个数的最大异或和分别为多少}{12}{subsubsection.4.2.1}%
\contentsline {subsection}{\numberline {4.3}Min25筛}{13}{subsection.4.3}%
\contentsline {subsubsection}{\numberline {4.3.1}快速阶层取模}{13}{subsubsection.4.3.1}%
\contentsline {subsection}{\numberline {4.4}Pohlig-Hellman}{17}{subsection.4.4}%
\contentsline {subsubsection}{\numberline {4.4.1}总结}{17}{subsubsection.4.4.1}%
\contentsline {subsubsection}{\numberline {4.4.2}Pohlig-Hellman}{17}{subsubsection.4.4.2}%
\contentsline {subsection}{\numberline {4.5}二次剩余}{23}{subsection.4.5}%
\contentsline {subsubsection}{\numberline {4.5.1}总结}{23}{subsubsection.4.5.1}%
\contentsline {subsubsection}{\numberline {4.5.2}2019牛客多校B}{24}{subsubsection.4.5.2}%
\contentsline {subsubsection}{\numberline {4.5.3}一元二次方程判断是否有解}{26}{subsubsection.4.5.3}%
\contentsline {subsubsection}{\numberline {4.5.4}求所有解}{27}{subsubsection.4.5.4}%
\contentsline {subsection}{\numberline {4.6}反素数}{29}{subsection.4.6}%
\contentsline {subsubsection}{\numberline {4.6.1}总结}{29}{subsubsection.4.6.1}%
\contentsline {subsubsection}{\numberline {4.6.2}求不超过n的最小反素数}{30}{subsubsection.4.6.2}%
\contentsline {subsubsection}{\numberline {4.6.3}求约数个数为n最小反素数}{30}{subsubsection.4.6.3}%
\contentsline {subsection}{\numberline {4.7}各种筛}{31}{subsection.4.7}%
\contentsline {subsubsection}{\numberline {4.7.1}x的质因子个数}{31}{subsubsection.4.7.1}%
\contentsline {subsubsection}{\numberline {4.7.2}矩阵的lcm}{31}{subsubsection.4.7.2}%
\contentsline {subsubsection}{\numberline {4.7.3}素数+欧拉函数+最小质因子}{31}{subsubsection.4.7.3}%
\contentsline {subsection}{\numberline {4.8}康托展开}{32}{subsection.4.8}%
\contentsline {subsubsection}{\numberline {4.8.1}康托展开}{32}{subsubsection.4.8.1}%
\contentsline {subsubsection}{\numberline {4.8.2}康托逆展开}{33}{subsubsection.4.8.2}%
\contentsline {subsection}{\numberline {4.9}扩展欧几里得}{34}{subsection.4.9}%
\contentsline {subsubsection}{\numberline {4.9.1}exgcd}{34}{subsubsection.4.9.1}%
\contentsline {subsubsection}{\numberline {4.9.2}求同余方程}{35}{subsubsection.4.9.2}%
\contentsline {subsection}{\numberline {4.10}离散对数}{35}{subsection.4.10}%
\contentsline {subsubsection}{\numberline {4.10.1}BSGS}{35}{subsubsection.4.10.1}%
\contentsline {subsubsection}{\numberline {4.10.2}EX\_BSGS}{36}{subsubsection.4.10.2}%
\contentsline {subsection}{\numberline {4.11}欧拉函数}{38}{subsection.4.11}%
\contentsline {subsubsection}{\numberline {4.11.1}欧拉函数性质}{38}{subsubsection.4.11.1}%
\contentsline {subsubsection}{\numberline {4.11.2}sqrt(N)}{38}{subsubsection.4.11.2}%
\contentsline {subsubsection}{\numberline {4.11.3}欧拉筛}{38}{subsubsection.4.11.3}%
\contentsline {subsubsection}{\numberline {4.11.4}N\^(0.25)+1e18}{39}{subsubsection.4.11.4}%
\contentsline {subsection}{\numberline {4.12}欧拉降幂}{41}{subsection.4.12}%
\contentsline {subsubsection}{\numberline {4.12.1}费马小定理}{41}{subsubsection.4.12.1}%
\contentsline {subsubsection}{\numberline {4.12.2}欧拉定理}{41}{subsubsection.4.12.2}%
\contentsline {subsubsection}{\numberline {4.12.3}扩展欧拉定理}{41}{subsubsection.4.12.3}%
\contentsline {subsection}{\numberline {4.13}排列组合}{41}{subsection.4.13}%
\contentsline {subsubsection}{\numberline {4.13.1}总结}{41}{subsubsection.4.13.1}%
\contentsline {subsubsection}{\numberline {4.13.2}排列组合公式}{41}{subsubsection.4.13.2}%
\contentsline {subsubsection}{\numberline {4.13.3}暴力求法}{42}{subsubsection.4.13.3}%
\contentsline {subsubsection}{\numberline {4.13.4}线性(N要小于p)}{42}{subsubsection.4.13.4}%
\contentsline {subsubsection}{\numberline {4.13.5}卢卡斯}{43}{subsubsection.4.13.5}%
\contentsline {subsubsection}{\numberline {4.13.6}扩展卢卡斯}{44}{subsubsection.4.13.6}%
\contentsline {subsubsection}{\numberline {4.13.7}错排}{45}{subsubsection.4.13.7}%
\contentsline {subsection}{\numberline {4.14}裴蜀定理}{46}{subsection.4.14}%
\contentsline {subsubsection}{\numberline {4.14.1}总结}{46}{subsubsection.4.14.1}%
\contentsline {subsection}{\numberline {4.15}唯一分解定理+约数定理}{46}{subsection.4.15}%
\contentsline {subsubsection}{\numberline {4.15.1}总结}{46}{subsubsection.4.15.1}%
\contentsline {subsubsection}{\numberline {4.15.2}约数之和}{47}{subsubsection.4.15.2}%
\contentsline {subsubsection}{\numberline {4.15.3}求二元倒数方程}{47}{subsubsection.4.15.3}%
\contentsline {subsubsection}{\numberline {4.15.4}具有N个不同因子的最小正整数}{48}{subsubsection.4.15.4}%
\contentsline {subsection}{\numberline {4.16}线性基}{49}{subsection.4.16}%
\contentsline {subsubsection}{\numberline {4.16.1}总结}{49}{subsubsection.4.16.1}%
\contentsline {subsubsection}{\numberline {4.16.2}验证存在性+最小值+最大值+第K小}{50}{subsubsection.4.16.2}%
\contentsline {subsubsection}{\numberline {4.16.3}最大异或和路径}{52}{subsubsection.4.16.3}%
\contentsline {subsubsection}{\numberline {4.16.4}区间询问异或和或上K的最大值}{55}{subsubsection.4.16.4}%
\contentsline {subsection}{\numberline {4.17}整除分块}{58}{subsection.4.17}%
\contentsline {subsubsection}{\numberline {4.17.1}总结}{58}{subsubsection.4.17.1}%
\contentsline {subsubsection}{\numberline {4.17.2}余数求和}{60}{subsubsection.4.17.2}%
\contentsline {subsubsection}{\numberline {4.17.3}有限小数对数}{60}{subsubsection.4.17.3}%
\contentsline {subsection}{\numberline {4.18}中国剩余定理}{61}{subsection.4.18}%
\contentsline {subsubsection}{\numberline {4.18.1}总结}{61}{subsubsection.4.18.1}%
\contentsline {subsubsection}{\numberline {4.18.2}中国剩余定理}{61}{subsubsection.4.18.2}%
\contentsline {subsubsection}{\numberline {4.18.3}扩展中国剩余定理}{62}{subsubsection.4.18.3}%
\contentsline {section}{\numberline {5}图论}{63}{section.5}%
\contentsline {subsection}{\numberline {5.1}小经验}{63}{subsection.5.1}%
\contentsline {subsection}{\numberline {5.2}K短路}{63}{subsection.5.2}%
\contentsline {subsubsection}{\numberline {5.2.1}Astar}{63}{subsubsection.5.2.1}%
\contentsline {subsection}{\numberline {5.3}K级祖先}{65}{subsection.5.3}%
\contentsline {subsubsection}{\numberline {5.3.1}总结}{65}{subsubsection.5.3.1}%
\contentsline {subsubsection}{\numberline {5.3.2}倍增法}{65}{subsubsection.5.3.2}%
\contentsline {subsubsection}{\numberline {5.3.3}重链剖分}{66}{subsubsection.5.3.3}%
\contentsline {subsubsection}{\numberline {5.3.4}长链剖分}{66}{subsubsection.5.3.4}%
\contentsline {subsection}{\numberline {5.4}LCA}{67}{subsection.5.4}%
\contentsline {subsubsection}{\numberline {5.4.1}tarjan离线}{67}{subsubsection.5.4.1}%
\contentsline {subsubsection}{\numberline {5.4.2}倍增法}{68}{subsubsection.5.4.2}%
\contentsline {subsubsection}{\numberline {5.4.3}树剖法}{69}{subsubsection.5.4.3}%
\contentsline {subsection}{\numberline {5.5}次小生成树}{71}{subsection.5.5}%
\contentsline {subsubsection}{\numberline {5.5.1}kruskal+lca}{71}{subsubsection.5.5.1}%
\contentsline {subsection}{\numberline {5.6}带花树}{74}{subsection.5.6}%
\contentsline {subsubsection}{\numberline {5.6.1}一般图最大匹配}{74}{subsubsection.5.6.1}%
\contentsline {subsubsection}{\numberline {5.6.2}一般图最大权匹配}{76}{subsubsection.5.6.2}%
\contentsline {subsection}{\numberline {5.7}矩阵树定理}{81}{subsection.5.7}%
\contentsline {subsubsection}{\numberline {5.7.1}总结}{81}{subsubsection.5.7.1}%
\contentsline {subsubsection}{\numberline {5.7.2}无向图生成树个数}{82}{subsubsection.5.7.2}%
\contentsline {subsubsection}{\numberline {5.7.3}有(无)向图生成树的权值和}{83}{subsubsection.5.7.3}%
\contentsline {subsection}{\numberline {5.8}判断完全图}{84}{subsection.5.8}%
\contentsline {subsubsection}{\numberline {5.8.1}判断完全图}{84}{subsubsection.5.8.1}%
\contentsline {subsection}{\numberline {5.9}树的直径}{85}{subsection.5.9}%
\contentsline {subsubsection}{\numberline {5.9.1}两次dfs}{85}{subsubsection.5.9.1}%
\contentsline {subsection}{\numberline {5.10}最短路}{85}{subsection.5.10}%
\contentsline {subsubsection}{\numberline {5.10.1}Dijkstra堆优化}{85}{subsubsection.5.10.1}%
\contentsline {subsubsection}{\numberline {5.10.2}Dijkstra配对堆}{86}{subsubsection.5.10.2}%
\contentsline {subsection}{\numberline {5.11}最小mex生成树}{88}{subsection.5.11}%
\contentsline {subsubsection}{\numberline {5.11.1}最小mex生成树}{88}{subsubsection.5.11.1}%
\contentsline {section}{\numberline {6}动态规划}{90}{section.6}%
\contentsline {subsection}{\numberline {6.1}总结}{90}{subsection.6.1}%
\contentsline {subsection}{\numberline {6.2}01背包}{91}{subsection.6.2}%
\contentsline {subsubsection}{\numberline {6.2.1}前k优解}{91}{subsubsection.6.2.1}%
\contentsline {subsubsection}{\numberline {6.2.2}求最优解方案个数}{92}{subsubsection.6.2.2}%
\contentsline {subsubsection}{\numberline {6.2.3}求恰好装满背包的最优解}{93}{subsubsection.6.2.3}%
\contentsline {subsubsection}{\numberline {6.2.4}求具体方案}{93}{subsubsection.6.2.4}%
\contentsline {subsubsection}{\numberline {6.2.5}超大背包}{94}{subsubsection.6.2.5}%
\contentsline {subsection}{\numberline {6.3}完全背包}{97}{subsection.6.3}%
\contentsline {subsubsection}{\numberline {6.3.1}求最优解方案数}{97}{subsubsection.6.3.1}%
\contentsline {subsection}{\numberline {6.4}多重背包}{98}{subsection.6.4}%
\contentsline {subsubsection}{\numberline {6.4.1}总结}{98}{subsubsection.6.4.1}%
\contentsline {subsection}{\numberline {6.5}分组背包}{100}{subsection.6.5}%
\contentsline {subsubsection}{\numberline {6.5.1}总结}{100}{subsubsection.6.5.1}%
\contentsline {subsection}{\numberline {6.6}树形依赖背包}{100}{subsection.6.6}%
\contentsline {subsubsection}{\numberline {6.6.1}总结}{100}{subsubsection.6.6.1}%
\contentsline {subsection}{\numberline {6.7}状压dp}{102}{subsection.6.7}%
\contentsline {subsubsection}{\numberline {6.7.1}总结}{102}{subsubsection.6.7.1}%
\contentsline {subsection}{\numberline {6.8}区间dp}{102}{subsection.6.8}%
\contentsline {subsection}{\numberline {6.9}数位dp}{102}{subsection.6.9}%
\contentsline {subsection}{\numberline {6.10}经典问题}{102}{subsection.6.10}%
\contentsline {subsubsection}{\numberline {6.10.1}最长上升子序列}{102}{subsubsection.6.10.1}%
\contentsline {subsubsection}{\numberline {6.10.2}最长公共子序列}{103}{subsubsection.6.10.2}%
\contentsline {subsubsection}{\numberline {6.10.3}最短不公共子串、子序列}{106}{subsubsection.6.10.3}%
\contentsline {subsubsection}{\numberline {6.10.4}最长公共上升子序列}{108}{subsubsection.6.10.4}%
\contentsline {subsubsection}{\numberline {6.10.5}整数划分}{110}{subsubsection.6.10.5}%
\contentsline {section}{\numberline {7}数据结构}{115}{section.7}%
\contentsline {subsection}{\numberline {7.1}CDQ分治}{115}{subsection.7.1}%
\contentsline {subsubsection}{\numberline {7.1.1}cdq}{115}{subsubsection.7.1.1}%
\contentsline {subsubsection}{\numberline {7.1.2}数值删除、逆序对个数（排列）}{117}{subsubsection.7.1.2}%
\contentsline {subsection}{\numberline {7.2}splay}{118}{subsection.7.2}%
\contentsline {subsubsection}{\numberline {7.2.1}插入x、删除x、查x的排名、查排名为x的数、x的前驱、x的后继}{118}{subsubsection.7.2.1}%
\contentsline {subsubsection}{\numberline {7.2.2}区间插入、区间删除、区间覆盖、区间翻转、区间求和、最大子段和}{122}{subsubsection.7.2.2}%
\contentsline {subsection}{\numberline {7.3}dsu on tree}{126}{subsection.7.3}%
\contentsline {subsubsection}{\numberline {7.3.1}总结}{126}{subsubsection.7.3.1}%
\contentsline {subsubsection}{\numberline {7.3.2}CF600E}{126}{subsubsection.7.3.2}%
\contentsline {subsubsection}{\numberline {7.3.3}CF570D}{128}{subsubsection.7.3.3}%
\contentsline {subsubsection}{\numberline {7.3.4}CF208E}{130}{subsubsection.7.3.4}%
\contentsline {subsubsection}{\numberline {7.3.5}CF246E}{133}{subsubsection.7.3.5}%
\contentsline {subsubsection}{\numberline {7.3.6}CF375D}{134}{subsubsection.7.3.6}%
\contentsline {subsubsection}{\numberline {7.3.7}CF1009F}{138}{subsubsection.7.3.7}%
\contentsline {subsubsection}{\numberline {7.3.8}wannafly Day2 E}{139}{subsubsection.7.3.8}%
\contentsline {subsubsection}{\numberline {7.3.9}ccpc2020长春站F题}{141}{subsubsection.7.3.9}%
\contentsline {subsubsection}{\numberline {7.3.10}洛谷P4149}{143}{subsubsection.7.3.10}%
\contentsline {subsubsection}{\numberline {7.3.11}牛客练习赛60E}{146}{subsubsection.7.3.11}%
\contentsline {subsubsection}{\numberline {7.3.12}牛客练习赛81D}{148}{subsubsection.7.3.12}%
\contentsline {subsubsection}{\numberline {7.3.13}CF741D}{151}{subsubsection.7.3.13}%
\contentsline {subsection}{\numberline {7.4}单调栈}{154}{subsection.7.4}%
\contentsline {subsection}{\numberline {7.5}单调队列}{155}{subsection.7.5}%
\contentsline {subsubsection}{\numberline {7.5.1}理想正方形}{155}{subsubsection.7.5.1}%
\contentsline {subsection}{\numberline {7.6}第二分块}{156}{subsection.7.6}%
\contentsline {subsubsection}{\numberline {7.6.1}将区间内x改为y、区间第k大}{156}{subsubsection.7.6.1}%
\contentsline {subsubsection}{\numberline {7.6.2}区间大于x的数减去x、区间内x出现的次数}{159}{subsubsection.7.6.2}%
\contentsline {subsection}{\numberline {7.7}树状数组}{163}{subsection.7.7}%
\contentsline {subsubsection}{\numberline {7.7.1}二维树状数组}{163}{subsubsection.7.7.1}%
\contentsline {subsection}{\numberline {7.8}线段树}{165}{subsection.7.8}%
\contentsline {subsubsection}{\numberline {7.8.1}总结}{165}{subsubsection.7.8.1}%
\contentsline {subsubsection}{\numberline {7.8.2}01序列、区间覆盖为0、区间覆盖为1、区间取反、区间1的个数、区间最大连续1的个数}{165}{subsubsection.7.8.2}%
\contentsline {subsubsection}{\numberline {7.8.3}单点修改、区间重排是否在值域上连续}{169}{subsubsection.7.8.3}%
\contentsline {subsubsection}{\numberline {7.8.4}单点修改、区间最大连续子段和}{171}{subsubsection.7.8.4}%
\contentsline {subsubsection}{\numberline {7.8.5}动态区间中位数}{173}{subsubsection.7.8.5}%
\contentsline {subsubsection}{\numberline {7.8.6}区间+k、区间最大连续子段和}{175}{subsubsection.7.8.6}%
\contentsline {subsubsection}{\numberline {7.8.7}区间+k、区间最大值、区间最小值、区间和}{178}{subsubsection.7.8.7}%
\contentsline {subsubsection}{\numberline {7.8.8}区间gcd}{180}{subsubsection.7.8.8}%
\contentsline {subsubsection}{\numberline {7.8.9}区间hash}{182}{subsubsection.7.8.9}%
\contentsline {subsubsection}{\numberline {7.8.10}区间乘法}{184}{subsubsection.7.8.10}%
\contentsline {subsubsection}{\numberline {7.8.11}区间覆盖+查询}{187}{subsubsection.7.8.11}%
\contentsline {subsubsection}{\numberline {7.8.12}区间异或x、区间求和}{189}{subsubsection.7.8.12}%
\contentsline {subsubsection}{\numberline {7.8.13}区间与、区间或、区间最小值}{191}{subsubsection.7.8.13}%
\contentsline {subsubsection}{\numberline {7.8.14}树上区间+k、区间×k、区间覆盖、区间立方和}{193}{subsubsection.7.8.14}%
\contentsline {subsubsection}{\numberline {7.8.15}矩阵+k、矩阵最大值}{197}{subsubsection.7.8.15}%
\contentsline {subsection}{\numberline {7.9}吉司机线段树}{199}{subsection.7.9}%
\contentsline {subsubsection}{\numberline {7.9.1}区间+k、区间覆盖、区间最大值、区间历史最大值}{199}{subsubsection.7.9.1}%
\contentsline {subsection}{\numberline {7.10}主席树}{202}{subsection.7.10}%
\contentsline {subsubsection}{\numberline {7.10.1}撤销X个操作(可撤销先前撤销的操作)}{202}{subsubsection.7.10.1}%
\contentsline {subsubsection}{\numberline {7.10.2}区间出现次数大于某值的最小数}{202}{subsubsection.7.10.2}%
\contentsline {subsubsection}{\numberline {7.10.3}区间第K大}{203}{subsubsection.7.10.3}%
\contentsline {subsubsection}{\numberline {7.10.4}区间内不同数的个数}{205}{subsubsection.7.10.4}%
\contentsline {subsubsection}{\numberline {7.10.5}区间内只出现过一次的数}{206}{subsubsection.7.10.5}%
\contentsline {subsubsection}{\numberline {7.10.6}区间询问最小不能被表示的数}{208}{subsubsection.7.10.6}%
\contentsline {subsubsection}{\numberline {7.10.7}区间众数}{209}{subsubsection.7.10.7}%
\contentsline {subsubsection}{\numberline {7.10.8}子树中距离其不超过K的最小点权}{210}{subsubsection.7.10.8}%
\contentsline {subsection}{\numberline {7.11}树套树}{212}{subsection.7.11}%
\contentsline {subsubsection}{\numberline {7.11.1}单点修改、区间第k大}{212}{subsubsection.7.11.1}%
\contentsline {subsubsection}{\numberline {7.11.2}数值删除、逆序对数（排列）}{214}{subsubsection.7.11.2}%
\contentsline {subsection}{\numberline {7.12}块状链表}{215}{subsection.7.12}%
\contentsline {subsection}{\numberline {7.13}普通并查集}{217}{subsection.7.13}%
\contentsline {subsubsection}{\numberline {7.13.1}路径压缩}{217}{subsubsection.7.13.1}%
\contentsline {subsubsection}{\numberline {7.13.2}按秩合并}{217}{subsubsection.7.13.2}%
\contentsline {subsubsection}{\numberline {7.13.3}启发式合并+路径压缩}{218}{subsubsection.7.13.3}%
\contentsline {subsection}{\numberline {7.14}种类并查集}{218}{subsection.7.14}%
\contentsline {subsection}{\numberline {7.15}可撤销并查集}{218}{subsection.7.15}%
\contentsline {subsubsection}{\numberline {7.15.1}可撤销并查集}{218}{subsubsection.7.15.1}%
\contentsline {subsubsection}{\numberline {7.15.2}加边、删边、判二分图}{219}{subsubsection.7.15.2}%
\contentsline {subsubsection}{\numberline {7.15.3}加边、删边、判联通}{221}{subsubsection.7.15.3}%
\contentsline {subsection}{\numberline {7.16}可持久化并查集}{224}{subsection.7.16}%
\contentsline {subsubsection}{\numberline {7.16.1}总结}{224}{subsubsection.7.16.1}%
\contentsline {subsubsection}{\numberline {7.16.2}可持久化并查集}{224}{subsubsection.7.16.2}%
\contentsline {subsection}{\numberline {7.17}带权并查集}{226}{subsection.7.17}%
\contentsline {subsubsection}{\numberline {7.17.1}带权并查集}{226}{subsubsection.7.17.1}%
\contentsline {subsection}{\numberline {7.18}双指针}{227}{subsection.7.18}%
\contentsline {section}{\numberline {8}字符串}{228}{section.8}%
\contentsline {subsection}{\numberline {8.1}字典树}{228}{subsection.8.1}%
\contentsline {subsubsection}{\numberline {8.1.1}指针版（释放内存）}{228}{subsubsection.8.1.1}%
\contentsline {subsubsection}{\numberline {8.1.2}字典树}{229}{subsubsection.8.1.2}%
\contentsline {subsection}{\numberline {8.2}字符串hash}{230}{subsection.8.2}%
\contentsline {subsubsection}{\numberline {8.2.1}总结}{230}{subsubsection.8.2.1}%
\contentsline {subsubsection}{\numberline {8.2.2}字符串hash}{230}{subsubsection.8.2.2}%
\contentsline {subsubsection}{\numberline {8.2.3}二维hash、矩阵hash}{231}{subsubsection.8.2.3}%
\contentsline {section}{\numberline {9}头脑风暴}{232}{section.9}%
\contentsline {subsection}{\numberline {9.1}dp合集}{232}{subsection.9.1}%
\contentsline {subsubsection}{\numberline {9.1.1}不等式约束（牛客）}{232}{subsubsection.9.1.1}%
\contentsline {subsubsection}{\numberline {9.1.2}三元组的约束（AT）}{234}{subsubsection.9.1.2}%
\contentsline {subsection}{\numberline {9.2}等差子序列}{235}{subsection.9.2}%
\contentsline {subsubsection}{\numberline {9.2.1}总结}{235}{subsubsection.9.2.1}%
\contentsline {subsection}{\numberline {9.3}回文问题}{240}{subsection.9.3}%
\contentsline {subsubsection}{\numberline {9.3.1}寻找回文路径（AT）}{240}{subsubsection.9.3.1}%
\contentsline {subsection}{\numberline {9.4}排列问题}{242}{subsection.9.4}%
\contentsline {subsubsection}{\numberline {9.4.1}字典序最小的（排列\&子序列）}{242}{subsubsection.9.4.1}%
\contentsline {subsection}{\numberline {9.5}区间多次询问问题}{242}{subsection.9.5}%
\contentsline {subsubsection}{\numberline {9.5.1}从区间中选出两个数使得异或值最大}{242}{subsubsection.9.5.1}%
\contentsline {subsection}{\numberline {9.6}数论只会gcd？}{244}{subsection.9.6}%
\contentsline {subsubsection}{\numberline {9.6.1}求给定范围内gcd为素数的数对有多少？}{244}{subsubsection.9.6.1}%
\contentsline {subsubsection}{\numberline {9.6.2}求给定范围内gcd为素数的数对有多少？}{245}{subsubsection.9.6.2}%
\contentsline {subsubsection}{\numberline {9.6.3}单点乘法取模+整体gcd}{246}{subsubsection.9.6.3}%
\contentsline {subsubsection}{\numberline {9.6.4}给定c,d,x求满足c×lcm(a,b) - d×gcd(a,b) = x 的 (a,b) 的对数}{246}{subsubsection.9.6.4}%
\contentsline {subsection}{\numberline {9.7}以子串为单位的倍增思想}{247}{subsection.9.7}%
\contentsline {subsubsection}{\numberline {9.7.1}以子串为单位的倍增思想}{247}{subsubsection.9.7.1}%
\contentsline {subsection}{\numberline {9.8}最大字段和问题}{249}{subsection.9.8}%
\contentsline {subsubsection}{\numberline {9.8.1}从序列中选出K个子串使得子串和最大}{249}{subsubsection.9.8.1}%
\contentsline {section}{\numberline {10}杂项}{251}{section.10}%
\contentsline {subsection}{\numberline {10.1}对拍}{251}{subsection.10.1}%
\contentsline {subsubsection}{\numberline {10.1.1}ac.cpp}{251}{subsubsection.10.1.1}%
\contentsline {subsubsection}{\numberline {10.1.2}wa.cpp}{251}{subsubsection.10.1.2}%
\contentsline {subsubsection}{\numberline {10.1.3}data.cpp}{252}{subsubsection.10.1.3}%
\contentsline {subsubsection}{\numberline {10.1.4}duipai.cpp}{252}{subsubsection.10.1.4}%
\contentsline {subsection}{\numberline {10.2}素数表}{253}{subsection.10.2}%
\contentsline {subsection}{\numberline {10.3}小tricks}{253}{subsection.10.3}%
\contentsline {subsection}{\numberline {10.4}玄学优化}{253}{subsection.10.4}%
\contentsline {subsection}{\numberline {10.5}头文件}{254}{subsection.10.5}%
\contentsline {section}{\numberline {11}赛前看一看}{263}{section.11}%
\contentsline {subsection}{\numberline {11.1}错误征集}{263}{subsection.11.1}%
\contentsline {subsection}{\numberline {11.2}运行结果和自己预期的不一样？}{263}{subsection.11.2}%