2025 省选代码源集训小记
naoliaok_lovely
·
2025-02-05 11:08:21
·
个人记录
Day 1
致敬传奇模拟赛，拼尽全力无法战胜 T1。
46+12+5=63\texttt{pts}
所以这里是集训小寄。
考试的时候开玩笑说要不然去 div2，然后老板说你们该打 div2 呀，怎么打的 div1……
接下来的 T1 到 T4 就是两套题的并。
T1
组合题，前后两步都是独立的：
求出每个 l 对应最小的 r 使得 [l,r] 是好区间，双指针即可。
将 (l,r) 视作坐标，求出最近的点，本质是一个 rmq。
本人不是很喜欢这类前后独立的题，感觉没什么意思。
T2
上来写了个假做法，然后优化半天发现没得救……
考场上的状态是 bool 的 f_{i,s} ，显然的优化是 int 的 f_s ，考场上却没想到，只能说唐的不止一点。O(nV^2) 的，可以稍加优化，但事实是暴力跑得飞快。
T3
只会贪心模拟，采九朵莲。
注意到，最后的答案可以写成 \max\limits_{i\in E}\{time_i\} ，其中 time_i 表示 i 这条边最后一次经过的最小时间是多少。s\to t ，再注意到如果两个点在到达 s 之前就“堵车”了，可以直接无视，只处理 s\to t 处的“堵车”现象，可以证明答案不变。s 的距离从大到小依次是 dis_1,dis_2\dots dis_k ，那么又可以注意到 time=\max\limits_i\{dis_i+i\} 。
对于树的数据用线段树合并实现上述操作即可，环的话直接断环成链是正确的。
真的服了，写半天重点在与 3 个“注意到 ”。
T4
完全不会捏。
注意到，一个矩阵是好的当且仅当删去所有全 0 行和全 0 列后，存在一个分界点 (i,j) ，使得左上方全为 1 ，右下方全为 0 ，左下和右上方分别都为好矩阵。
暴力是 O(n^6) 的，简单优化可以做到 2D1D。(n,m) 的矩阵的信息；转移上，对于每一行只去转移最靠左的转移点。
Day 2
专题讲解：决策单调性、凸性优化 DP。
没怎么记录例题，但是在文章广场看到了这个。
定义
单调矩阵：记 minpos_i 表示第 i 行最小值的位置，则 minpos_i 单调不减。
完全单调矩阵：每一个子矩阵（选出一些行列，不一定连续）都是单调矩阵。事实上，如果所有 2\times2 的子矩阵都是单调矩阵，则该矩阵完全单调。
大多数单调矩阵都是完全单调。
蒙日(Monge)矩阵：对于每一个 2\times2 的子矩阵，都有 A_{x_1,y_1}+A_{x_2,y_2}\le A_{x_1,y_2}+A_{x_2,y_1} ，即满足四边形不等式。
显然蒙日矩阵一定是完全单调矩阵，事实上大多数完全单调矩阵都是蒙日矩阵。A_{x_2,y_2}-A_{x_1,y_2}-A_{x_2,y_1}+A_{x_1,y_1}\le0 的形式非常像二维前缀和，设 A 的差分数组为 B ，这等价于在 B 中左上角为 (x_1+1,y_1+1) 、右下角为 (x_2,y_2) 的矩阵元素和不大于 0 。这就是可以令 x_1+1=x_2,y_1+1=y_2 的原因。
特别地，对于区间问题 A_{i,j}(i>j) 是未定义的。为了满足蒙日矩阵，我们一般令 A_{i,j}=(j-i)^2\cdot\infty 。
两类问题
离线：f_i=\min\limits_j\{g_j+w(j,i)\} 。
在线：f_i=\min\limits_{j<i}\{f_j+w(j+1,i)\} 。
如果 w 为蒙日矩阵，则上述 dp 均具有决策单调性。
三种方法
分治法（CDQ，整体二分）——单调矩阵
二分队列/栈——完全单调矩阵
SMAWK 算法——完全单调矩阵
前两种都是老朋友了，第三种实际上也不难。
SMAWK 学习笔记——Lynkcatn\times m 的矩阵，如果我们可以求出所有偶数行的转移点，则奇数行可以在 O(m) 时间内求出。直接这样做是 O(n+m\log n) ，但其实可以优化到 O(n+m) 。考虑 n 很小的时候，其实只会用到 n 列而非 m 列，于是每轮先进行一下 reduce 操作即可保证复杂度。
蒙日矩阵最短路
要求：恰好走 k 条边。
trick：f_i=\max\{g_j+\texttt{int}+\lfloor\texttt{double}\rfloor\} ，由于只有一个小数，可以强制把下取整丢出去：f_i=\lfloor\max\{g_j+\texttt{int}+\texttt{double}\}\rfloor 。这样可以保证内部是一个连续函数，方便优化。
凸性优化 DP
trick：
f_i=\max\begin{cases}
f_i+a\\
f_{i-1}+b-ki
\end{cases}
如果满足转移前 f_i 是凸函数，则上下两个选项都是凸函数。但凸函数的 \max 并非凸函数（复合才是，对应闵可夫斯基和），所以直接做会损失凸函数的条件。g_i=f_i+k\frac{i(i+1)}2 ，于是有：
g_i=\max\begin{cases}
g_i+a\\
g_{i-1}+b
\end{cases}
CF1534G A New Beginning
qoj8362 gamea\le b ），再打扣血。对于回血，优先打 a 小的；对于扣血，优先打 b 大的。
Slope trick
像上面经常用到的那样，直接维护 dp 数组差分的方法被我们称之为 slope trick。一般会上平衡树等大型 DS。（众所周知我不会平衡树，所以可以倒闭）
Day 3
自习日。
完蛋，发现好多实现都不太会，成了数据结构小丑。
“考得好就牛 B 上天了，考得差就是题目的问题。”
Day 4
唐完了。
刚上来没看出来 T1 怎么做，但是隔壁 zhuzc 已经开始敲了，鸭梨山大捏。
T3 看上去很好玩，所以去手摸了很久，不多，也就几十组小数据喵，然后红温了。本来想写个暴力帮我手摸的，发现暴力不会写，这下更唐了。
最后的时间回 T2 打了暴力，不然分数就过于幽默了。
100+36+0=136\texttt{pts}
T1
和 std 不太一样（大不相同）？
发现把原题的交换改为“任意赋值”好想得多。f_{i,l,r} 表示前 i 个位置，前缀和在 [l,r] 之间（奇偶正确的情况下）的方案数。转移式写出来发现 l,r 独立，所以改为对前缀和的 \min 和 \max 分别 dp 即可。
T2
其实就是在最小化 \sum a+\dfrac x{\sum b} 。
设 f_i 表示 \sum a=i 时最大的 \sum b ，考虑如何快速计算 f 。（考场上只做到了线性，但是此题显然需要至少做到 o(\log) 甚至 O(1) ）\frac ab 最小的。设他为 (A,B) ，则可以证明，其余的物品加起来也只会选择不超过 A 个！（对前缀和考虑抽屉原理可得）i>(\max a)^2 ，有 f_i=f_{i-A}+B 。
（其实想过这方面，但是没去太深入的刻画这个东西）
实现的时候不要每一次给 ans 赋值都求一遍 \gcd ，本人寄飞了。
T3
大战 3h 暴砍 0\texttt{pts} 。（无限接近正解，更红温了）
容易让直径 \le4 ，因为这等价于深度 \le2 。每次操作一条竖着的链，分析度数即可保证总步数。
考虑让某一个点（设为 1 ）的最终度数为 n-2 ，如果存在一个点的距离 1 的 dis\ge3 ，显然可以用一次操作让 deg\gets deg+1 。最后的部分要考虑 7 的个点的导出子图……（本人已经到了这一步，然后手搓 7 个点倒闭了）
T4
听说好像叫什么约瑟夫链？
从置换的角度考虑，把 p 当做间隔，第 i 段相当于往后面的 i-1 个位置连边。
掉线 ing...
线性基求交
这里指异或空间线性基。
记 \operatorname{base}(A) 表示线性空间 A 的基底，于是 \operatorname{base}(A\cap B)=\operatorname{base}(A^\perp\cup B^\perp)^\perp ，即线性空间的交可以变为正交空间的并。
Day 5
专题讲解：数据结构题目选讲。
QOJ9918
先考虑对于单点怎么做。
建一棵时间线段树，考虑 dp，转移是经典的 f_{i,0}\to f_{i+1,0/1},f_{i,1}\to f_{i+1,0} ，直接写成矩阵即可。找最长后缀可以用线段树二分。
树上的话，一个直观想法是套个树剖，但是好像不太好做。一个经典想法是交换维护内容的维度 ，把时间丢到内层。这部分发现似乎可以用线段树合并，于是外层也不要树剖了，直接差分即可。
CF1750H
先考虑给定一个串如何判断。
显然把 1 变为 0 是不优的，我们想什么时候可以把 0 变为 1 。结论是对于任意选取的若干 0 段，如果把未选取的部分都视为 1 的情况下都无法操作，显然该串不合法；事实上如果对于所有的选择方案都成立，则是一个好串。O(n^2) 判断单个串。O(\log n) 个，这是因为只有当前的 0 段长度比左边的 len 大才合法，这个东西在成倍增长。
当然上面只是判断单个串，事实上还需要维护一些别的东西。不太懂了……
其实这个题的和数据结构关系不大，混进了列表里。
CF1852F
转化为最大独立集。
以坐标为 x 轴，时间为 y 轴，图画出来就是每一个红点可以往上面的 V 字型匹配。转化为最大独立集，发现我们可以找到一条折线，取折线上方的红点与下方的蓝点，这就是一个独立集。对这根折线 DP。
转 45\degree 方便一点，有加一个一次函数的操作，所以维护差分即可。典中典平衡树维护这个东西，重回 slope trick。
CF1942H
因为可以重排，显然把增加放前面减少放后面，所以任意时刻非负的限制等于没有。
设对于每个点是增加 a_i ，减少 c_i ，则 a_i-c_i\ge b_i ，即 a_i\ge b_i+c_i 。考虑匹配，则 b_i 可以向儿子节点以及祖先节点匹配，c_i 可以向子树内节点以及祖先节点匹配。其实就是把 a 当成左部点，b+c 当成右部点，要求右部点完美匹配。
用 Hall 定理找到状态：设右部所选集合为 S ，f_i 表示 i 子树内的 \min\limits_S\{\sum\limits_{to(S)} a-\sum\limits_Sb-\sum\limits_Sc\} 。由于 b,c 的匹配方式不一样，还要记一下 a_i 必选还是 \sum\limits_{j\in subtree(i)}a_i 必选。
jiangly 尝试直接最大独立集，倒闭了喵\~
CF1824E
首先思考如何判断一个 (V',E') 是否合法。首先显然有 |E'|=|V'|-1 。对于一条选定的边，如果有一侧不存在任何一个点被选择，那么该方案显然不合法；否则可以说明必然合法。
证明：|E'|=|V'|-1 矛盾。
枚举 \min(A,C)=x ，考虑求 B+D 的最大值 f_x 。
一个点可以选当且仅当 a_i\ge x ，边可以选当且仅当 c_i\ge x 。先把所有非法的边两端合并起来，使得新树 T 中的所有边均合法，每个点表示若干原先的点（不一定合法）。且所有度为 1 的点至少表示一个合法点，否则可以删去。cnt=\min(|E|,|V-1|) ，那么贪心方案如下：
点：选择每个叶子中最大的权值，然后选择剩余权值中前 (cnt+1-\text{叶子数量}) 大的权值。
边：选择前 cnt 大的权值。
上 DS 维护信息即可，线段树/平衡树合并可以做到单 \log ，当然可以直接启发式。
CF1876G
将询问记为 (l,r,x) ，离线下来考虑从右往左扫 r 。注意到只有 a_r>x 时才会操作，序列整体加 1 等价于 x 减少 1 ，这样序列就固定了。
考虑暴力，每次取出所有 a_r>x 的 (l,x) 询问，然后让 x\gets x-\lceil\frac{a_r-x}2\rceil 。注意到，如果 x_1,x_2 两个数都被取了出来，那么他们的差值会变为一半，所以总操作次数是 O(n\log V) 的。
可以用带权并查集维护答案。
CF1515H
zhuzc：这是什么 Ynoi，直接线段树套 trie 树秒了！
思路类似之前那道挑战 FWT，从全局修改变为了区间修改而已。
jiangly：这类问题的常用处理手法是，能打标记就打标记，不能打就递归，最后用势能来分析复杂度。
upd：爽了，以为是原题，结果写了 4h 。和之前那道的区别还是挺大的。
CF1523H
不管删除，如果可以直接到就是 1 步，否则一定会到能够到达的点中 i+a_i 最大的那个。
倍增，f_{i,j,k} 表示 i 出发跳 2^j 步，删了 k 个点的最终位置。O(k^2) 暴力转移。总复杂度 O((n+q)k^2\log n) 。
CF2018E2
看上去人类智慧？
似乎不太可做，先考虑稍微暴力一点的解法：记 f_i 表示每个子集的大小都是 i 时，最多可以分出多少组。求单个 f 可以贪心做到 O(n\log n) 。r ，每次操作是后缀加，查询全局最大值，于是可以发现只保留后缀最大值也是对的。记一下后缀最大值的差分数组，每次找到 \ge l 的第一项更新差分数组即可。如果 <l 的都不是后缀最大值了就说明全局最大值增加了 1 。复杂度 O(n\alpha(n)) 。
这部分题解提到了一个 trick：l,r 互不相同的区间，则差分数组变为 01 序列。思考起来更形象，但是就按照上面说的做也行。
这样做应该就可以过 easy version 了，但是还不够。
容易发现 f 具有单调性，考虑“整体二分”。注意到这个其实是虚假的整体二分 ，你如果知道 f_i 的值，对于 f_{i+1} 还是要把 n 个区间遍历完的，就是其他点的答案只能帮你限制当前的 f ，如果要具体求解的话需要跑满。f_i\le\frac ni 。显然这个东西的值只有 O(\sqrt n) 种。虽然我们的整体二分丧失了绝大部分功能，但是最基础的“如果当前 f 上下界相等，可以直接返回”的性质还是有的。配合上前面单个值的方法，简单分析复杂度可以发现是 O(n\sqrt n\alpha(n)) 。
CF1707E
说是结论和 NOIP T4 有异曲同工之妙。
f^k((l,r))=\bigcup\limits_{i=l}^{r-1}(f^k(i,i+1))
倍增套 rmq 即可维护这个东西，查询跟着倍增数组查就行了。O(n\log^2n) 。
QOJ9559
维护用线段树/平衡树合并/分裂，问题在于查询。可以先离线下来，把所有要用到的叶子提前标记好，实现是容易的。
听说有在线做法，大概是额外开一棵树专门维护叶子。
Day 6
自习日。
写了下线段树分裂的板子，做上面数据结构题的时候感觉自己的代码力还是不够，还得练。
对平衡树比较生疏，不过发现大多数平衡树能干的事可以用线段树代替，但这毕竟不是长久之计。
Day 7
感觉节奏还可以，上来大概 40\min 切掉了 T1。cnt ，直接做是 O(n^3) 的，但是拿个 map 记有用状态可以过掉不少特殊性质，预期 44\texttt{pts} 。（事实上只得了 32 ）30\texttt{pts} 的暴力，过掉的时候大概离开始 3\rm h 。
翻了下其他人的分布，发现 T2 好像很多人都过了，于是又返回去看，发现自己很唐，没有必要单独枚举个数，直接把状态里面的 cnt 改为 cnt-cnt\_need 就好。半个多小时过掉了 T2。
总觉得 T3 后半部分的思路是对的，需要优化的是前面的分解质因数。感觉可以拿个什么 \gcd 搞一下，但是倒闭了。
100+100+30=230\texttt{pts}
要是省选真是这样就好了。
T1
真·简单题
### T2
贡献里面的 $-1$ 很烦，如果没有这个东西的话数位 DP 即可。所以可以直接枚举 $cnt$ 跑，复杂度 $O(n^3)$。
就像上面说的，把 $cnt$ 换成差值。具体的，定义 $f_{i,0/1/2/3,0/1,j}$ 表示前 $i$ 位，选的数要进位 $0/1/2/3$，$m$ 是否要进位，选的数减去预计选的数的差为 $j$。复杂度 $O(n^2)$，但常数有点大，循环展开或许会快很多。
也可以从高位往低位跑，因为每次 $m+1$ 之后高位基本不变。
### T3
%%%乱搞大师 recollect_i
考场上只会 $O(n^2\omega(V))$ 的做法，大概是把 $[l_1,r_1]$ 哈希一下，枚举 $[l_2,r_2]$ 的时候查就好。瓶颈在于分解质因数。
jiangly 顺便分析了一下碰撞概率。
发现并不真的需要分解为素数。这是一个常见处理手法：在值域很大、个数很少的之后，可以在 $O(n^2\log)$ 的复杂度内找到一个“伪素数”集合，满足两两互素，且原本的每一个数可以分解为这个集合内的数的乘积。
赛时想到了这个东西，但是不会求。
考虑增量构造，已知一个集合，现在加入了一个数 $x$。设集合内的元素为 $p_i$，先求出 $\gcd(p_i,x)=g$，若 $g$ 不为 $1$，那么可以拆分为 $p_i=gp_i',x=gx'$。考虑维护 $g,p',x'$ 三个数，问题在于 $g$ 和另外两个数并不互素。递归调用就行了。（糖丸了，没想到递归）
最后对所有伪素数尝试开 $d$ 次方，其中 $d|k$。
总复杂度好像是 $O((n\log V)^2)$ 的。
# [Day 8](http://oj.daimayuan.top/contest/313)
上来开 div1，发现保龄了，返回去开 div2:)
因为先做的 div1，等于是前一个小时在想 T2T3。结果心态炸了，差点拼尽全力无法战胜 T1（在两个半小时的时候 A 掉了）。
回到 T2，延续之前想的思路，倒着处理整个问题，即有向边变为双向边。发现题目中的定向直接视为双向好像差不太多，问题在于一些边界情况。没有必要统一定向，因为如果一些点可以缩为一个 scc 的话内部的边可以全部视为双向边，所以只需要看对于当前点是否存在定向方案即可。手玩之后发现上面的“边界情况”只有 $size=2$ 的 scc。所以记一下总共的 $scc\_cnt$ 和 $size=2$ 的 $scc\_cnt2$ 即可。
发现不会求初始图的信息，但想了一会儿又会了，启发式合并就行。
实现用了 `unordered_set`，本机 $3.6s$，交上去 $2.4s$，但愿能过吧。（因为样例是完全图，感觉跑的最慢也就那样了）
只有 $30\min$ 左右了，看了下大家 T3 都没过，于是打了前面三档暴力跑路。
期望得分 $100+100+27$，实际得分 $100+75+27=202\texttt{pts}$，被卡常了。
### T1
随便计算下贡献，方法很多，有树剖+线段树的，有线段树合并的，本人用的虚树。
### T2
上边说的基本就是正解，但显然用不着启发式维护边集。可以做到线性维护这个东西。
赛后耗时 $2\rm h$ 艰难战胜。
小知识：竞赛图一定存在哈密顿路径。
### T3
将方案转概率，对于 $a\to b$，如果相互独立，那么有 $a'=ab,b'=a+b-ab$。但这个东西错得离谱，因为显然我们的操作互相影响。
不过上面的东西并非毫无启发——在树上是成立的。（因为删去一条边之后两边不连通了）可以通过子任务 $4$。
环会导致不独立，枚举环上的一条边，然后断环成链。这条边我们选择为环上编号最小的点的出边，因为是第一个用到的，然后就和树一样了。
### T4
$k=0$ 可以贪。
发现只有一组样例，有蹊跷。打表可得答案是凸的（费用流建模可证），可以 wqs 通过 $q=1$。
考虑模拟费用流。
拿线段树维护模拟费用流时的修改即可。
# [Day 9](http://oj.daimayuan.top/contest/316)
前面有几天没跟着代码源练，所以我们不妨将中间的时间线消去，所以是 Day 9。
有事，没打比赛。
### T1
简单题，平均值等价于 01 分数规划。先将所有点视为好点，在当中选择一个点集 $S$ 删去。考虑 $S$ 的性质，不难发现是一个独立集，且这是充要的。
跑一个最小独立集，由于连边是区间，可以用线段树优化 DP 做到单 $\log$。
发现和 $k$ 无关，怀疑是想错了，但其实就是诈骗。
总复杂度 $O(n\log n\log V)$。
# Day 10
专题讲解：图论题目选讲。
### CF2046D
看上去非常网络流，于是思考怎么建模。
常见手法是把每个点拆为入度和出度，把最小个数表示为费用。方式很多，注意一下细节就行。
需要注意的是直接做对于环会有问题，所以需要提前跑缩点。
apaid：/,de'eg/。
### CF2041G
看上去比较好做，但其实不简单，主要是难写，需要想出一个可以写的做法。
如果边界的行列全为黑色，删掉之，然后把相邻（八连通）的黑格连边。可以发现白格是割点的充要条件是，染成黑色时候出现了环。
离散化一下，可以用并查集维护这个东西。
### CF2041K
题目比较绕，本质上是保证有向图的最长反链 $\le k$，求传递闭包之后 $|in(u)-out(u)|$ 最小的点。
先缩成 DAG，然后将他拆分为若干条链。这个是最小链覆盖，所以条数不超过 $k$。拆分出来之后对链 BFS，复杂度为 $O(k(n+m))$。
考虑如何求最小链覆盖，直接网络流不太对，增广次数是 $n-k$ 而非 $k$ 次。事实上要求出最小链覆盖不是一件简单的事，所以转而求一个尽可能小的链覆盖。充分发扬人类智慧，未被选择的点权为 $1$，选择过的点权值为 $0$，每次取权值最大的链。这个东西看起来没什么道理，但稍加分析可以得知这东西得到的链是 $O(k\log n)$ 条的，可以接受。
apaid 还给了一个随机取点的做法，比较乱搞，但复杂度是一样的。
### CF2029I
方差的常见套路是**枚举平均数**。事实上，如果把方差视作一个二次函数，会发现 $x$ 取平均值时 $f(x)$ 取到最小值，这刚好符合方差的定义。
用网络流建模，每次增广等价于求解最小子段和。这个东西用线段树就亖了，要暴力做，否则会凭空多一个 $\log$。发现数据范围保证了 $n\cdot m$，所以暴力是对的。
### CF1815F
给了三角形肯定有用，否则就变成了任意图成立了。
事实上确实比较诈骗，我们令每个三角形的边权分别为 $1,2,3$ 各一个，等价于三个点增加了 $3,4,5$。我们先把 $3$ 给每个点加上，作为初始点权，于是变为了 $0,1,2$。
这个可以理解为给每条边定向，然后每个点的点权为 $a_i+deg_i$。定向是简单的。
apaid：这样做是 work 的。诈骗题？放屁，就问你现场能不能做出来。
### CF1835F
“不好”就是增广不出来的时候把这一轮遍历到的点取出来。跑网络流就行。
考虑刻画 $|S|=|N(S)|$，发现其实就是若干限制“选了 $A$ 就要选 $B$”。这个是 2-sat，于是从这个角度思考这个问题，即如果存在 $(i,j)$ 且 $link_j\ne i$，连边 $i\to link_j$。新图上 $i$ 可达的点就代表最小的包含 $i$ 的点集满足 $|S|=|N(S)|$。
缩点，问题变为 DAG 上找最少的边，可达关系不变。感觉从原问题到这一步的转化过程还是非常巧妙的。
最后是一个简单贪心，发现可以 `bitset` 优化做到 $O(\frac{n^3}\omega)$。
### arc176_e
$n=10$ 是坑点，难点在于想到网络流。
其实连边套路是见过的，和[切糕](https://www.luogu.com.cn/problem/P3227)类似。用割掉一条边表示这个变量的取值即可。
### QOJ1197
顺序：黑条，白条，单点。
大致想法是先用一些 bool 变量把答案表示出来，然后利用这些变量建模。
存一下 black_row，black_column，white_row，white_column，棘手的是每个点只能染两次，这很难写成一个二元限制。（怎么处理的忘了）
写代价的时候可以骚搞一下式子，比如 $+\infty\times(a\operatorname{or}b)$ 变为 $+\infty\times(a+b)$，反正都是无穷大所以无所谓了。同理好几处都需要调整一下限制，另外需要把一些变量的定义取反，然后就可以建图了。
apaid 说只要二元乘积项前面的系数是负的，就一定可以用最小割建模。不是很懂其中道理。
apaid：线上同步赛的时候拼尽全力建不出模。总之这题就非常难。
### QOJ9276
限制比较奇怪，题目保证存在一种方案使得每一行**至多**只有一张卡朝上，构造一种方案使得每一行**至少**有一张卡朝上。
事实上如果题目让你求那个至多的方案，是 NPC 的。(apaid 好像又说不是 NPC，可以做)
先对每一行去重，如果每一行的个数都 $\ge2$，显然有解，将保证的那组方案取反即可。
考虑那些只有一个数的行，于是这个数字的翻转情况确定。这有点类似于 topsort，于是先处理掉。然后每一行只保留 $2$ 个数，发现可以 2-sat，很难想到，但是讲出来就比较简单了。
# [Day 11](http://oj.daimayuan.top/contest/317)
打的比较炸裂。
上来 T1 只想到了暴力区间 DP，是 $O(n^5)$ 的，然后就觉得是推式子题，结果算半天啥也没算出来。发现每个点的答案可以拆成左右两部分相乘，于是上面的 DP 可以优化到 2D2D。写出来之后盯了一会儿代码，发现转移的时候可以拿个辅助数组记一下转移值，优化到 2D1D。过的时候已经 $1.5\rm h$ 了。
T2 在 $20\min$ 内敲出了 $O(nm)$ 暴力，然后剩下的时间分数就不变了。觉得这个东西非常线段树，但是怎么都写不出来，拼尽全力无法战胜。
T3 手模之后发现对于合法的方案只有两种情况：首先删掉不可能的点，要么所有区间有交且剩刚好 $2$ 个点，要么存在两个集合 $S1,S2$，他们之间没有交集，对于每个集合内的区间有且仅有一个公共点。但是发现并没有这一档部分分，因为这个性质仅仅可以减少 check 的复杂度。只能 $10\texttt{pts}$ 跑路。
发现(之前)隔壁机房的都阿克了 pretest，%%%。
$100+30+10=140\texttt{pts}
人均 200 ，蚌埠住了。
T1
定义 f_{l,r,k} 表示区间 [l,r] 进行比赛，胜者为 k 的概率。这个是 3D2D 的。f_{l,r,k}=f_{l,k,k}f_{k,r,k} ，所以我们只需要存左右端点两个数的获胜概率，状态改为 f_{l,r,0/1} ，优化至 2D2D。g_{l,r}=\sum_kf_{l,k,0}f_{k+1,r,1} ，可以做到 2D1D。
T2
题解糖丸了，用的分块，但由于这道题的操作可复合所以大家都是直接线段树。
难点在于列出分段线性函数，但是众所周知我不会这种比较抽象的东西。
T3
发现自己居然没有正式玩过血染钟楼。
又糖丸了，考场上枚举了 2^m ，但是显然游戏状态只有 O(n^2) 种，所以暴力应该是这个东西，可以获得 25\sim40 分。
分情况讨论，就是上面列出的两个 Case。
Day 12
专题讲解：字符串专练。
老板说低年级同学可以学一下字符串算法，发现我也没学过。这下只能现学现卖了。
QOJ9915
拓展了一下，$k=1$ 可以上科技，大概是搞一个 $(x-y)^2(x-y-1)(x-y+1)$ 的代价，然后 FFT。能匹配上当且仅当权值为 $0$。
一般这种**模糊匹配**传统的字符串算法做不了，一大原因是相等关系**没有传递性**。遇到这类问题常用的思路是 bitset。
设 $f$ 为一个 bitset，从左往右扫 $r$，$f_i$ 表示中心为 $\frac i2$ 的串是否仍然回文。构造一个 $g$ 满足 $|a_l-a_r|\le k$，每次用 $f\gets f\operatorname{and} g$ 即可。由于值域比较小可以预处理一些信息以快速计算 $g$。
赛时很卡常，std 是 bitset + 指令集。
apaid：你如果对字符串科技有一定了解，就知道这个东西做不了，一眼 bitset。
### QOJ9406
限制类似于一个三角形，但是发现三个限制中只有一个有用，就是那个“$\text{小}+\text{小}>\text{大}$”。
一个结论是 $S+T\ge T+S$ 当且仅当 $S^\infty\ge T^\infty$，其中加法表示拼接，后面的无穷表示无限个串拼在一起。
设研究的三个串为 $A,B\le C,A^\infty\ge B^\infty$，那么限制只剩下了 $A+B>C$。
这里可以设计出一个近似解，大概是找到一个偏序关系直接排序。~~直接 sort 被出题人卡掉了，但是先 shuffle 再 sort 可以过。~~
正解是注意到 $A$ 一定是 $C$ 的前缀，所以可以枚举一下然后二维数点。
### arc175_f
听说现场没人过。
在末尾加入一些字符之后考虑逆序对个数。设当前考虑的 $A=B+T$（显然只有两个串是前缀关系才有必要考虑），那么加上 $c$ 之后比较大小等价于比较 $c$ 和 $T^\infty$。
先后缀排序实现 $O(1)$ 比较字符串，然后怎么维护一下 lcp。比较掉线喵\~
### P9482
apaid：Day2 T2，但是做不出来就拿不到金牌。
首先不考虑回文串，那么可以当做比较一个前缀和后缀。这个是好做的，把前后缀拼起来跑 sa，然后二维数点。
所以只需要修一下回文串。这个如果对着 $l$ 做其实比不太好做，可能要在回文树上跳 $fail$。但如果是对着 $mid$ 做就直接是二维数点。
### CF2053G
发现造数据的同学就在现场，膜拜。
之前 jiangly 讲过一次。
简单说了一下题解里面提到了 wtf，就是 apaid 的乱搞。造数据的同志说尝试卡过那个做法，发现只有所有字符全一样可以卡掉，apaid 好像特判了。
正解就是按照两个串有没有公共循环节分讨。
### CF1909G
apaid 有一个基于数论硬做的方法，赛时卡了 $1\rm h$ 常，没有意识到考试结束了。
std 的精妙想法：直接枚举 $|y|$。这一步反而最难想到，因为太暴力了。
把 $y$ 看成一个窗口，有一个关键结论是如果 $y$ 合法且后面一位也能匹配上，那么把 $y$ 向右平移一位也合法。于是发现只需要判一下 $len$ 就解决了，求一下循环节，枚举一下 $m-n$ 的因数、最短循环节的倍数即可。
### GYM100962D
就是 [Border 的四种求法](https://www.luogu.com.cn/problem/P4482)。
apaid：感觉 SAM 的题经常配合线段树合并。
### CF1043G
大力分讨，显然答案为 ${1,2,3,4,-1}$。
难点在 $2$ 和 $3$ 的讨论，另外几个是简单的。
需要 runs？我不会，可以寄了。
求最短 border 的 trick：
先检测 $len\le\sqrt n$ 的串，如果没找到答案，那么答案在数组中位置不超过 $\sqrt n$。这是因为这些长 border 不能相交，否则会得到更小的 border，而这些 border 至多 $\sqrt n$ 个。
apaid：这就是一个板子检测题，把各种板子拼起来就过了。
### CF917E
std 点分治，但没什么用。
找到 lca，直链可以 AC 自动机，难点在拐点。
好像要建立失配树，然后对着等差数列双指针。
要二维数点，复杂度一个 $\log$。
补充一下树上路径是小串，给定大串 $S$，求路径在 $S[l,r]$ 中的出现次数。这个简单得多，是唐题，对 $S$ 后缀排序就行。
# [Day 13](http://oj.daimayuan.top/contest/318)
Dog_King 出的题。
别样的暴力大赛。
T1 看到随机，画了下图，很快想到了每次是把矩形切成两半。但是复杂度分析错误耽误了一点时间。
T2 字符串题，不擅长，T3 迷迷糊糊题，不会，总结就是摆烂了。
于是开始拼暴力。T3 一开始写了一个 $O(n!n^2q)$ 的东西，~~没分~~，样例跑了 $10s$，经过一顿乱搞拼尽全力无法战胜。想了一下发现可以预处理第 $i$ 大的贡献，写了一个 $O(n^4)$ 的做法，发现只有 $10$ 分。（虽然可以过全部 pretest）
但是发现常数很小，于是开始卡常，尝试通过 $n\le300$ 的部分分。简单改了一下循环的上下界，然后优化了一下取模，在代码源上好像不算慢的样子。
T2 的话一眼 SA 或者 SAM，选择的是后者。直接在后缀树上 DP 可以获得 $10\texttt{pts}$ 的高分，但是花了我 $1\rm h$ 的时间。
$100+0+30=130\texttt{pts}$，T2 好像挂了，但是 T3 冲的很快。
### T1
其实只需要暴力求就可以，数据随机保证拐弯次数不会过多。
数据不随机也可以做，用一些高级的归并。复杂度是严格的 $O(n\log^2n)$。
upd：后面经讨论可以离线做到 $O(n\alpha(n))$，大概是并查集合并一下，先找到将两个点切开前的矩形，找矩形和计算矩形内部贡献都是好做的。
### T2
$f_i$ 表示 $i$ 子树内的答案，DP 式和考场上是一样的，即搞一个辅助数组 $g_i$ 表示 $i$ 的儿子有几个不为空。提出了一个关键点，就是这里其实不是 $O(n)$ 的，是 $O(\sum)$，其中 $\sum$ 是字符集大小。（忘记题目限制了字符集大小了）
真的可以 DDP！发现 $g$ 数组不用上传，只需要上传 $f$，所以数组不是 $10\times10$ 而是 $2\times2$。
感觉考场上什么都想到了，但是做不出来。不会 DS，放弃了。
### T3
把上面写的“第 $i$ 大”改为“比 $i$ 大”，可以设计一个 $O(n^3)$ 的东西。
注意到堆本质上是一个计数器，处理 `c = min(c + type, i + 1 >> 1)`。正难则反，考虑溢出了多少，发现就是 $\max\{s_i-\lceil\frac i2\rceil\}$。可以转成“从一个点到一个点，不能越过某条线”的经典问题，翻折容斥，组合数一下即可快速求得答案。
修改就是个纸老虎，因为限制了加减的值不会很大，暴力平移即可。
复杂度 $O(n+qV)$，$V$ 是修改的权值。
# Day 14
专题讲解：计数问题杂谈。
### CF1842G
trick：一般这类求乘积的期望/总和，一般会乘法分配律展开处理。
把每个括号拆成 $a+v+v+\dots+v$，考虑每个括号选哪一项。 $f_{i,j}$ 表示前 $i$ 个括号，有操作了 $j$ 次的总和。直接 DP 就是 $O(n^2)$ 的。
### P11420
和上面的问题类似，算是加强版。
考虑贡献提前计算，状压一下。对于 $m\le16$ 的时候，容易状压做到 $O(n^2m2^m)$。事实上，当 $m>\frac n2$ 时，中间的那部分是浪费的，因为每次操作都会覆盖到，于是可以优化到 $O(2^\frac n2poly(n))$。
继续优化，发现需要状压的部分其实只有 $\min(n-2m+1,m)$。按照 $\frac m3$ 分一下类，可以做到 $O(n^6)$。
### CF1704H1
最后一定形如若干链 $a_1,a_2\dots a_k$，其中 $a_1$ 占领了 $a_1,a_2$，$a_i(2\le i<k)$ 占领了 $a_{i+1}$，$a_k$ 没有占领任何点。
所以可以把链长为 $1$ 的特殊处理，直接枚举链长为 $1$ 的个数和链长大于 $1$ 的个数，甚至不用 DP，可以直接计数。
### agc028_d
Dog_King 给了一个很逆天的做法：$V+F-E=C+1$。不过没看懂他在干嘛。
自己做的时候卡在环上了，结果直接破环成链是对的。显然最后的联通块在序列上是区间，于是区间 DP，$f_{l,r}$ 表示 $[l,r]$ 为一个联通块的方案数，这个可以简单容斥求得。
需要注意的是计算答案的时候，$1$ 和 $n$ 可能在同一联通块内，这个的简单处理手法是先把答案初始化为总方案数，表示 $1$ 号点所在联通块的贡献，接下来枚举区间的时候跳过 $1$ 号点就行。
### CF1774G
先考虑 check，可以直接贪。
看到奇偶相减，自然的想到对称，去构造相似的方案进行抵消。（另一个套路是 LGV 也要熟悉一下）
注意到如果存在一个区间包含其他区间，那么对答案就没有贡献（因为分别对应奇数和偶数的方案），可以丢掉。于是现在的区间互不包含。
现在我们有 $[l_1,r_1]\dots[l_k,r_k]$ 满足 $l_1<\cdots<l_k,r_1<\cdots<r_k$。显然第一个区间必选，注意到假设有 $l_3\le r_1$，此时可以直接选第三个区间，但一旦选了第三个区间答案就是 $0$（因为第二个区间选不选分别对应奇偶方案），又可以丢掉。这就导致对于一组询问，其实最后得到的可以选择区间是**唯一**的！换句话说，答案为 ${-1,0,1}$。
更加形式化的，首先找到 $l$ 最小的两个区间，标号为 $1,2$。接着，找到左端点大于 $r_1$ 的第一个区间，设为 $3$ 号区间，找到左端点大于 $r_2$ 的第一个区间，设为 $4$ 号区间……以此类推，最后得到的区间如果并集为 $[l,r]$，则答案为 $(-1)^k$，否则为 $0$。
### CF1804H
先考虑给定一个排列，在序列上计算答案。此时 $dis$ 就是差分，这个可以状压得到，是简单的。
从序列扩展到环，多了一个取 $\min$ 的操作。考虑所有的直径，计算他被跨过的次数。这个东西直接算刚好对应的就是想求的劣弧而非优弧，是我们想要的。
于是直接考虑 DP 直径两半的集合。发现 $C_{16}^8$ 其实可以接受，只有 $1.2\times10^4$。需要注意的是转移不能直接写，需要一个中转状态，把删一个数和加一个数分开写。
### P11746
显然有 $n+m$ 为奇数。
“不相同”这个限制是困难的，考虑“相同”的行列是偶数。容斥，容易做到 $O(nm)$。把式子列出来，暴力推一下，发现可以优化到线性。不过要快速幂，所以 $\log$ 是跑不掉的。
### CF1375H
暴力 $O(nq)$ 是简单的。
合并操作其实就是要求值域不交，所以需要存的有两个维度：下标和值域。显然可以树套树做到 $O(n\log^2n)$。
不知道会不会被卡常数（指的是操作次数的常数），不过可以写值域分块，每一块内部按下标排。
### CF1553I
Dog_King：《比较板的 NTT》。
显然极长区间没有交，所以可以根据 $a$ 得到区间的结构。以样例一为例，对应的结构一定为 $[1,2,3],[4],[5],[6]$。对于单个区间，方案数是好算的（注意公差要分正负），问题在于“极长”这个条件。果断容斥，可以列出一个平方级别的 DP 式，即用 $f_{i,j}$ 表示 $i$ 个数分为 $j$ 段，转移可以用前缀和做到常数。继续硬做没什么前途，分治 NTT，最后是大常 $O(n\log^2n)$。
### arc140_f
与上一个类似。刚刚的每一段是一个等差，现在是一个差值确定的等差，看上去更好做了。
看到题解里有一个很妙的东西：$|p_i-p_{i+1}|=m$，考虑 $p$ 的逆映射 $p^{-1}$，有 $|p_i^{-1}-p_{i+m}^{-1}|=1$。于是按照余数分类，即可变为 $m=1$。
说回这道题，二项式反演暴力求解是容易的，找到生成函数后发现可以 NTT 直接求解。
### CF1781H2
显然要找到能包含所有 $1$ 的极小矩形，然后平移到最靠左上角的可以放的地方来去重。
发现这个“平移”可以刻画为若干限制，加上题目原本给的，于是现在有若干位置被钦定为 $0/1$。
不急，下线一会儿……
复杂度 $O(hw\max(h,w))$，同阶就是三方。
### CF2062H
经典套路是，显然全 $0$ 的行列可以删掉，然后题目中有 $3$ 条边的限制可以变为任意同行/同列的点之间全部变为 $1$，然后求联通块。发现直接跑也是对的，不用删全 $0$ 行列。
联通块可以用可以包含的极小矩形刻画，定义两个矩形没有交当且仅当行和列分别没有交。每次合并两个矩形。
于是现在会求解单个集合的联通块个数，但题目要求所有子集。可以对列扫描线，行状压处理。
### CF2029H
先暴力，比较套路的是预处理集合 $S$ 的停留时间，于是接下来每一次都会有新的人加入集合。DP 的时候需要枚举子集，复杂度 $O(3^n)$，~~但听说赛时有人卡常卡过去了？~~
直接做不太好做，考虑容斥，$f_s$ 表示集合 $s$ 里面的人都知道消息，集合外的人随意的期望时间。把 DP 式列出来发现可以拆开，然后半在线卷积优化(根据 popcount)。复杂度 $O(2^nn^2)$。
### CF1761F1
找找性质。
手玩一下，一个合法排列一定满足：(交换奇偶后面的内容也成立)
- 奇数位置先递增后递减。
- 偶数位置先递减后递增。
画在图上像一个矩形。
注意到这个之后就可以 $O(n^2)$ DP 了。具体的，根据环上的顺序 dp，枚举一下起点，$O(1)$ 转移。
### CF1761F2
题解里有关于上面结论比较清晰的图。
前缀和一下，然后翻折容斥怎么搞一下。
# Day 15
杂题选讲。
### QOJ10108
实际上 $01$ 串并没有什么用，任意串都可以做。
前缀和一下，变为 $0,n$ 必选，每一段必须比上一段大/小。容易想出暴力 DP：$f_{i,j}$ 表示前 $i$ 个数能否划分为前 $j$ 段。手玩一下，其实这个东西可以贪，尽可能靠前，并且在 $t$ 串中相同的一段统一处理更加简单。
### QOJ10101
$LIS(a+b)=LIS(b+a)$ 这个条件直接构造本身比较困难。一个简单的思路是令 $b$ 序列递减，这样拼接之后至多令原先的 $LIS$ 增加 $1$。不过可能会出现等式一边加了 $1$ 另一边没有加的情况，不妨设左边多了 $1$。
显然不可能存在构造使得等式两边的结果变小，只能让他变大。考虑翻转 $b$ 的一段前缀，发现只需要考察能使右边变大的、最短的一个前缀。可以证明如果该方案不行则无解。
### QOJ10110
考察一棵树是不是好的。
假设有一个权值，他需要从 $a_1$ “运输”到点 $a_k$，于是这条路径上的边以及与路径相邻的边会有一些选择的顺序。所以每一个点的所有出边的顺序都是固定的。具体的，把路径画出来，应该是一个欧拉回路。
下线ing……
转化完最后是一个 DP。直接写是 $O(n^4)$ 的，但可以交换 DP 顺序做到 $O(n^3)$。
### QOJ10104
把每个时刻的格子当做一个点，连边 $(t,i,j)\to(t+1,i+1,j+d_i)$，容易发现最终是若干条链，且答案为 $\prod(len+1)$。
由平移点改为平移网格，这样每一条链都是竖直向下的。统计每种长度的链出现了多少根即可。
给了一个笛卡尔树上启发式合并的做法。
### arc193_c
倒着染色显然更好处理。
第一次操作等于要同时删除一行一列，后面的操作只需要删一行或一列。
直接 DP 即可。
需要判一下边界，比如全部都是删行或者删列。看上去不难，但实际上细节很多。
### arc193_d
只关心相对距离。
对于 $a,b(a<b)$ 两个点，显然每一步可以使他们之间的距离减少 $0,1,2$。贪心地去匹配。
下线ing……
### QOJ10102
拼尽全力无法战胜题目后面的彩蛋。
听到什么转置？？？
### QOJ10111
把题目抽象为切割矩形。每次等于是把矩形的中间竖着切开，然后可以上下翻转。
于是可以由此刻画一个 $z$ 能否变为 $a$。
考虑区间 DP。发现贪心策略是尽可能往前切。但是这样会算重，原因是序列中可能存在相同的数，此时就寄了。于是考虑如何去重，这个比较简单。
# [Day 16](http://oj.daimayuan.top/contest/319)
**最后一舞！**
可惜的是并没有打，因为上午一直在腹泻，来学校发现 Fiyuls 也寄了，鉴定为昨晚上吃的面的问题。
### T1
这类题目已经不陌生了，显然可以转化为每次染一行/一列。
补成一个完整的矩阵，考虑什么样的矩阵可以被染出来，对于任意两行 $i,j$，一定有 $i\subset j$ 或者 $j\subset i$。设 $s_1\subset s_2\dots\subset s_k$，求方案数的话一种经典的方法是对差分计数，即 $\{^n_k\}(k+1)!$。
现在回到原题目，显然可以交换两行间的顺序，于是不妨设 $l_i\ge l_{i+1}$。考虑对轮廓线 DP，设 $f_{i,j}$ 以第 $i$ 列作为右边界的矩形，有 $j$ 种本质不同的行。根据上面的子集包含关系，转移有 $f_{i,j}\xrightarrow{j+1}f_{i+1,j}$ 和 $f_{i,j}\xrightarrow{j}f_{i+1,j+1}$。这个是当前列染色的转移，另外上移边界也要转移，每次移动的时候，可能导致 $j-1$，也可能不变。
### T2
其实树状数组是可 $k$ 进制的，但是这个题给的代码不太对。正确的 $k$ 进制树状数组 `lowbit` 函数返回的应该是最低非零位的**位权**，例如题目给出的 $5430$ 应该返回 $10$。
所以其实题目给的代码并不是在求前缀和。
`query` 是好做的，因为暴力的复杂度就是对的。问题在于 `add` 函数，因为可能每次加的数都很小。
考虑 $k$ 为奇数且 $n$ 较小，发现每次取 `lowbit` 都是同一位，根据数学知识我们知道这一位的变化是有循环节的，于是可以处理这个循环节。
现在考虑 $n$ 较大，这样的话显然空间是开不下的。加速找链的过程。
现在 $k$ 可以为偶数，那么可能会出现 `lowbit` 这一位加着加着为 $0$ 了。经典套路之把 $2$ 的质因数分出来，令 $k=k'2^r$，那么 `lowbit` 这一位会变为 $0$ 当且仅当原本的值为 $k'$ 的倍数。这里依然可以暴力，如果判断当前 `lowbit` 这一位会变为 $0$，直接暴力做这部分，于是就规约到了 $k$ 为奇数的子问题，可能细节会多一点。
### T3
感觉是乱搞题。
要用 **DFA(有限状态自动机) 最小化**。显然我是不会的，但是看介绍好像并不算特别难的样子。过程有点类似 **DP 套 DP**。即删除无用状态、合并等价状态，使得最后的状态数最少。
设移动步数为 $k$。首先是 $k=0$，那么每个颜色即为一个等价类。对于 $k>0$，我们要尽可能的减少状态数。这玩意看上去没法倍增优化，因为你倍增最多求到等价类，求不到走多少步之后变得不等价。
考虑**启发式分裂**。
总复杂度 $O(n\log n)$。