HL集训合集 01

[$\large\text{河暗集训 Part.1}$](https://www.luogu.com.cn/training/511783) [$\large\text{河暗集训 Part.2}$](https://www.luogu.com.cn/training/554101) ## 五月集训 开头 6 题，每题都相当于是题单。懒得总结。 ## 七月集训 - 7.3~7.10 不做记录。 - 7.11 上午：Przyciski ~ 学习轨迹 晚上：kangaroo ~ 交换 缺失：[卡密](https://oj.hailiangedu.com/d/hlxly2022/p/1299?tid=668f4e291706a3d130f8e7f6)、[划分](https://oj.hailiangedu.com/d/hlxly2022/p/1300?tid=668f4e291706a3d130f8e7f6) 下午到的机房然后开改。 然后呢，~~不小心看到了第一题题解~~。 然后先把第二题打了 然后第一题懂了就打了 然后第三题题解看了两行发现是绝妙的树形dp和判环，遂写。~~虽然我连判环都能写炸~~ 第五题看题界有个区间赋最小值，摆。 晚上三题先摆。 第四题写下对题解代码的理解： 1. 筛，然后维护个奇怪的东西 2. 把所有环找出来，记录环大小。 3. 插入 [multiset](https://blog.csdn.net/sodacoco/article/details/84798621)，同时维护 lcm 和最大的次数 4. 去重 5. 枚举 i 和 j，计算（还没仔细看） - 7.12 上午：Moutains and Valleys 缺失：[数学高手(Hydro 数列递推)](https://hydro.ac/d/loj/p/P538)、[墅居结垢(Hydro 七曜圣贤)](https://hydro.ac/d/loj/p/P541)、[染色](https://www.cnblogs.com/Konjac-Binaries/p/15371157.html#t2-%E6%9F%93%E8%89%B2)、[马里奥(Hydro 旅游路线)](https://hydro.ac/d/loj/p/P539) 非常好初始化，使我的马里奥旋转。 非常好随机数据，使我的得分旋转。 然后呢赛后 10min 过了它： 先倍增或者~~乱搞~~求出每个点加完油后到每个点可走的最大路程，单次就类似于floyd。 然后进行一个记忆化搜索预处理一下。 然后 $O(1)$ 查询就做完啦 第一题(数学高手)直接处理log个数后看同号即可。 第二题赛后发现自己sb了，mex 就是没出现过的和被删除的数的最小值，然后一个桶一个单调队列刷了。 第三题提高的，set维护一下每次把最高的输出更新其他的即可。 第五题以后再探索吧。 - 7.13 早上：Partition ~ 中暑 缺失：[串串串(「美团 CodeM 决赛」elimination)](https://loj.ac/p/6211)、[光明(「美团 CodeM 决赛」radar)](https://loj.ac/p/6213) T1人话：找到最大的数 $p$ 使得 $\frac{m}{p}\geq n$ 且为整数，然后 $O(\sqrt{m})$ 秒了。 T2，每个菜只有三个位置可以贡献答案，建个桶就好了。 T3，设 $f_{i,j}$ 为前 $i$ 个字母中有 A/AB/ABC 的答案，设当前的字符串方案数为 $w$。 A: $f_{i,1}=f_{i-1,1}+w$。 B: $f_{i,2}=f_{i-1,2}+f_{i-1,1}$。 C: $f_{i,3}=f_{i-1,3}+f_{i-1,2}$。 ?: $f_{i,3}=3f_{i-1,3}+f_{i-1,2}$，$f_{i,2}=3f_{i-1,2}+f_{i-1,1}$，$f_{i,1}=3f_{i-1,1}+w$。 T4 直接枚举符号暴力 dp。 T5 非常的神秘。推柿子发现数列 `a` 在 $2^i$ 次操作后的结果是 `(a>>(1<<i))^a`（然后要抹掉一些位） 然后倍增+bitset即可卡过。 T6 斜率，但是不会；T7 摆烂。 - 7.15 早上：Milk Visits G ~ 人员调度 深绿色是看了题解或听完讲评然后自己过的，*天天爱跑步不确定*。 #### $01.\ \color{52C41A}\text{[USACO19DEC] Milk Visits G}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166023217) 发现可以按照颜色大小排序**离线**。 上**树剖**，线段树维护的是最小值。 如果 $col=i$ 的询问都处理完了，把满足 $a_j=col$ 的点 $j$ 的权值设为无穷即可。 #### $02.\ \color{32A40A}\text{Trees of Tranquillity}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166039826) 嗯是的你可以发现 $fa_i<i$，嗯是的这玩意有用。 发现 tree1 上的点都要在一条链上。 发现 tree2 上一个点选了它的子树就不能选。 然后发现如果 tree1 上 $u$ 是 $v$ 的祖先，tree2 上他俩覆盖范围**要么是包含要么是不交**。 贪心，普通的**线段树**维护。 #### $03.\ \color{32A40A}\text{DFS Trees}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166060481) 非常妙啊.png 首先你仔细看一遍题面发现边权互不相同，所以 **MST 唯一**。 然后运用一个奇妙的性质：**一个 DFS 树只有树边和返祖边**。 然后转化成：对于每个点，所有非 MST 边两端是否都是祖孙关系。 随便选一个当根节点，遍历所有非 MST 边： 如果两端当前不是祖孙关系，**两端的子树**满足条件。 如果两端当前是祖孙关系，（其实还是两端的子树），处理更麻烦，**除了两端点之间的点外**的都满足条件。这里需要倍增或 LCA。 然后**树上差分**，最后判断每个点满足条件数量即可。 #### $04.\ \color{32A40A}\text{[SDOI2011] 消防}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166176939) 弱化版是 $\small\color{32A40A}\text{[NOIP2007 提高组] 树网的核}$。 首先我们把直径找出来。 只用找一条是因为如果有两条答案唯一（直径÷2） 考虑选完后参与答案更新的部分： 1.直径上每个点向外延伸的距离 2.选中两个端点到直径两个端点的距离 然后双指针即可。 #### $05.\ \color{52C41A}\text{[NOIP2016 提高组] 天天爱跑步}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/130277193) 之前做过，懒得整。 #### $06.\ \color{52C41A}\text{[省选联考 2021 A/B 卷] 宝石}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166225173) 芜湖！不用主席树和树剖过了！ 首先考虑**倍增**，$f_{i,j}$ 表示 $j$ 位置上往前匹配 $2^i$ 个位置到的最大深度的节点（这里反着也要做一遍，后面要用）。 这个基础状态是可以一遍 dfs $O(n)$ 的。 然后呢把询问拆成两块，一个是 $x\rightarrow lca$，一个是 $lca\rightarrow y$。 前半段先找到第一个匹配位置，然后直接倍增即可。 后半段先二分一下答案再从下往上跳！ 但是首先怎么找？ **把所有询问离线**，同时二分答案，每次找到那个点只需要 $O(n)$，然后每个询问再单独验证一下可不可行 $O(\log n)$，加上二分，复杂度是 $O(n\log^2 n)$！ 至此我们用**二分和倍增**过了这道题。 - 7.16 早上：善意的投票/冠军调查 ~ 无限之环 缺失：[Codechef RIN 「Codechef14DEC」Course Selection](https://vjudge.net/problem/CodeChef-RIN) 部分题目有没有看题解也是记不清了。 #### $00.\ \color{32A40A}\text{模板}$ [$\small\text{网络最大流}$](https://www.luogu.com.cn/record/140526628) $\small/$ [$\small\text{最小费用最大流}$](https://www.luogu.com.cn/record/145781340) #### $01.\ \color{52C41A}\text{[SHOI2007] 善意的投票 / [JLOI2010] 冠军调查}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/120483000) 【网络流 最小割】 最简单的一个最小割建边。 首先处理第二种冲突： 对于一个小朋友 $i$ 建立点 $i$，如果本来反对就 $i\rightarrow t$、本来支持就 $s\rightarrow i$，边权均为 $1$；很容易理解。 那么第一种冲突怎么做呢？ 很简单，每一对小朋友连双向边，边权为 $1$。 是的我们做完了。 #### $02.\ \color{52C41A}\text{最长不下降子序列问题}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166276727) 【网络流】 这里设 $S$ 为最长长度，$F_i$ 为前 $i$ 个答案。 首先最长长度我们可以 $O(n^2)$ dp。 然后开始考虑第二问。 首先如果 $F_i=1$ 就 $s\rightarrow i$，如果 $F_i=S$ 就 $i\rightarrow t$。 接下来考虑两点之间在什么情况下连边？ $A_i<A_j$ 且 $F_i+1=F_j$，也就是 $i$ 能转移到 $j$。 ~~我才不会说我在这里卡了好久。~~ 连边数是 $O(n^2)$ 的，可以跑过。 第三问就改一改边权，注意不要加上 $1\rightarrow n$ 即可。 #### $03.\color{52C41A}\text{「Codechef14DEC」Course Selection}$ $/$ [$\text{Submission(HL)}$](https://oj.hailiangedu.com/d/hlxly2022/record/66962a7a1706a3d1301109dd) 【网络流 最小割】 好妙的连边。 每个课程拆点，然后转化成总成绩减去最小的扣分。 $[i,j]\rightarrow[i,j+1]$ 表示第 $i$ 个课程在第 $j$ 学年上课，边权即为满分减去绩点。 比较特殊的，$s\rightarrow [i,1]$、$[i,m+1]\rightarrow t$。 一次如果割掉了某一条边，就相当于这节课选择在这个学年上。 接下来看先后关系，对于 $1\leq j\leq m$，$[a,j]\rightarrow [b,j+1]\ (\inf)$，这样 $b$ 割的边一定在 $a$ 后。 然后跑网络流即可。 #### $04.\ \color{52C41A}\text{[TJOI2015] 线性代数}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166281599) 【网络流 最小割】 首先让我们愉快地推一下柿子。 $(A\times B-C)_{1,i}=-C_{1,i}+\sum_{j=1}^{n}A_{1,j}\cdot B_{j,i}$。 $D=\sum_{i=1}^{n} A_{1,i}\cdot\left(-C_{1,i}+\sum_{j=1}^{n}A_{1,j}\cdot B_{j,i}\right)\\ \color{white}D\color{black}=-\left(\sum_{j=1}^{n}A_{1,j}\cdot C_{1,i}\right)+\left(\sum_{i=1}^{n}\sum_{j=1}^{n}A_{1,i}A_{1,j}\cdot B_{j,i}\right)$ 由于 $A$ 是 01 矩阵，考虑最小割，总价值（$\sum B$）减去最小代价。 然后前面 $s\rightarrow i$，边权为 $C_{1,i}$，表示选了就要扣掉。 然后对于每一对 $(i,j)$，建立新点 $v$，然后 $v\rightarrow t\ (B_{j,i})$，$i,j\rightarrow v(\inf)$，可以参考文理分科。 然后一发就过了这道题。 #### $05.\ \color{32A40A}\text{[SCOI2007] 修车}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/120516743) 【费用流】 大眼观察~~题解~~后发现，如果第 $i$ 个师傅修第 $j$ 个顾客的车在**倒数**第 $k$ 个，那么产生 $k\times c_{i,j}$ 的代价。 于是我们可以 $s\rightarrow i\ (1,0) \{1\leq i\leq m\}$，然后 $i\rightarrow [j,k]\ (1,k\times c_{i,j})$，那些点连向汇点即可。 最后结果除以 $m$ 就做完了，你说得对但是这个想法很神仙。 #### $06.\ \color{32A40A}\text{[WC2007] 剪刀石头布}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/147366008) 【费用流】 唯 一 真 神 第一步是转化成非石头剪刀布情况最少。 发现非石头剪刀布情况只需要两个入度。 所以如果一个节点最后入度为 $i$，它做出的贡献是 $C_i^2$。 考虑拆边，去掉原本就有的后剩下的费用依次是 $...,i-1,i$。 然后一条边定向可以 $s\rightarrow u\ (1,0)$，$u\rightarrow a/b\ (1,0)$。 最后记得构造方案。 #### $07.\ \color{52C41A}\text{[AHOI2014/JSOI2014] 支线剧情}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166342300) 【费用流】 这里是自己想的一个简单易懂的做法。 首先 $s\rightarrow 1 (5000 0)$（至多重开 $5000$ 次）。 然后对于每条边 $(u,v,w)$，建两条边： 一条是 $u\rightarrow v (1,-p+w)$，其中 $p$ 是个很大的数，表示不走这条边更劣。 一条是 $u\rightarrow v (\inf,w)$，重复走就正常算。 然后跑费用流的时候程序就会把所有边都走一遍，最后直接输出 $ans+p\sum K$ 即可。 #### $08.\ \color{32A40A}\text{[SCOI2012] 奇怪的游戏}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166318069) 【网络流】 笑点解析：`int Z(int i,int j){return i*n+j-n;}`。 首先黑白染色，然后讨论 $n\times m$ 的奇偶性。 如果是奇可以算出答案，检验一下。 如果是偶就二分答案，每次跑一遍网络流（源点到黑点，白点到汇点）。 然后做完了，但是我调了 1 小时才发现这个笑点。 #### $09.\ \color{32A40A}\text{文理分科}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/140527515) 【网络流 最小割】 非常好**最小割**练习题。 首先转化为总满意值减去最小。 首先单纯选文理，$s\rightarrow i$、$i\rightarrow t$ 分别连文理单选价值。 然后相邻选了同一种怎么办？以文科（$s$）为例。 建立新的点 $u$，$s\rightarrow u$、$u\rightarrow \text{同时选的点}$，权值分别为全选文的价值和 $\inf$。 为什么呢？因为无穷的边一定不会在最小割里，所以只要有一个选里，$s\rightarrow$ 就必须割掉，否则（都选文）就可以保留。 于是我们可以愉快地过掉这道题。 #### $10.\ \color{32A40A}\text{无限之环}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166436730) 古希腊掌管费用流分类讨论的神。 记得写这个。 - 7.17 上午：Kids Designing Kids ~ 星际迷航 缺失：[圣光术（当咸鱼也要按照基本法）](https://vjudge.net.cn/problem/UESTC-1544)、[旅行计划（LOJ 小奇的旅行计划](https://loj.ac/p/6561)[、Hydro私域同题）](https://hydro.ac/d/cduestc/p/633)。 小奇的旅行计划暴力草过去的。 关联直接标 dfs 序，进入的时候加线段树出去的时候减掉就变成扫描线模板。 星际迷航没看题解自己写的，[建议看这个](https://www.luogu.com.cn/article/3vtwr10g)。 - 7.18 早上：跑步 ~ Security Guard 剩下 T3 和 T10。 #### $01.\ \color{32A40A}\text{跑步}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166775579) 我不会五边形数，所以我选择按照第一篇题解进行人类智慧分块 dp。 令 $m=20+\sqrt{n}$，开大点不然会喜提 40pts。 使用 $1\sim m$ 的数时，设 $f_{i,j}$ 表示最大数不超过 $i$，和为 $j$ 的方案数。 易得 $f_{i,j}=f_{i-1,j}+f_{i,j-i}$，然后滚动一下可以做到时 $O(n\sqrt n)$，空 $O(n)$。 那接下来只能用 $\geq m$ 的数，设 $g_{i,j}$ 表示用了 $i$ 个大于等于 $m$ 的数，和为 $j$ 的方案数，这里的转移方程也比较智慧： $g_{i,j}=g_{i-1,j-m}+g_{i,j-i}$，前者是加入一个 $m$，后者是把目前加入的所有数 $+1$。 因为 $i\leq \dfrac{n}{m}$，所以复杂度和 $f$ 一样。 注意两个方程的初始值 $f_{0,0}=g_{0,0}=1$，就可以 dp 了。 然后最后结果就是枚举一下两边乘起来。 #### $02.\ \color{32A40A}\text{You Are Given a Tree}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166790475) 第二道人类智慧哦哦哦 首先看单次怎么算： 设 $g_i$ 表示从点 $i$ 往下可以连多少个点（如果点 $i$ 已经连好则为 $-\inf$）。 然后每次求出儿子中 $g_i$ 的最大和次大，然后尝试和这个点连起来即可。 这是 $O(n)$ 的！ 然后我们考虑人类智慧，令 $m=\sqrt{n\log n}$。 对于 $i\in[1,m]$，我们直接爆算。 然后呢对于 $i\in(m,n]$，我们发现答案种类数一定不多且不升，我们考虑二分。 这样这个复杂度是对的，但是交上去 T 飞了怎么办呢？ 我们借鉴题解！把这个搜索改成循环的样子就可以过了。 #### $04.\ \color{52C41A}\text{[USACO19DEC] Meetings S}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166781520) 可以算是自己想的……？ 很神秘一道题，可以先把 [$\text{[ABC360D] Ghost Ants}$](https://www.luogu.com.cn/problem/AT_abc360_d) 过了。 下文默认排序，这个瓶颈是 $O(n\log n)$。 首先注意到两个性质： 一是相撞在某种意义上可以转化为穿过。 二是这些奶牛相对顺序不变。 所以我们根据一可以得到每头牛到达牛棚的顺序以及到达那个牛棚，又根据二知道到达的是哪个牛。 于是我们 $O(n)$ 把 $T$ 求了出来。 接下来只要算相撞次数，转化为满足 $i<j$、$d_i=1,d_j=-1$，$x_j-x_i\leq 2T$。 双指针秒了。 #### $05.\ \color{32A40A}\text{[NOIP2020] 移球游戏}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166958481) 哦哦哦哦哦好强的构造。 首先考虑只把一个颜色排成一列，下文 $1$ 是这个颜色，$0$ 是其他颜色。 **第一步**，构造一列 $0$。 假设第 $1$ 列有 $x$ 个 $1$，第 $n+1$ 列为空。 然后执行 $n$ 次 $n\rightarrow n+1$，然后把第一列所有的 $1$ 移到第 $n$ 列，所有的 $0$ 移到第 $n+1$ 列。 然后把第 $n+1$ 列的 $m-x$ 个 $0$ 移回第一列。 然后把第二列中的 $0$ 全部塞到第一列，剩下的塞到第 $n+1$ 列（可以证明足够填满）。 然后第二列为空，第一列全 $0$。 **第二步**，把每列的 $1$ 放到最上面。 这里还是默认第 $n$ 列全 $0$，第 $n+1$ 列为空。 先看第一列的放上去的方式，其他同理： 数这一列 $1$ 的个数 $x$，执行 $x$ 次 $n\rightarrow n+1$。 然后还是把这一列的所有 $1$ 放到第 $n$ 列，所有 $0$ 放到第 $n+1$ 列。 此时你惊讶的发现，第 $n$ 列的 $1$ 都在上面，第 $n+1$ 列全 $0$，第一列为空，于是我们就做完了。 **第三步**，造成一列 $1$。 直接把上面所有一扔到空行，然后用一列把其他的填上就好了。 这样我们就归位了一种颜色，剩下的以此类推。 **第四步**，特殊处理三列情况。 是的还没完！发现剩下两种颜色三列时这种方法不行！ 令第三列为空，第一列 $1$ 个数为 $x$。 首先按照前面的方式，这些 $1$ 在第二列，剩下的 $0$ 在第三列。 然后调整顺序把这些放回第一列，使得第一列最上面和刚开始第二列最上面颜色一样。 把第三列的放回第二列，然后把第二列最上面一个放到第三列。 然后把第一列上面那些扔到第三列。 然后第二列剩下的看颜色丢到第一或第三列。 我们做完了！！！！ #### $06.\ \color{32A40A}\text{Love-Hate}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166922109) 随机化好好好随机化。 发现方案中至少有一半的人，我们随机一个人成功概率还是很高的。 然后发现状态数只剩下 $p$ 个了，用一个神秘的状压 dp 就可以过了。 #### $07.\ \color{32A40A}\text{James and the Chase}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166991545) 随机五十次选点判断，如果还没有好点大概率是不到 $20\%$。 然后考虑对于一个点怎么判断： 以它为根的 dfs 树中没有横叉边和前向边，易证，用倍增是 $O(n\log n)$ 的。 然后如果找到好点了，可以用这个树判断其他的状态。 对于一个点可以这么判断： 得到这个点和它子树中连向外面的边的数量 $w$。 如果 $w≠1$，那么这个点不是好点。 如果 $w=1$，这个点的状态和指向那个点的状态一样。 还是易证大佬。 具体实现就用 multiset 合并即可，做完了。 #### $08.\ \color{52C41A}\text{Kuroni and the Punishment}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166824542) 非常好自己想出的随机化。 首先我们发现答案不大于 $n$，因为可以全部改成偶数。 然后可以得出结论，需要修改 $2$ 次的数不会超过 $\dfrac{n}{2}$ 个！ 然后我们可以随便抽 $30$ 个数，这样每次抽到的数都需要至少修改两次的概率只有可怜的 $2^{-30}$！ 那么假设抽到的数是 $i$，那么对 $i-1,i,i+1$ 这三个数进行质因数分解，把每个质因子计算更新一遍答案即可。 由于 $2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19\cdot23\cdot29\cdot31$ 结果约为 $2\times 10^{11}$，所以一个数最多有 $11$ 个质因子，那么最多进行 $990$ 次计算，每次计算是 $O(n)$ 的，但是能过。 #### $09.\ \color{32A40A}\text{Tourism}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166800905) 看到题解后我：？？？？？？？？？？？？？？？ 按自己的理解复述一遍。 首先最优解中间九个点黑白染色后一定是黑白相间，这个概率可以算是 $2^{-9}$，错误率 $\frac{511}{512}$。 然后我们每次随机黑白染色如果染对了，用简单的 $O(n^2k)$ 一定能得到最优解。 然后我们染色 $5000$ 次后如果每次都错，概率高达约 $0.0057\%$。 然后我们就过了这题。 总结：啊？ #### $00.\ \color{32A40A}\text{[CSP-S 2022] 假期计划}$ $/$ [$\text{Submission}$](https://www.luogu.com.cn/record/166907537) 哦哦哦随机化。 先把满足条件的点对连边。 然后每次随机把每个点染成 $A/B/C/D$，然后规定必须走 $1\rightarrow A\rightarrow B\rightarrow C\rightarrow D\rightarrow 1$。 然后直接跑一遍。 一次成功概率大概是 $\frac{2}{4^4}$，跑 $500$ 次加一个卡时过了。