NFLS
SDNetFriend
·
2021-12-15 21:28:29
·
个人记录
模拟赛
WC2022 模拟赛 1
西可。流
题意……迷惑得很，全场最高 18 pts 还是只输出了特殊情况。转化成了电阻网络模型，然后最后求的效率就变成了起点到终点的电势差。很玄学，没看懂补图的意义何在，总之就是只看给定的边，然后 1\to n 要连通并且不能有矛盾，即满足两点间电势差一定，无论走哪条路都一样。不满足这两个条件就是特殊情况，否则输出起止点电势差即可。
西柯。串
两个比较神奇的引理。
最终操作次数 \leq n 。只要从前往后一个一个扔就可以了。
既然这样那其实就是要考虑哪些位置可以固定，整体减去固定个数即是答案。
对于 A,B 中分别对应的元素 x,y ，设 pre_A(x) 表示 A 序列中 x 之前的元素的集合，保证 pre_A(x) 被 pre_B(y) 包含是 x,y 可以固定的充要条件。
因为操作肯定是从后往前扔数，也就是两个数如果不移动那么它们前面的数只多不少，否则一定有数要向后走就需要移动这两个数便不可以固定。所以必要性是一定的。对于充分性，其实本来是要考虑第 i 个确定元素到第 i+1 个这段的，但考虑到前 i 个都满足条件，如果扩充到第 i+1 个时，新区间内多出来的都可以扔到前面去，依旧可以满足条件，故得证。
西壳。仙人掌
自己捣鼓了个玄学做法。
首先，建圆方树。然后设一个 f_{u,fa} 表示 u 以 fa 为父亲时子树内的最大深度，于是可以记忆化搜索。具体来讲，对于一个圆点，它的答案就是除了父亲以外的子树答案取最大。对于方点，朴素做法是得到除父亲以外的每棵子树的答案排成环然后枚举位置。这样做对于环的处理复杂度是 O(n^2) 的，只有 70 分。
然后考虑对环的优化。可以设一个阈值，大概是 10 ，如果环大小超过阈值，就以方点为根整个跑一遍，对跑出来的环上答案建 ST 表用 RMQ 来倍增得到答案，这样环上每个点的处理代价就变成了 O(n\log n) ，可以通过，但复杂度过于玄学并且卡时通过。
似乎和正解差不多？不过正解是有序搜的，即采取换根 DP，如果直接乱记搜可能会降低命中率导致出问题，然后喜提四倍常数。
WC2022 模拟赛 2
A. 木偶
神奇题，神奇到连题解都没有，其实是找规律。
首先很好写出 O(n^3) 的朴素 DP，然后把表打出来，发现最边上那一斜线的答案就是组合数，然后发现相邻斜线的系数很有规律，以 k=8 为例，那么系数就依次是 \frac{8}{1},\frac{7}{2},\frac{6}{3},... ，于是只要预处理出阶乘就可以做了，问题不大。
B. 点格棋
想简单了……大部分的活包括什么并查集啊，找环，链之类的都做的很成功，甚至比正解更简洁，但如何博弈没想清楚喜提 0 pts。
首先显然能决定开哪个连通块的人会从最小的开始开，如果下一个人直接吃完就相当于交换了先后手，这时候最重要的地方在于：考虑如何使先后手不变 ，然后发现不变的代价，在链上是留两个位置，环上是留四个位置，可以证明一定可以达到目的。于是可以直接 DP。考场上人都傻了啥也不会（为啥一个连通块的还写挂了啊）
这类博弈问题需要注意的就是角色奇偶性的改变对局面产生的影响。
C. awa
正解过于毒瘤无人能做，于是拆成四个部分分，死于多测不清空 。（又不是回答 Yes No 的为啥要多测啊）
Subtask 1
暴力搜就可以。
Subtask 2
发现是菊花图，只要特判询问的点是叶子还是根，然后统计下总体答案就可以了。
Subtask 3
一条链的情况，经典套路主席树查区间 pre_i<l 的点的个数即可。
Subtask 4
我挂得好冤啊。点分治，用树状数组维护子树深度，每次考虑一颗子树就先干掉其贡献然后退出时加回去就可以了。
WC 2022 模拟赛 3
最爆炸的一场，不 要 熬 夜
A. 甜甜圈
高维问题一定要先考虑是否可以各维度分开考虑，可以大幅降低难度。
可能刚开始漏了四角覆盖的情况导致后来也没有分开考虑的意识，以后要先手玩样例防止理解误区。
然后对于一维上的问题，我们发现其实可以规约成另一个问题：“给定序列上 n 个区间，对于每个区间，包含和没包含的部分分别打上不同的专属自己区间的标记，问出现次数最多的标记组合的出现次数。”然后对于标记肯定不能直接打是 2^n 的，考虑转换标记，即每个区间都异或一个 62 位的二进制数，因为是整个序列所以最后不同的标记在这题里只有 10^6 个，根据生日碰撞不会出现问题。
即随机数序列标记也是一种类似哈希的方法，异或起来的值表示了区间的性质。这玩意实际上就是哈希，对状态数极多的标记的特殊处理方式。
B. 机场
一眼能看上去是个费用流，但不会建图全部白搭
网络流干支流模型
应用场景：描述对总流量限制时，如果采取“填满”来限制有可能会导致通到一起去之后信息失去辨识度，导致无法得到正确的信息。此时可以将“填满”转化为“分完” ，每次有消耗就分出去一些流，在消耗结束的位置再流回去。这样分出去的可以单独跑一路就不会造成信息的损失。
对于本题，可以对每个时刻 A 类位置建图，即建一条从起始到最终时刻的链，流量限制为 a ，这个成为“干流”。同时对于每个飞机，发现选择不多，即：停在 A 位置，停在 B 位置，停在 A 位置之后下一时刻挪到 B 位置。然后发现停在 B 不会对 A 位置产生影响，同时会产生最大的消耗，那剩下两种情况可以转化为对消耗的减少，但需要占用 A 位置。
也就是每一个飞机，如果想要减少消耗就建一条支流，在对应的占用时间分别连边并加上费用，这样直接跑最大费用最大流即可解决问题。
网络流注意点
费用流 EK 算法跑得比 Dinic 快，因为此时 Dinic 很难多路增光，而 EK 可以省去多余的边的遍历。费用流只要原图没有负环就不会跑出负环，如果一直 BFS 可能是别的地方写错了。
C. 计数题
WC 2022 模拟赛 4
A. 随机背包
对于合法情况数远远溢出的情况不用折半搜索而考虑分开贡献。
首先因为数据随机，所以期望会有 2^{240} 个不同的数，这远远超过了 p 的范围，也就是期望每个数都能找到。
所以朴素一个思路是折半搜索，即先预处理 5\times 10^6 个不同的数，可以选前 20 个元素的子集，然后在后面枚举一下在前面查找，这样期望每个询问的复杂度大概是 200 次带个 \log ，大概是 60-80 可惜人傻自带大常数只有 60 。
然后考虑正解，我们发现 40 个数的子集是妥妥能表示出所有数的，考虑拆成六个部分，同时把询问的 x 搞成 32 进制，然后这六个部分每一段负责一个预处理一下即可 O(1) 回答询问。
B. 最小生成树
点有点权时，并查集和最小生成树可以构造出堆的性质。考虑构造特殊性质有利于问题简化
考虑朴素做法，即每次都连一条 1\to u 的边，然后如果 u 所在连通块与 1 连通（不是第一次加边都是）就断掉 u 与 1 路径上的最大边然后加上当前边。那么每一步加上哪个点自然就是由这两条边的权值决定。
然后考虑一个神奇的构造性质 ，首先我们从边考虑贡献，因为我们可以把生成树构造为堆的性质，即上面的点权值都比下面的小。那么考虑从加第二条边开始，被删去的边对应的点一定是把当前边作为父向边的点。从第二步开始，无论取哪一条边都是上面连通，那么必然在下边取。由于堆的性质，最靠近的边权一定最小，于是一定连下面的边。
因此归纳可得每一步都符合连通的位置在祖先上，也就是说一定取一个定点。那么把点和其父向边权值加起来排序，然后从小到大加在答案里即可。
C. 村庄道路网
判断一张无向图是否是树：点之间有 A,B 两种互反的关系，且各自具有传递性，每个点只与一个和其有 A 关系的点连边的无向图是树。
首先这个题 y\geq 0 是唬人的，不要管这个，直接看成一个完整的平面直角坐标系即可。
我们分析一下可以得知，这里说 u 对 v 有 A 关系表示 u 离原点的曼哈顿距离比 v 大，那么 B 关系自然就是更小。我们分析得知，和 u 有 A 关系的点只能有一个，这说明原图实际上可以变为一棵无向树。
如果我们以原点为根，那么问题就转化成了给定两点求各自到二者 \text {LCA} 的距离。然后分析一下可以尝试优化一步一步走的过程，即如果 |x| 和 |y| 相差较大则会一直走直线，相差不大就会在四个象限反复横跳。我们称第一种为直线优化，第二种为螺旋优化。
对于直线优化，直接走就可以。对于螺旋优化，两步两步走，这样坐标变化会很有规律。然后最好加一个循环，因为螺旋之后还可能有直线，加循环可以避免讨论，于是本题结束。
WC 2022 模拟赛 5
打得最好的一场 QwQ
A. 这是一道简单数据结构题
现场切了没什么问题，不过对于主席树区间加直接采用差分改成单点加，最后对整棵树统一处理了每个区间的最大值。
实际上主席树处理区间加问题最方便的方法是使用标记永久化的线段树。不然 pushdown 实在是太难处理了。
B. 这是一道简单求最值问题
C. 这是一道简单计算题
Cayley-Hamilton 定理
先咕一小下。
注意矩阵乘法具有分配率！
WC 2022 模拟赛 6
虽然不是很好但很舒服。
A. PolarSea 与 rating
首先一个数有原根，当且仅当其是 1,2,4,p^k,2p^k(k\in\N^*,p\text{是奇素数}) ，然后有了这个之后，我们先来考虑 A=B 的情况怎么求，那因为要求的是和，所以考虑每一个有原根的数的贡献，即看多少子集会包含这个或这类数 。那自然分成五部分讨论：
对于 1 的贡献直接 {len\choose A} 即可，其中 len=R-L+1 。
对于 2 的贡献，我们设 c 表示当前区间奇数个数，那么就是 {len\choose A}-{c\choose A} ，即减掉全奇数的子集。
对于 4 的贡献，我们设 a 表示区间是 2 但不是 4 的倍数的数，那么用所有的减去没有 2 因子的减去只有一个的就是至少两个的，于是是 {len\choose A}-{c\choose A}-a{c\choose A-1} 。
然后对于 p^k 的贡献，我们设区间除去 2 以外的质因子个数是 b ，奇数的这个贡献为 d ，于是其贡献为 b{len-1\choose A-1} 。
对于 2p^k 的贡献，我们考虑用上面的减去没有偶数的子集，即 b{len-1\choose A-1}-d{c-1\choose A-1} 。
然后现在的问题就在于求 S(n,m)=\sum_{i=0}^m{n\choose i} 这个东西就可以做 A\neq B 的部分了，根据组合意义可以想到，S(n,m+1)=S(n,m)+{n\choose m+1},S(n+1,m)=2S(n,m)-{n\choose m} ,第二个式子直接组合意义考虑，即原来每种不到 m 的组合都可以塞进一个新来的。有了这个直接分块预处理即可。
注意组合数前缀和的计算。
B. PolarSea 与前缀和
即便是一种较劣的但易于计算的情况，只要包含了最优答案计算就没有问题。
我这个 O(n^3A) 的垃圾做法在 bitset 的加持下卡过去了 60
我们考虑枚举最终位置 i ，然后设 f_{i,j} 表示考虑前 i 个和为 j 最多取几个，同时 g_{i,j} 表示考虑 i 及之后的和为 j 最少取几个。然后枚举位置，枚举前面的和，我们发现后面的和合法的一定是一段区间，于是单调队列优化。
但怎么保证最终位置一定是 i 呢？可能溢出或者不够啊。因为这里并不是严格的 i 位置，如果不够了就把位置前移，要不然就后移，总之这样的代价一定不会高于把前后挪过来的最大代价的，并且一定包含答案，故可以解决问题。
C. PolarSea 与位运算
写了个玄学的三棵 Trie 剪枝来剪枝去卡过了 60 ，正解是做 \log 次 FWT，所以爬去学 FWT 了。
这个题学了 FWT 简直就是板子中的板子啊屑屑屑。
WC 2022 模拟赛 7
A. 卷王 tzc 和 tree
很玄学的做法，甚至碾了标算。
首先肯定要缩链，即只有一个儿子的点没用，像建虚树那样新建一棵树即可。
然后刚开始数据太水暴力做就过去了，后来加强数据记忆化照样过。题解里的方法是考虑 DP，因为有 w 的限制，所以想要到 u 点仍然有任务那么分配任务的位置到 u 的深度差不能超过 \log w ，于是根据这个，设 f_{u,i} 表示 u 节点，下方的点到当前点贡献是 j 的答案，然后每一次询问枚举因数复杂度就可以达到 O(q\sqrt[3]w) 。
然后分析一下发现如果记搜 + 暴力复杂度上界是这个玩意，于是可以快乐地碾标算了。
B. 颓王 lxr 和 matrix
C. yxh 和 dag
一道依赖数据随机的题，数据不随机出题人也不会？怀疑这里随了一棵深度 O(\log n) 的树，于是就随便搞，把询问离线下来，维护对于当前区间右端点，所有左端点的答案。每次加进来一个右端点就暴力枚举其所有父亲，包括加进来的那些边到根的路径更新即可。
然后链的部分分过不去，所以？咕。
WC 2022 模拟赛 8
A. 滑翔
全员 AC 的题，我却差点没过去。
思路即如果把过程反过来，那一定是走对应方向第一个比自己高的山。那么就可以顺逆建两棵树，用树剖搞搞就可以。实际上也可以用树状数组维护子树贡献，这样是一只 \log 的，但很玄学自己的树剖两 \log 跑得更快。
B. 乘积
满分需要 NTT，一直没学，部分分没啥难度直接 O(n^2) 暴力枚举，然后考虑下 A 全都相等的情况就有 80 。
C. 字符串
做法不少，写了 SAM 和线段树合并。
尝试像 NOIP2021 的 T2 那样转化一下，我们对于任意一对合法的 (R,T) 都可以找到唯一的 [a,b]=[c,d](d>b) 与之匹配，则 [a,c) 即是那个 R 。
那问题就转化成了找到所有的 [a,b]=[c,d] 并计算这里所有 [a,c) 的贡献。
那么对于找所有相同的子串自然可以想到 SAM。首先把串反过来，那么对于一对匹配的位置其贡献即为 w_{p_i}-w_{p_j}(i>j) ，其中 p_i 代表当前串第 i 次出现的位置。然后式子就变成了 \sum_{i=1}^{|p|}\sum_{j=i+1}^{|p|}(w_{p_j}-w_{p_i}) ，然后分离讨论贡献发现实际可以转化为 \sum_{i=1}^{|p|}(i-1)w_{p_i}-\sum_{i=1}^{|p|}(k-i)w_{p_i} ，然后建出 SAM 之后这个就可以用线段树合并维护了。记得写垃圾回收否则会 MLE。
WC 2022 模拟赛 9
A. [1K1K模拟赛] 高亮
赛时真是想到大部分然后不会去重。
首先因为只是考虑可以匹配的前后缀，那么枚举 T 中的中点自然不方便因为难以去重。然后因为是子串问题，故考虑使用 SAM。
我们发现，如果我们对 T 的正串和反串分别建 SAM，那么我们统计对于一个前缀有多少后缀能与之匹配，即是看有多少后缀出现位置和当前前缀的出现位置有交，那么自然是在正串的 SAM 上找到该前缀的所有出现位置然后统计答案。
首先的想法是我们维护每个位置出现了哪些后缀然后放到正串树上搞线段树合并，但难搞的是可能每个位置的后缀数是 O(m) 的就非常难搞，考虑优化。
当我们考虑每个位置出现的后缀时，我们实际上是在反串的树上找到每个点到根的路径上出现的所有的后缀 。这就有趣了，因为是收集一个路径上的信息，所以考虑我们可以树剖一下，然后对所有后缀出现位置重编号，这样每个 T 上的位置对应的出现的后缀就是 O(\log m) 段区间，然后就可以用线段树合并维护区间并了。
代码算是很难写了，各种变量不知道取什么名字。
寻子树信息转化为 dfn 连续段（这个已经用烂了），然后寻链信息比如什么到根路径的问题用重链剖分来解决。关键在于信息表示的转化。
B. [1K1K模拟赛] 我们
总结
区间计数问题记得考虑分治，因为通过分治可以将所有区间唯一地对应到一个区间中点上。
做法
首先考虑这个“左值”的限制，我们发现对于每一位，最终的左值这一位为 1 当且仅当区间内对应的位既出现了 0 也出现了 1 ，那么我们发现区间的左值是具有区间包含单调性的，很巧最大值也包含这个性质，考虑如何利用。
那我们分治，先考虑最大值，每次我们可以得到 O(n) 个区间集合满足区间最大值相同，这个可以直接双指针扫出来问题不大，当我们处理了这些固定最大值的区间集合时，考虑如何计算贡献。首先考虑最大值在左边，那么枚举左端点从左往右，这个时候我们要统计左值大于等于最大值的区间，那么左边的区间变短右边就需要右移，那么就一直移直到左值大于等于最大值。这时只要暴力移动即可，因为我们需要右移当且仅当左值有一位产生了变化，而每次最多移整个区间，那么复杂度上界即 O(n\log n\log v) ，几乎不可能卡满于是可以通过。
C. [1K1K模拟赛] 军队
WC 2022 模拟赛 10
A. 旋转多边形
总结
只能写一种胡起来的奇怪做法，对于已经实现的做法暂时没想通为啥对就先不写。同样不要过度转化。
做法
这里直接给了向量我们就要利用向量的性质，这至少比直接给你转化后的形式让你搞成向量要简单一些。
那么考虑向量点乘，结果的正负性取决于二者夹角，那么对于最终向量 v 考虑作一条与其垂直的直线，直线两侧点乘 v 的正负性不同。于是问题转化成能否找到一条直线使得存在一侧的向量编号连续，即只有一个编号连续区间。
那么考虑双指针维护当前一侧的所有向量，然后动态维护段数，在移动过程中如果存在段数为 1 的时刻说明有解，否则说明无解，复杂度瓶颈为极角排序的 O(n\log n) 。
B. 阅读理解
总结
自行开发的最劣的单 \log 做法。
记得完全利用数据结构，不要对问题过度分解，可能会导致问题复杂化。
像这种多关键字排序，数据结构也可以维护不止一个关键字，只要把两个状态压缩起来就没有问题，可以用平衡树或是动态开点的线段树。
做法
首先处理一下每次找的是删完之后对应排名的元素，但考虑这个实在麻烦，考虑用数据结构处理一下当前删后对应排名的元素在原序列中的位置，这个可以用动态开点的线段树然后在线段树上二分得到。
然后考虑这三个关键字，首先确定我们需要的 u 可以直接二分得到，然后剩下两个关键字可以一起考虑！ 具体来讲，我们把每个点的权值直接设成 (n+1)h_v+v 然后直接塞进根据 DFS 序开出来的主席树里面即可。那么最后也是每个询问在主席树上二分，只要减去对应子树的一段即可，也就是三棵主席树一起二分。时空间复杂度均为 O(n\log n) 。
C. 香蕉与求和
题意
比较复杂所以写一下：
给定长为 n 的正整数序列 a ，以及三个正整数 m,s,t 。对于一个下标序列 T 定义：
G(T)=\gcd_{i=1}^ma_{T_i}\\
S_x(T)=\sum_{i=1}^m a_{T_i}^x\\
P_x(T)=(\prod_{i=1}^m a_{T_i})^x\\
W(T)=P_1(T)\text{的最小质因子}
最终我们要求出对所有合法 T 的 G(T)S_s(T)P_t(T)W(T) 的答案之和。
解法
观察一下，能够发现 S,P 两个似乎可以推，而剩下两个似乎可以枚举。首先考虑枚举部分，想一下其具体取值有多少种，能不能通过枚举固定？ 看一下值域只有 10^6 似乎是可以的。对于 \gcd 这一步，一般都要想到欧拉反演，即考虑枚举它们的 \gcd ，这样总复杂度至多是个调和级数 O(n\log n) 的（指对于每一个 \gcd 的合法集合大小），也就是讲现在式子变成了：
\sum_d\varphi(d)\sum_{T,\forall_id\mid a_{T_i}}S_s(T)P_t(T)W(T)
那我们现在考虑如何处理后面的部分，同样地，我们考虑得到所有的 W(T)=l 的答案之和。但是这类问题直接求等于的情况的限制是很大的，故考虑容斥先求“至少”“至多”的答案 。这里我们选择求至少（总感觉至多也可以？）即限定选的所有的数的最小质因子都 \geq l 。所以现在式子变成了：（这里设 L(x) 表示 x 的最小质因子）
\sum_d\varphi(d)\sum_l\sum_{T,\forall_id\mid a_i,L(x)\geq l}S_s(T)P_t(T)
前面的所有限制实际上都是在限定集合，后面的东西就相当于从集合里面随便选然后求贡献。
那实际上我们现在只需要解决：
\sum_T\sum_{i=1}^ma_{T_i}^s\prod_{i=1}^ma_{T_i}^t
考虑如何计算序列中一个数的贡献。对于序列中的一个数，它要乘上所有包含它的可能序列的值之积，那考虑这个东西，我们可以把序列所有数加起来，然后它的 m 次幂显然包含了所有可能序列的积。也就是说，转化一下我们钦定序列里面有这个数，也就是讲式子可以变成：
m\sum_{i}a_i^{s+t}(\sum_ia_i^{t})^{m-1}
然后这个东西加入元素什么的都非常好维护，于是问题解决力！所以流程大概是：枚举 \gcd 后按照 L(a_i) 从大到小的顺序逐个加入集合，并记录后缀和，然后差分得到所有最小质因子的答案，求和即可。
注意区分欧拉反演和莫比乌斯反演！二者分别是：
n=\sum_{d\mid n}\varphi(d)\\
[n=1]=\sum_{d\mid n}\mu(d)
所以这个题用欧拉反演最方便，于是本题结束。
WC 2022 模拟赛 11
A. 闪烁之光
总结
还是比较简单的，可惜花费的时间比较多，关键在没有想到那个点上，不敢进一步细化问题。
做法
首先我们可以得到每个点的到一个集合内的点的连边个数，即两次第一次询问整个集合加上那个点，第二次只询问那个集合，两次作差即可。那么对于每个点我们就转化成了有一个序列，序列有些位置有元素，每次可以询问任意位置元素个数和，保证所有序列元素个数是 m ，让你得到所有元素位置。则可以考虑类似线段树的方法，每次二分看下左右有没有点，有的话递归继续问，这样总询问次数就是 O(m\log n) 的。
B. 三人博弈
一个比较玄学的博弈？什么时候搞搞博弈相关的东西再看看吧。
C. 开关
总结
发挥还算稳定，考场上想出一个非正解但能卡过去的做法，可惜后来改假了（虽然得分更高），也许是精力问题后半段有点迷糊。还是要把思考时间放在前半场，后半场容易失误。
另外类似问题建图一定要用主席树，直接线段树可能会导致多加边。树上考虑到某个点一定距离点的问题时记得点分治。
做法
O(n\log^2 n) 做法考场上想出来的，首先这题肯定要是个 2-SAT 优化建图。考虑这种问题用点分治，然后对于其每一个分治点，我们显然要从每棵子树开始，考虑其它子树的贡献，那么就拆成前后缀主席树的拼接，然后分别主席树优化即可。
注意 2-SAT 问题经常一个限制是两条边的，正逆都要考虑，那么到了这个题上就用两棵维护正向边四棵维护反向边即可，常数有点大。在点数边数很多的题目上，如果被卡常尝试把 vector 换成链式前向星。
O(n\log n) 做法现在还没明白是长链剖分的何种性质导致了这个做法。
首先根据上述做法，无论正逆限制我们只要处理一次即可，在这个基础上对树进行长链剖分，从最长的链开始，从下向上处理所有的答案，遇到轻边就递归进入处理，与下面的信息合并，并加入主席树中并继续向上考虑。这样每对可以产生贡献的位置都会从上到下考虑一次并且每个节点的信息只会在链顶处被合并一次，即总复杂度就是 O(n\log n) 的。
WC 2022 模拟赛 12
A. 木棍
总结
没什么好说的，因为判断失误导致值域只有 10^7 还在那开 map 然后直接 TLE。但好处是改成数组之后因为一大堆剪枝直接冲到了最优解。
枚举情况时考虑最容易被确定的去枚举，带有一定的 meet in the middle 的思想。
做法
很多都写了容斥，即要考虑重复的情况，实际上不必要。因为对于两根和三根相同的情况，都把长度离散化然后从小到大考虑。动态维护一个取两个得到某个值的方案数，假设取的是 i,j 那么保证 i\leq j 。然后对于三根相同的，在考虑到第 i 个长度时先不更新前面维护的那个，称作 f ，先枚举后面的取三个一样的，再看 f 中能不能找到和当前这个直接匹配的更新答案，同时考虑当前长度取两根和取三根。对于两根相同的，可以共用同一个 f ，然后考虑到当前值时，枚举前面的，假设分别是 i,j 然后看下后面有没有长度等于 i+j 的，如果有就分别用 i,j 各取两根或者另外两根拼成 i+j 来更新答案。不难证明这样计算是不重不漏的，就不需要考虑去重。
B. 己酸集合
处处透露着玄学气息的一道题。
首先这个 n\leq 3\times 10^4 时间还给了 8s 看起来是想让我们写 bitset，然后看这个三角形实际上是三个半平面，那么我们可以分别算出三个半平面的 bitset 然后与起来就是最终的答案。
那考虑我们可以将询问离线，然后对所有半平面进行极角排序，最终形成的效果是从 0 转到 2\pi 。然后可以以特殊的方式对三个半平面的向量定向使得一定是向量左侧的点被取到。
然后我们就可以开始转向量了。因为最终的半平面一定可以由过原点的斜率相同的向量平移过去，因此我们考虑将旋转的那个向量作为横轴，对所有点的纵坐标排序。那就产生了 O(n^2) 个大小关系改变时刻，具体来讲两个点顺序交换当且仅当两点形成的向量和当前向量夹角 \sin 的正负性改变，这里可以用叉积处理。
但直接做 O(n^2) 还是吃不消，考虑我们分块然后把答案加起来，假设块长为 B 那么总复杂度为 O(nB\log n+\frac{nm\log n}{B}+\frac{nm}{w}) ，然后块长取 O(\sqrt m) 最优，于是本题结束。一些小细节：
对于顺序交换类的问题，可能比较的那个关键字相同的情况下有不止一对需要交换的，这样就需要对别的关键字也排序可以保证交换的连续性否则会炸掉。
C. 斐波那契
做法
考虑如何简化问题，首先序列长度为 n 且 0,1 个数分别为 x,y ，那么显然有 x=n-y ，那么就可以把每个序列的贡献 x^ay^b 转化为 \sum_{i=0}^a{a\choose i}n^{a-i}(-1)^iy^{b+i} 。那么进一步简化问题，我们只需要求出所有合法序列的 y^i(i\in[b,a+b]) 之和即可得到最终的答案。那么考虑如何解决这个问题，我们设 F_i=\sum_A y_A^i 同时最终的式子转化为了 \sum_{i=0}^a{a\choose i}n^{a-i}(-1)^i F_{i+b} 。
也就是我们现在要求 F_i ，考虑拆幂，根据第二类斯特林数有 x^n=\sum_{i=0}^nS(n,i)x^{\underline{i}} ，则有：
\begin{aligned}
F_i&=\sum_A\sum_{j=0}^i S(i,j)y_A^{\underline{j}}\\
&=\sum_A\sum_{j=0}^iS(i,j){y_A\choose j}j!
\end{aligned}
那么我们考虑设 G_j=\sum_A{y_A\choose j} 则有：
F_i=\sum_{j=0}^iS(i,j)j!G_j
那么也就是说我们如果预处理出了 G 的值便可以快速求出 F 便可以求出最终的答案，考虑如何求 G_j 。我们可以转化为组合意义，即 G_j 表示对于所有的合法序列里面的 1 ，从中取出 j 个的方案数。可以考虑分治，即我们判断两个区间是否可以合并只需要管两个区间相交的地方是否都是 1 即可。那么我们设 f_{n,c,X,Y} 表示长度为 n 的串，已经取了 c 个且开头结尾的元素分别为 X,Y 的方案数，那么对于两个区间的合并即 f_{n+m,x+y,X_0,Y_1}=f_{n,x,X_0,Y_0}\times f_{m,y,X_1,Y_1}(Y_0=0\or X_1=0) 。于是可以分治去求，最终的 G_i=\sum_{X=0}^1\sum_{Y=0}^1f_{n,i,X,Y} 。于是总复杂度 O((a+b)^2\log n) 。
我高声膜拜 tzc
WC 2022 模拟赛 13
A. 最大子段和
总结
注意类似的反向思考问题的思路，可惜实际做题中不好想到，只能多注意从答案来处理贡献这一点吧。
然后注意线段树处理多段最大子段和的方式，以及可反悔贪心。学习过程主要是见过类似套路才能想着去接近。
做法
比较复杂，只记大体思路。
首先对于最大子段和，我们可以转化成前缀和的形式，于是我们就可以快速地二分我们最终的最大子段和看需要的操作次数来得到答案，这提醒了我们答案具有单调性且要从答案考虑贡献。
我们设 f(x) 表示最大子段和达到 x 的最小步数，能够转化为 \max_{i=1}^n t_i-ix ，其中 t_i 表示把序列划分为 i 个非空段能得到的最大的和，这就不难看出对于每一段减去 x 之后，哪些剩得最多那么对应的操作次数就是那个，也就是考虑对多少段进行操作。
那么这个问题便可以解决，即我们可以用线段树维护，每次查询全局最大子段和，然后把这一段取反接着继续取即可，其实就是个可反悔贪心，取反之后再取就是不取，并且如果取了被取反的只能是分开了两段，那么段数会多 1 可以证明答案的正确性。
那么我们求出所有 t 之后，如果我们对于所有 i 把图像画出来，那么就是个凸包，那么最终的凸包其实就是 f 函数。这个求出来了之后我们考虑对于一个 g(x) 其实就是查纵坐标为 x 的下面第一个在凸包上的整点，这样就可以直接求了，细节比较多。
B. 文本编辑器
总结
高声膜拜 yyh
这题一开始只能想是一个树形结构，但没想到把合法和不合法的分开连链。一部分原因主要是去看 T3 去了没有想太多，可能是困了？下次注意分配时间。
做法
首先可以证明一个东西，即当某个操作可以被撤销时，它到最终的修改操作上所有的状态都是可以被对应操作的，具体可以考虑单调栈证明，当时只是发现但并没有证明。
具体来讲，我们考虑维护一些链，保证这些链上活动状态都是相同的，那么最简单的形态就是隔一个连一个交替形成两条链，这种只要保证每个加进来的都是撤销的最后一个就能达到。
但考虑其它情况，首先明确在最后一个加进来的点所在的链上的点都是活动状态，于是每次再新加入一个点就在上一个点的链上查询可行的点，找到之后我们实际上是要撤销找到的那个点，那么具体连哪个点呢？又是奇怪的小结论，即应该连上撤销的点上一个加进来的点。具体来说我们实际上就是在找和最后加进来的点最后的状态相同的点，那么如何考虑这个东西？
如果找到的哪个点撤销了它上一个点那么显然是的。否则它就去撤销前面的点了，但因为找到的那个点撤销的点一定和前面那个点是一条链上的，故其前面的那个点一定符合要求，得证。
于是主席树维护链上对应区间最小级别然后主席树上二分即可。
C. 保龄球
总结
爆零球
耗费了大部分时间，不过最后单车变摩托。
还是说不要为了图某些方便而去忽略思考某些问题吧。比如这里反着做肯定代码好写复杂度也低，但因为题里给了前缀和就不考虑怎么转化成后缀这种行为是非常不可取的。
做法
太长了不能细说，反着做不怎么用想显然是个 DP，但考虑前缀转后缀实际上就是在考虑每个位置能放的范围罢了。
写了正着做法，不过非常复杂。具体来讲你要考虑当前的对前一位的贡献，如果上一位是全倒了那么还得考虑上上位，于是全都记录一下然后超级大讨论，码量大常数也大，超级垃圾的做法。
WC 2022 模拟赛 14
A. 托卡塔
总结
难得遇到几乎是原题的题。
做法
考虑之前做过要求只有一段，现在改成维护树上连通块数，那么因为 m\leq 7 所以用线段树维护编号序列到当前位置的后缀的连通块数，然后维护前 m 小值即可。
B. 尼伯龙根
总结
思路与正解比较接近，不过还是没有很好地考虑“贡献”的思想，但还是有一定程度上受到了别人说这是个 SAM 板子题的影响，确实可以 SAM 不过 SA 也不错。现在没有很能掌握 SAM 的情况下多用 SA 吧，有时间再看看 SAM。
以及类似的均摊思路“每个点只贡献一次”，并且具有单调性的问题要注意。
注意注意注意区间信息要转成点的信息方便处理。
做法
首先肯定按照区间长度从大到小排序，然后每次考虑当前区间是否被前面考虑过的区间包含。具体来讲，对于这个“贡献”，我们可以发现，对于每一个区间，对于更小的区间的贡献，因为我们按照区间长度排好了序，那么可行的左端点一定是一段区间，并且这段区间会不断增长。
那么我们考虑从序列里面不断加点，直到加完整个序列。然后每次询问只要看下在 SA 上当前串出现的区间是否有被删的点即可。因为我们是一个一个删的所以可以直接对应到 rk 来更新。于是这题就做完了。
C. 先人祭
很抽象的一个题，倒是可以练练圆方树什么的，有点毒瘤细节多，暂时不是很想补总结。
WC 2022 模拟赛 15
A. 矩形
补了补了！似乎可做！tzc 太强了！
考虑一波容斥，即我们用所有的三元组个数 {n\choose 3} 来减去交一对两对三对的就是最终的答案，其实看部分分就能发现他在启示我们这么做 。
首先考虑一对两对相交的答案，简单画一下发现这两种情况，都能找到两个矩形满足其和另两个一个有交一个没有交。这样我们就可以找到所有满足这样条件的组合就是答案。
那考虑怎么去求这种三元组，其实就是找一个矩形，找一个和它交的，然后再找一个不交的，即 d_i*(n-1-d_i) （d_i 表示和 i 有交的矩形个数）就能求出这个矩形的贡献，那考虑怎么求这个度数。
考虑容斥，能够发现不交的条件还是很好找的 ，即对于 i,j 不交只要满足 l_i>r_j,r_i<l_j,u_i<d_j,u_j<d_i 之一即可，那这个东西直接拿树状数组查一下就可以了，但我们发现会重复计算，即是完全在每个矩形四个角范围内的那些矩形，这个扫描线正反两次就做好了，这样我们就求出了交一对两对的答案。
B. 均分
总结
毒瘤构造，不知道咋搞的，最后也没搞清楚。不知道写构造题总结有啥用
C. 字符串
总结
毒瘤讨论+找规律。规律不好找，还得打表，垃圾题。
WC 2022 模拟赛 16
A. 1004535809 与 1004535809
总结
比赛时快写出来的题，不知道咋说，分析下可能是后半场太困了（雾）
做法
首先不能直接建出图，可以把问题转化成两棵树，两个点在树上跑，求跑 k 步以内两个点都回到原处的方案数。跑一步指任意一棵树上的关键点移动一步。
我们发现可以把两棵树分开考虑求出答案后直接 O(k^2) 卷积即可。
那么考虑这是个树上的 DP，我们设状态 f_{i,u,v} 表示从 u 点开始，走 i 步，不经过 v 的子树回到 u 点的方案数，然后这个东西就转移就可以了，然后设个 g_{u,i} 表示从 u 点开始走 i 步回到原点的方案数，具体转移就用 f 做一个类似背包的操作即可。
正常直接做会常数过大跑 8s 直接 TLE。然后我们发现可行的状态实际上就是树上一条边，于是用链式前向星，一条边就可以表示一个状态然后就可以过掉了。
B. 6002TE 与颜料
总结
主要还是没观察出应有的性质，即全都被覆盖这个是假的，只要分析出了这点就能得知答案下界是 2\max(n,m)+2 。实际上正常思路是有确定一个点或者位置一定不被上色，但因为这个下界导致这个位置即横纵轴中点之一。
注意单调栈一般维护的是最值覆盖区间方便线段树区间修改 。
做法
知道了这个之后，我们从一维枚举两个端点，然后中间的点全都贡献到另一维。因为要保证另一维过中点，所以问题就变得简单了，即每个在另一维对区域的贡献都可以固定下来，于是可以单调栈优化，配合线段树即可。
C. PolarSea 与遗忘的森林
网络流类问题很多时候可以通过数据范围判断，当然这不一定是全部的依据，本题是一个很类似匹配的形式，也可以从这一点上考虑网络流做法。
根据前几天学来的，考虑决策规范化 ，对于每一个点的限制，只要保证存在大小对应的环且环上有长度对应的链即可。即初始形态都是一些环连一些链的形式，剩下的非环点就随便连就可以了。
也就是说，我们只要首先处理出哪些点构成了哪些环，剩下的连成链一定是最优的 。
首先我们考虑环，把点分成两类，一类是一定在环上的 h_i=0 ，另一类是可能在环上的 h_i=-1 。我们可以列出限制 ：
对于每一个出现过的 l_i 都至少有一个环满足要求。
当然还有一些限制我们没考虑，即环的数量是越少越好的，所以想要求出某个大小的环的数量只要看一定是对应大小环点的点有多少个然后再补全最后一个环一定是最优的。
这样我们可以对所有的环建点，每个点都向自己可以放的环连边，看能不能跑到满流即可。
WC 2022 模拟赛 17
A. 点分治
总结
浪费时间有点多，要好好读题，不要因为某个题意和自己做过的题差不多就把问题复杂化，看清楚题意再做。
做法
大水题，甚至可以改成距离小于等于 d 的，直接搞组合数前缀和。但这个更水一点，我们发现每个数为 1 的位置的数量即为其深度，并且每个点之下对应深度的点的个数是个组合数，然后简单容斥即可。
B. 博弈
总结
遇到这种细节巨大多的题，不一定要先去打，可以先读一下下个题判断一下性价比，实在不行打完暴力再来开大题。
C. 最优化
总结
最大的失败在于没有在这上花时间，都在打 T2。明明是一道见过的套路却给放弃了。
做法
首先最难处理的就是我们不知道每个点要经过几次，为了解决这个问题，数据范围不大并且看起来很像网络流，于是传递闭包，这样我们强行要求每个点只经过一次。
然后我们需要在图上找到若干条路径。我们发现即每个没有被路径覆盖的点或者不成环的链都会产生 C 的代价。我们发现最终这部分贡献恰好是 n 减去边数。那么就直接费用流跑匹配即可，跑最小链覆盖即可。
WC 2022 模拟赛 18
A. 最短路
总结
细节好多好多。刚开始分析得比较顺利，后面因为讨论能力不行寄了，然后直接写一波 DP 然后加一些特判卡过 85 分，其实还好。
对于这种大讨论题，而且能分析出最后的答案肯定和组合数或者什么数列有关但是细节搞不好的可以考虑打表找规律，能降很多思维难度。
做法
考虑简化问题，我们求出四条路径的答案然后合并，具体来讲即是从起点的 0,1 到终点的 2,3 。然后我们转化一下问题，相当于我们在走一个网格图，每次移动直走代价为 2 方案数翻倍，转弯代价为 1 方案数不变。那么其实就变成了求起点到终点，在固定第一步方向的情况下的最短路径和方案数。
我们把向下和向右分别看成 0,1 那么问题转化成求有一个 x+y 长度的 0,1 序列有 x 个 0 ，求最多的 01 交替数和对应的方案数。然后可以 DP，特判 x=y 的话就能拿到很多分。
然后我们发现这个显然跟组合数有关，于是打表找规律特判即可。
B. 集合
总结
线性基结合小技巧。小技巧还是好好积累。
做法
这个技巧即，可以证明对于最优答案的代价，一定存在一个 k 使得其 \sum b+k\sum c 也是最小的。考虑证明，如果我们给每个方案看成一个点 (\sum b,\sum c) ，假设最优答案在双曲线 xy=ans 上，那么过最优答案点的切线显然可以使其它所有点都在切线上，于是得证。
这样我们就可以根据 k 来修改每个点的价值，并且可以找到点之间相对关系改变的 k ，这种改变共有 O(n^2) 个。我们现在把改变后的价值看成总价值，那么要构造线性基显然从小到大贪心扫是最优的，于是暴力建线性基，每次交换重构线性基即可。
C. 字符串
咕，过段时间补。
WC 2022 模拟赛 19
A. 刀言刀语
总结
难得流畅的思路，转化得也很好，可能做得快原因在于分析了性质吧。看到任何一种奇怪的生成方式，那么它自有它的特殊的性质，不能和平时的做法一概而论，否则容易走进旧题的圈套里。
做法
问题里面的撤销操作可以直接变成在任意合法位置去掉或者套上括号，那么只要能够同时维护加入和删除即可。
根据以前的做题经验，并列的 n 个括号对答案的贡献是 \frac{n(n-1)}{2} ，但这对问题的解决帮助不大。
然后考虑观察这个加括号的方式，发现所有在外面套的括号，左侧括号都是在一起的，而加括号只能在最右侧加，那么就可以问题转化为每次操作在序列最后放一个小球或者挡板，然后一段连续的小球贡献就是上述贡献，然后用树状数组维护区间小球数，然后用 set 存挡板位置就可以了。
B. 刀妙构造
总结
赛时没有看这道题，不过赛后想想似乎不是很难，不知道能不能独立想到这个错排的证明方式。
注重归纳法在证明中的运用，包括博弈论类问题也是，而且不仅可以正着归纳也可以反向归纳。
做法
关于是否有解，如果不去分析，我们可以知道对于一个左右端点已经固定的区间内部，其中元素是错排是这个区间有解的必要条件，但实际上是充要条件，这就需要很神奇的证明。
考虑当前区间，我们假设内部元素就是错排，考虑如何归位最左侧的元素，如果归位之后仍然是错排那么就可以通过归纳证明其充分性。首先朴素地想肯定是一个一个往左侧挪，但如果遇到 a_x=x+1 这种如果挪的话可能导致区间被拆开不一定能保证错排的性质，考虑我们其实遇到这种情况可以先交换 a_{x-1} 和 a_x ，同时如果 a_{x-1}=x 也是这种情况那就接着往前找直到不满足这个性质，然后交换。当然如果整个区间都满足这种性质那么直接一趟交换过去是没什么问题的。然后就可以归位第一个元素并且保证区间仍然是错排，于是就连着证明带构造把这个问题解决了。
C. 刀压电线
总结
第一题做得很快，感觉直接开 T3 是个不错的策略，因为我真是不太会做构造题（雾）。但最大的失误在于走进了思考误区，没有成功简化问题模型。
最大的难点在于如何找到可用的边，而已经找到了多源 BFS 然后取临界点这个做法，但脑抽多源 BFS 居然开了 p 个队列……可能是迷糊了，以后干脆上来开 T3 防止犯困。
做法
首先这种东西看起来就很像 Kruskal 重构树，其实不建重构树也完全行得通，因为我们需要的并不是重构树上的子树信息，但建树自然会方便。
那么现在最大的问题就是如何求出最小生成树。我们发现，无论如何路径一定是顺道经过尽可能多的房子是最优的，那么我们考虑对网格上每个点求一下到这个点最近的房子，然后在那些覆盖区域有交界的房子之间连边即可，可以证明这样边数不会很多是 O(nm) 的，关键在于这类问题的转化，似乎也是无权网格问题的特例？只能这样想了。
然后就直接跑 Krukal 重构树就可以了。yyh 说这个题可以整体二分？听起来比较可行，但现在我的感觉是瓶颈在于如何建树，建出来了基本就随便做了。
WC 2022 模拟赛 20
A. 连通图
总结
太屑了。
怀疑是考试时太困了，想了大半不想想了，太离谱了。
做法
构造题，首先缩点，然后我们的目的就是让所有没有入度或者出度的点相互可达，首先可以连成一个环，但这有可能不是最优解，因为有些原图中的路径也可以参与到最终的环中。考虑如何利用这些路径。
我们可以把每对可以相互到达的无入度和无出度点配对然后首尾相连，这样还会剩下一些点，然后可以证明这些点随便配对就可以，最后还剩一些点再随便按照某种方式连到环上就可以了。
B. Heavy Command Cruiser
总结
考试被第一题拖住了没有细想这个题，有部分原因是模型转化出错，考试时只看出了每个叶子节点可以代表一个区域，但发现如果这样表示又难写又没办法转化，而没有即时进行另外的转化。DP 使用不够熟练，性质分析不到位。
总之是道好题，可惜没能力做。
做法
发现一个性质即两点之间最短路经过的所有区域，都至少接触了两点间树上路径上的一条边。
那么我们便可以把信息压缩到树上的最短路径上，即状态可以表示为在哪个边的哪一侧走到哪条边的哪一侧，然后可以用树上倍增类似的方式进行转移，毕竟信息可以合并。然后考虑建虚树压缩每条边，取最小权值即可。
然后每次询问就是在树上查询，问题不大。尝试卡卡吧，毕竟真的不想学猫树什么的，考试估计也不会考，大概压缩下 \log 估计能跑得快些吧。
刚才遗漏了整道题最关键最核心的所在。
即最开始那个 DP 并不是简单地建虚树，而是实实在在求出一条边一侧到另一侧的最短路，这就考虑到另一侧是从上面过还是从下面过，于是考虑从下到上和从上到下进行两次 DP，并且把权值改为从一侧到另一侧的最小代价。
考虑先从下向上，每个点此时的 w 表示走自己子树中的路径和自己最后从一侧到另一侧的最小代价，这个不难求，只要把每个点所有子节点的 w 都加起来和走自己的取 \min 即可。
然后考虑从上向下，此时每个点的 w 表示既经过上面也经过下面从一侧到另一侧的最小代价，而我们现在可用的有：父节点上下均可的答案，并列节点向下的答案，那么显然如果考虑向上即是走一圈并列节点的向下然后经过父节点的上下均可。于是我们就成功更新了答案。
这样就能保证最短路径上的每一个区域都至少覆盖了两点之间最短路的边之一，就都可以被最短路边的某侧表示，然后再来一个 DP，用倍增处理即可。
具体地讲这个 DP，我们设 f_{u,i,0/1,0/1} 表示从 u 的父边的左/右侧到 u 的 2^i 级祖先父边的左/右侧的最小代价，然后用类似 Floyd 的方式转移即可，然后细节有点多要注意。
C. Sword of Annihilation
WC 2022 模拟赛 21
A. 上升序列
不算难题可惜没想到。
观察限制看得出来很可能是先二分一次然后操作操作啥的。
对于这类题的性质，有些东西是“显然没用的”，比如讲这个题里面大于 2A 的所有元素。那即便是这种“显然没用”的东西，也很有可能能给我们一定的启发。正是这个我们才有可能意识到我们要按照值域给这些元素划分，不同值域内的元素性质不同并且值域的分界点都可以通过二分找到。
因为范围在 [A,2A] 内的元素最多取一个，考虑取不取。取得话取最小的并让剩下的尽量小一定最优。不取的话即是在 [0,A] 中取 k 个，考虑怎么办。
首先前面的上下界分别是后 k 个之和和前 k 个之和。考虑从下界不断增大？假设你选连续段你不知道到哪去选即便能二分到想要的位置但代价太大根本做不了。换个思路，我们给最小的 k 个和最大的 k 个从小到大排起来，每次取一段连续区间。这样有什么好处？每次移动区间改变量一定不超过 A ，并且正好从值域下界移到了值域上界 。这就保证了统计没有漏，因为不存在一下跨过去的情况，并且值域全覆盖，有这么多优秀的性质，自然……
B. 服务器
做明白了属于是。
无脑做法直接点分治配合树状数组。但复杂度是 O(q\log^2 n) 的，整解是复杂度 O(n\log n) 的线段树合并。
首先这个限制就非常像线段树合并，它确实是。而且考虑线段树合并是可持久化的，即每次合并都建新点就可以。其实实在不行离线一下完全没问题。然后就完了？
C. 守卫
WC 2022 模拟赛 22
A. UTF-8
比较垃圾的题，毫无区分度全员 AC，还是个大讨论，问题我调 UB 还调了一个小时……人麻了。
B. Y 星人
？？
也许是头疼？想得很乱。
对于这种范围巨大的题，首先可以 DP 来，但纯 DP 一分都拿不到，但思路是从纯 DP 上得到的，故题是垃圾题，但我更垃圾，没有发现这一点。
首先既然不管怎么设，怎么转移都得不到分，那么就从最暴力的方式开始，我们直接设 f_{x,y} 表示到达 (x,y) 处的最小代价。于是因为必然一次走一步，故有：
f_{x,y}=\min(f_{x-1,y}+c_y,f_{x,y-1}+x^2)
但这个式子我们能得到什么吗？并没有。首先这个式子无法直接转移，值域开得十分有毒，但我们发现有毒的那一维，其贡献直接给到了 x^2 ，这意味着我们需要去思考其函数的性质 。那函数肯定不能是二元的，为了方便思考我们考虑确定其中一维将另一维视为自变量 开始讨论。
也许还不能看出确定哪一维比较靠谱，先接着想然后复盘。题解中给出的是确定同一个 y 作为一个函数。其实也可以想我们可以一个一个考虑函数间的关系，但对于同一个函数内部我们就可以不一个一个处理。
还是太迷惑了……代码也搞得非常迷惑，简单写下其中流露出的思想。除了上面已经总结的，还有对这类问题我们可以看成是数据结构题，如此一来我们可以把每次更新拆成几个可能比较好处理的操作然后依次做。而且还要想清楚每个操作的本质。
对于最终的做法， 有一部分是考场上想到的，即对于两列，如果考虑在左侧列向下一段然后直接向右走到另一列然后接着向下，那么代价关于位置的函数是二次的，我们显然要找最小值。很有趣地，我们发现最小值位置和起止点的 x 无关。那要是这个极值点根本走不到说明什么？走不到那一定是直接向右走或者走到最下面再向右。
思考第一种情况，那么这一列完全不需要作为一个转折点存在。第二种情况，emmmm，怎么说？只能说没必要走到那里去，绕过去还不优，所以如果最优点走不到这一列就不用存。
考虑最优点必须单调递增，于是单调栈（不明不白地），过段时间慢慢补……
C. 语言学
部分分很多，最终解法也不止一个，是很好的字符串题。
border 有个优秀的性质即如果给其看成一对一对的，则其中之一一定是一段前缀，在处理前后缀问题上有奇效。
Subtask 5
憨批一个，关键在于如何判断某一个 T 的前缀是否是一个 S 的后缀，这个直接字符串哈希就可以了啊。
然后就可以进行标记，我们对与之相匹配的后缀标记一下，然后对所有的 T 串反向建 AC 自动机，那么每个点的贡献即是在 AC 自动机 Fail 链上不同的颜色数，这个东西可以直接建 Fail 树然后一次 DFS 求出。
关于这个一次 DFS 只要记录当前每种颜色的出现次数然后动态统计即可，复杂度 O(n\sum |T|) ，可以得到 35 到 45 分。
Subtask 6
czx 做法
具体来说，我们需要解决的问题之一即我们考虑一个 T 的所有划分位置，其两两前缀之间在 Trie 上的转移并没有什么转移边。因此考虑如何优化这个过程。很神奇地，可以直接用倍增配合哈希跳重儿子，这样每次复杂度是 O(\log^2n) 的。然后可以看出我们对于每一个串 T 其所有位置的贡献我们要取并，而且是矩形并。这样最后做一次扫描线就可以了。
喜提最劣解。
WC 2022 模拟赛 23
A. 小b爱取模
序列类问题，如果是固定序列看性质类问题，可以考虑转前缀和然后转点与点之间的关系 。如果是对序列连续段修改，可以考虑转化成差分然后每次修改两个点 。二者的实例即某些莫队、去年 NOIP T3。
这个题很重要的性质是操作顺序不产生影响。当我们转化成差分后，每次操作就变成了在两个点上操作。那如果我们记原序列为 a ，差分序列为 b ，答案序列为 c （即每个点被加了多少），那么这个 c 天然具有合并操作的功能 。
并且转了差分后直接就能把问题转化为把 b 的每个位置转化为 0 ，并且对其的修改都是单点的，所以难度降低很多。同时思考 c 序列的性质，即一个 c 序列合法当且仅当任意前缀和大于等于 0 ，而每个 c 序列的操作次数即所有正数的和。
首先构造初始序列，假设每次操作右端点都是 n ，这样实际上就是一个一个把所有的 b 改成 0 。然后想办法减小答案，我们可以发现显然是让一些 c 变成负数。因为 b 序列是模意义下的，所以把任意一个 c 改成 c+tk(t\in\Z) 然后保证每个前缀和非负一定是可行的。
于是操作流程就变成了找到一些 c 将其减去 k ，最后看能减去多少的 c 。显然每个 c<k 那么减去一个 k 对前缀和的影响同时也是最优的。
B.XorSum
我是傻逼吧，彻头彻尾的傻逼吧。
最大值最小却 TMD 不知道二分答案。
对“最大值最小”类问题可以二分答案处理。
注意 OI 问题中统一处理的“顺序性”。
接下来我们考虑我们二分的答案 v ，假设我们知道最终的答案里面每一位一共有多少个 1 ，那么我们 从大到小分配它们 ，显然分配过程中我们可以确定一些数一定小于 m ，这是因为我们是从大到小考虑的，如果高位更小那么低位不管怎么放最终都是小于 m 的。然后考虑如何分配，显然是先尽量分配给那些已经小于 v 的然后再分给剩下的。
考虑如何得到每一位有多少个 1 。我们设 b_i 表示最终答案第 i 位有多少个 1 。先构造初始解，首先要根据异或保证每一位的奇偶性，然后每一位再根据 s-x 的更高一位决定是什么。这样每一位的个数最多是 3 并且同时满足了和和奇偶性。那么我们对其进行变换，即我们可以使 b_i-=2 然后使 b_{i-1}+=4 而仍然满足条件。
考虑 DP，我们设 f_{i,j} 表示从高到低考虑到了第 i 位，有多少个数高位等于 v ，此时到低位最少移过去多少。
考虑到高位向低位移很多不优，所以第二维只有 5 ，然后就完了？？
WC 2022 模拟赛 24
A. 塔
B. 排序
对于 OI 中看起来有“牵一发而动全身”性质的东西，通常处理思路是用 DP 将其问题规模缩小。但对于这种构造题有时候也可能是将操作“不完全运用”，即即便影响范围很大但我们仅仅着眼于一个位置。类似地，如之前那个给一些点
首先简单思考一下。观察这个操作，一个特点是能够将开头的元素移到序列的中部。我们可以先考虑一个一个归位第一个元素。然后我们就获得了一个复杂度为 O(n\log n) 的做法，大力卡卡常可以获得 80 分。
C. 树
WC 2022 模拟赛 25
A. 冒泡
转化没想到。
非常草，有一个大家看起来十分显然的转化死都想不到导致直接寄掉。
即，对于冒泡排序来讲扫描次数是每一个位置的数在前面比它大的数的个数取最大值。具体来讲怎么想到这个？比赛时最大的问题在于对着前头的向后这一点看了三个小时却没想到是后面的往前。
可以看出来每一次扫描，对于每一个前面有比自己更大的数的数，比它大的数都会减少一。于是问题就转化成了位置减去排名的最大值。
关于这个我们可以先全部离散化然后用值域线段树统计，每次修改某个位置的数，使得其排名变化，那么对于其它的位置的排名，被修改的一定是一段区间，然后就完了。
我是傻逼。
B. 猫或狗
看出来是 DDP 奈何不会写广义矩阵转移。
正常矩阵优化利用的是乘法对加法的分配律，即 a\times b+a\times c=a(b+c) ，而广义矩阵则是利用加法对 \min,\max 的分配律，即 \min(a+b,a+c)=a+\min(b,c) 。也就是讲，在广义的矩阵转移下，a\times b=c 的具体表达为 c_{i,j}=\min_k(a_{i,k}+b_{k,j}) ，然后就可以转移力！
具体来讲我们把状态设为每个点向上没有猫和没有狗两种状态，转移式子就很方便，然后树剖一下本题解决。
另外比较正统的方式是矩阵乘列向量貌似，以后都这么写好了。
C. 山体滑坡
两种做法。
LCT 解法
考虑这个一会加边一会删边就很像线段树分治。于是我们可以方便地处理掉时间这一维，只要保证操作可以撤销。
然后我们要处理序列维，即对于每一个询问的位置统一处理。我们可以考虑计算两两点对的贡献。即实际上对于序列的某个前缀都是一个图，那么考虑一对点何时在一个连通块里，实际上就是两点所有路径最大点编号的最小值，这就有点类似最小点权生成树，我们可以用 LCT 来维护顺便求出两点间路径最大点编号，这样每次连边不在一个集合直接连，否则查一下最大点编号看一下是否比当前更大，如果大就断掉然后连上当前的边并且改变贡献的位置即可。
实际上就是在考虑两个集合连接的最早时间。
总结：
看这种边“出现又消失”可以考虑用线段树分治，其好处是：无需考虑删边，只有撤销操作 。
另外同样是对贡献考虑，重点思路在于想到那个最小点权生成树的转化。具体地讲，思考时我们要先模拟一下，或是说用朴素的办法处理问题，然后思考哪一步可以使用某些数据结构来优化。
分块解法
做法就是按照修改时间分块。
然后考虑对于每一个询问拆成前后缀的贡献来考虑。明确流程，我们在处理一个块时，把存在的边分为覆盖了整个块的边和没有覆盖的边，同时我们要通过移动断点来加边同时来处理相应的询问。
即，假设我们处理前缀，从小到大枚举断点，并首先加上那些覆盖了整个区间的边。然后处理每一个询问，都要加上对应询问时刻那些没有覆盖的边，然后全部退掉。
因为区间内修改最多 O(\sqrt n) 个所以先全都加上然后全部退掉正确性是有保证的。不过这样复杂度好像卡到了 O(n\sqrt n\log n) ？但改变块长复杂度可以变为 O(\sqrt{n\log n}) 。就这样吧。
总结：
注意本题有两维限制 ，所以我们可以考虑对一维分块就可以很方便地枚举另外一维处理问题。
JSOI2022 模拟赛 1
哈哈爆零了（大雾），不应该花费太多时间在这个 T1 上即便做法能被一眼秒掉也写不出来。
B. 会考
没怎么思考，感觉考试时身子发虚。但是有一点可能产生了一个接近的思路？
考虑一定被涂黑的位置是如何产生的，首先比较显然即一个黑色的位置一定对应着某个极长的黑色连续段，否则可以通过对应的两个连续段分开导致这一块是白色。
那么考虑什么情况下这个位置会永远被对应的黑色连续段占据，即让这个黑色连续段尽量向前向后移动，最后两边的交即是一定是黑色的位置 。
既然我们知道黑色的位置一定是移到最前面和移到最后面的交，我们不妨只利用它求移到最前面后哪些位置是黑色的，当然这个也就是我们要的答案。想象一下，假设我们全部移到最左边后，右边还有 k 个格子是白色的，那么对于每一个极长的黑色连续段，其对应的一定是黑色的位置一定是其删去前 k 个后得到的，如果不超过 k 个就直接删完。
那么显然我们可以通过枚举 k 来判断可不可以，即对于一个 k 我们将每个黑色连续段前面补上 k 个(当然不能补超了，这个要提前判断)，然后对于一大段空白的位置，用 DP 判断并构造看是否能用一些 \leq k 的连续段填上，最后看能不能满足后面只留 k 个空位即可。
问题是 k 的值域可能是 O(n) 的，这个怎么办？
思考一下我们刚才是如何构造一个解的，我们会发现，如果我们在 k 的时候有一个解，那么 k-2 时也会存在一个解，其实就相当于每段白色长度都增加了 2 ，这个时候用一黑一白两个填上去就一定合法，所以只需要试一下 k\leq 3 是否有解即可。
C. 全过
看到这种某个和的组成方式，可以想生成函数 。（其实有点类似背包？）
解法
对于一个元素 a_t 的生成函数显然是：
\sum_{i=0}x^{ia_t}=\frac{1}{1-x^{a_t}}
那么对于 n 个元素一起考虑，其生成函数即：
F=\prod_{i=1}^n \frac{1}{1-x^{a_i}}
所以我们想知道某个数 v 有多少种方案能组合出来只要看 x^v 的系数即可。
（等等考试时的暴力好像是 h\leq 100 的那档，直接背包？？我好菜啊！）
但是这个东西是个分式，很不好求，于是考虑变换一下？（从来没见过，学习了）注意，对于等比数列求和，如果项数无限那么式子大概是 \frac{1}{1-x^{...}} ，而如果有限则是 \frac{1-x^{...}}{1-x{...}} （首项为 1 ），而如果是有限项我们是可以暴力求系数的，这里考虑设 w=\text{LCM}(a_1,a_2,...,a_n) ，那么转化一下会有：
\begin{aligned}
F&=(\frac{1}{1-x^w})^n\prod_{i=1}^n\frac{1-x^w}{1-x^{a_i}}\\
&=(\sum_{i=0}x^{iw})^n\prod_{i=1}^n (\sum_{j=0}^{\frac{w}{a_i}-1}x^{ja_i})
\end{aligned}
这样做的好处是，前面的形式同一，可以快速求出某一项的系数，而后面变成了有限项，而且因为数据范围的原因可以直接暴力多项式乘法。此时我们考虑一下前面那个每一项的系数，其中 x^{iw} 的系数，其实就用插板法，把 i 个相同的球放进 n 个桶，其实就是 {n+i-1\choose n-1} 。
那如果我们想要获取某一项的系数，只要把前后的卷积一下即可。我们设前面第 i 项为 q_i ，且 q_{iw}={n+i-1\choose n-1} 。后面的第 i 项为 p_i ，可以预处理，又设 G(k,r) 表示取 kw+r 个的方案数，有：
G(k,r)=\sum_{i=0}^{n-1} q_{(k-i)w}p_{iw+r}
关于为啥只枚举到 n-1 ？考虑 p 的最高次为 nw-\sum_{i=1}^na_i ，那么只枚举到 n 就足够了。
这样对于每个询问，枚举 r 然后二分，因为显然 r 固定的情况下，G(k,r) 关于 k 单调，因为可以 O(n) 快速求出 G(k,r) ，所以每一个 r 求一下取最小值即可。w 最大约是 1000 。
时间复杂度 O(qwn\log h) 。
JSOI(P)2022模拟赛5
送分题
AK吧
吼吼吼吼吼吼吼吼吼吼吼吼吼吼吼，看来贺题解的人不止我一个。
但是感觉对 WQS 二分理解还是很不完全。
首先一个小知识点，假设 a,b 是两个函数，并且都是上凸包，且此时我想生成一个 c 数组使得 c_n=\max_{i+j=n}a_i+b_j ，根据凸包的性质，我们像归并排序那样维护 i,j 两个指针，从小到大考虑 n ，到下一个 n 的时候看下哪个指针移动后值更大就贪心移动那一个，所以这种可以线性合并。
众所周知，区间选出 x 个子区间的最大和这个东西是一个上凸包。我们可以用线段树，每个区间维护一个数组，f(x,k) 表示 x 节点的区间，选 k 个区间的最大和，那么这是一个凸包！
但同时问题也来了，我怎么得到答案？总不能做背包吧，背包也不能合并啊。
对于这种“恰好选出 k 个”的问题，可以想到 WQS 二分来解决。首先显然如果我能把这一堆凸包合并起来，那最终也会是一个大凸包。但实际上我们并不需要合并，只需要分别在几段上面都做 WQS 二分就可以了。
JSOI(P)2022模拟赛8
Walk
也不知道考试时候在想什么，但这证明了部分分真的很重要。
刚开始真是一通乱想，但就是完全没有思路。后来看到那个 w\leq 100 的部分分，仔细想了一下出了个 O(nw) 的暴力，然后发现只要把没有用的东西去掉就是正解。
当不知道正解时，不要觉得部分分显然，好好想想说不定就出正解了。
想不出正解要留意部分分的提示性。
假期
主要是方向走错了，这个没有办法。
这个状态设得说怪也怪说不怪也不怪……只是一开始总是想左右合并……
实际上我们设状态 f_i 表示左端点为 i 时，能得到的最大价值。那么显然这个价值由左右端点唯一确定，并且感性理解可以得知这个东西有决策单调性。
于是转化为一个喜闻乐见得问题，分治做一下就可以了。
具体来讲失败主要在于很多东西重复考虑导致没有成功简化问题，比如最终我只需要管区间而不需要管左右分别怎么样类似的问题。
光明
长链剖分几乎是模板，学一下就可以了。
注意转移中有深度维的可以考虑长链剖分，尤其是复杂度看起来要线性的时候。
游戏
感觉第一种胜利条件不太可能实现，即给 Bob 逼到无路可走。因为无论选择什么位置，Bob 都可以选在 Alice 旁边，然后此时 Alice 只能往一个方向走，并且 Bob 就会跟上来使得这种情况重复出现。
有了这个依据，我们意识到胜利只有可能是因为 Alice 踩过了 k 个格子。那既然是 Alice 先选，考虑胜利条件实际上变成了：存在一个相同属性值的连通块长度为 l 且 \lceil \frac{l}{2}\rceil\geq k 。此时 Alice 一定可以选择走这个连通块，并且 Bob 不管怎么堵都无法堵死 Alice 并且 Alice 一定可以完成目标。
于是转化一下条件，只要存在一个长度大于等于 2k-1 的连通块就一定可以胜利。我们把原来的 2k-1 直接称作 k ，然后考虑求解这个问题。
可以使用容斥，求不存在长度大于等于 k 的连通块的方案数。对于“至少一个”的限制，可以反过来求“一个也没有”。
根据刚才的思路，设 f_{i} 表示考虑前 i 个位置，没有可行连通块的方案，于是有转移：
\left\{
\begin{array}\
f_i=1&i=0\\
f_i=mf_{i-1}&i<k\\
f_i=mf_{i-1}-m&i=k\\
f_i=mf_{i-1}-(m-1)f_{i-k}&i>k
\end{array}
\right.
当然这个式子还是写麻烦了。对于这种问题，除了我们可以容斥掉有一个连通块的情况，还可以直接枚举极长颜色段，于是 DP 式就是：
f_0=1\\
f_i=(m-1)\sum_{j=1}^{\min(i,k-1)}f_{i-j}\\
ans=\frac{m}{m-1}f_n
对于最后那个系数，我们可以看作普通的系数是为了防止和下一段颜色一样，但到了最后没有下一段，于是要除过去再乘一下。
然后首先对于 k 比较小的询问可以直接矩阵乘法，这里干脆设个阈值为 200 。
所以题解里写：“用生成函数来刻画解 2 的做法”，具体来讲是？
\frac{m}{m-1}[z^n]\sum_{t\geq 0}((m-1)\sum_{i=1}^{k-1}z^i)^t
看起来被 t 次幂的东西也是一个生成函数？其对应的数列是 \langle0,m-1,m-1,m-1,...\rangle ，考虑生成函数相乘相当于卷积，那么这个数列的生成函数实际上就对应了一次变换。
因为初始的生成函数是 F(z)=1 所以前面没有写。那考虑前面那个 \sum_{t\geq 0} 是做什么的，因为是加起来的所以排除依次变换的可能。
按照上面的递推式，我们设 G(z)=(m-1)\sum_{i=1}^{k-1}z^i 则有 F(z)=F(z)G(z) ，所以 F(z)=\frac{1}{1-G(z)} ，然后封闭形式转化，得到了 F(x)=\sum_{t\geq 0}(G(z))^t ，于是带进去就得证啦！
于是现在我们得到了正确的生成函数转化的式子。
焯，为什么题解是先得到了我认为是推出来这个式子的式子啊。
于是得到：
\begin{aligned}
F(z)&=\frac{1}{1-G(z)}\\
&=\frac{1}{1-(m-1)\frac{z^k-z}{z-1}}\\
&=\frac{z-1}{z-1-(m-1)(z^k-z)}\\
&=\frac{1}{1-(mz+(1-m)z^k)}-\frac{z}{1-(mz+(1-m)z^k)}
\end{aligned}
然后因为我们需要第 n 项的值，所以我们对着上式求出 [z^n]\frac{1}{1-(mz+(1-m)z^k)} 和 [z^{n-1}]\frac{1}{1-(mz+(1-m)z^k)} 然后系数合起来就是我们需要的答案，于是设 g(n)=[z^n]\frac{1}{1-(mz+(1-m)z^k)} 并尝试求解。
观察到这种形如 \frac{1}{1-x} 的式子可以转化开，于是有：
g(n)=[z^n]\sum_{t\geq 0}(mz+(1-m)z^k)^t
然后我们只需要求第 n 项的系数，观察到这个式子可以用二项式定理，于是进一步转化：
g(n)=[z^n]\sum_{t=0}\sum_{i=0}{t\choose i}m^{t-i}(1-m)^iz^{ki+t-i}
然后我们需要 ki+t-i=n 则 t=n+i-ki （因为考虑枚举 i 的话就不会有分数的问题），则式子转化：
g(n)=\sum_{i=0}{n+i-ki\choose i}(1-m)^im^{n-ki}
于是我们解决了这个问题！具体来讲我们考虑这个 i 要枚举到多少，即 n+i-ki=i\to n=ki ，也就是说这个算法的复杂度是 O(\frac{n\log n}{k}) ！
并且这个 \log n 的底数实际上是 p ！一般来讲会比以 2 为底快很多，虽然 p 搞成 2 也不是没有可能，但如此小的常数，直接暴力卢卡斯定理就可以了！
然后我们设阈值 k=200 的话，小于我们就矩乘，大了就用这个办法，然后问题解决力！
JSOI(P)2022模拟赛9
强制在线写挂又挂大分。
期望 100+100+30 挂成 50+60+30，干脆写离线得了（大雾）。
回合游戏
强制在线写挂了！看清到底需要异或什么。
开局猜了个结论没想到就直接对了。
既然这看起来是个数据结构题，那维护的东西肯定不能太复杂，于是考虑转化题意。
我们发现，如果我们给每个点一个权值，为这个点上所有边的边权和的一半，那么每个人操作时一定会选点权最大的点。
具体证明也不困难，即如果一条边两端都被同一个人选那么他就会恰好获得这条边的价值，如果是被不同的人选那么这条边不会对任何人产生贡献。于是发现这种贡献方式和直接做是一样的。
于是肯定先手取排序后奇数位置上的，后手取偶数位置上的，这个东西用值域线段树维护很方便，当然也可以平衡树。
中位数
wssb 强制在线又写挂了！记得加强制在线
首先看到中位数的问题，想到二分答案，具体来讲对这个题来讲，假设我们二分的答案为 x ，那么我们把 <x 的数设为 -1 剩下的设为 1 ，一段区间中位数 \geq x 的充要条件是这段区间和 \geq 0 。
于是我们二分答案时肯定要贪心让区间和最大这样我们能使中位数增大。但具体这个权值的修改，可以用主席树实现。我们最终一定会取 [b+1,c-1] 以及 [a,b] 的最大后缀和 [c,d] 的最大前缀，这个东西用线段树是好维护的，于是这个题就做完了。
七管荧光灯
算是对博弈论有一点基本的感觉了，考场上只知道 30 分的做法。
对于 30 分我们发现实际上如果 4 没有石子那么就剩下了一个环，然后尝试证明何时先手必胜或者必败。
我们会发现，当所有的灯管石子数一样时，先手必败。具体来讲，先手不可能再次把所有的灯管变得石子数一样，但是后手一定可以再次把石子数变一样。变到最后就全都是 0 然后先手就输掉了。
这对于博弈论的启发，其实也在 OI Wiki 上写了，那就是：
一个状态为必胜态当且仅当其后继状态中有至少一个必胜态。
一个状态为必败态当且仅当其后继状态全都是必胜态。
结合这两条就可以较好地进行博弈论问题的证明。
这个题满分的结论是：先手必败当且仅当 1,2,3 灯管石子数相同，5,6,7 灯管石子数相同，1,4,5 灯管石子数异或和为 0 。
然后具体实现主要考虑做这个异或和为 0 的就可以了，具体可以考虑数位 DP，把上下界变成一个差分然后只考虑上界即可。
JSOIP2022模拟赛10
写 Dijkstra 如果距离相等一定不要入队！
然后据说 T3 是个水题？不太敢做（大雾），只写了五十然后挂成 28。
第二题开场半小时写一个乱搞没想到得了 60，后来又花了两个小时写“正解”只多了十分。
期望 100+100+50 挂成 50+70+28，WSSB。
飞天鼠
首先可以想到，爬树操作在哪爬都一样，所以能不爬就不爬。然后，到达一个点，花费的时间越少到达的高度会越高。
具体来讲，如果之前没有向上爬树那么显然，花费的时间就是下降的高度。如果之前向上爬树，那么现在的高度肯定是 0 ，并且花费时间更多的话高度就一直是 0 ，所以结论成立。
于是把 Dijkstra 过程中的状态改为到达某个点的最短时间和最短时间到达的高度然后直接做就可以了。
Dijkstra 如果距离没有变小千万不要入队。
守卫
还是没有注意到部分分的提示性质，做得非常迷糊，不过数据也是相当的水…好吧总比开子任务然后爆零好。
本题一个 O(nm) 的做法是结合贪心来的，具体来讲，如果我们离散下来所有有可能有忍者的位置，然后去掉区间包含的情况，排序后能得到一些左端点单调递增，右端点也单调递增的区间。那如果我们想让这些符合要求，我们可以从左向右贪心，遇到一个没有放忍者的区间，放一个忍者到其右端点，显然这样是最优的因为这样一定能让这个忍者发挥最大的价值并且不放是不可以的。
然后考虑我们怎么确定一个位置必须放？只要看看如果钦定这个位置不放能不能有合法的解就可以了 。所以我们枚举每个位置然后贪心一次，就能获得一个 O(nm) 的做法。
然后考场上猜了一波结论，即一定放的位置一定会在正着反着贪心得过程中都被走到，然后……假了。看起来是输出的东西少了？也就是说还有别的情况我没有判到。但现在转变一下思路，从暴力部分分出发想一下。能不能一次干掉一大堆位置？正着反着贪心之后，会留下来一些位置，如果对这些位置暴力做可以吗？
当我正反贪心两次，两次都被放忍者的位置一定是必须放忍者的。感性理解一下，如果我正着贪心我是把忍者尽量向后放，反过来贪心是尽量向前放，那既然都放到一块了这个位置就非选不可了。
优秀子序列
一道随机化算法的题吧。
问题本质上是模意义下的等比数列。注意到一个特殊的限制即 k\geq \lceil\frac{n}{3}\rceil ，这意味着答案序列相邻元素不会相差太远。
具体来讲，我们随机两个位置作为相邻两项，然后向前向后扫得到一组答案。而答案序列长度至少是 k ，就保证了算法找到正确位置的概率很大。
具体如何证明它的正确性呢？我们考虑某次随机找到答案的条件：
两个元素都属于答案序列，概率为 \frac{1}{9} 。
两个元素是答案序列里面相邻的两个元素。
第二个不是非常直观，我们设一个 d ，然后我们让随即元素的距离在 [1,d) 里面随机，当然这个 d 不能设太大。
我们设 c_i 为答案序列相邻元素在原序列中下标差为 i 的元素对个数，我们只考虑 d 以内的，设答案序列相邻元素在原序列中距离 >d 的距离之和为 x ，那么能推出式子：
x+\sum_{i=1}^{d-1} ic_i\leq n-1
并且因为答案序列长度下界是 k 并且没有考虑的元素距离下界是 d ，所以有：
d(k-\sum_{i=1}^{d-1}c_i)\leq x
所以我们继续变换：
\begin{aligned}
d(k-\sum_{i=1}^{d-1}c_i)+\sum_{i=1}^{d-1}ic_i&\leq n-1\\
dk+1-n&\leq \sum_{i=1}^{d-1}(d-i)c_i
\end{aligned}
因为 1\leq d-i\leq d-1 ，所以继续变换：
\sum_{i=1}^{d-1}c_i\geq \frac{dk+1-n}{d-1}
我们给边界什么的放宽松一点，这个式子右边是 O(k-\frac{n}{d}) 的。这也大概是我们判断距离以内的相邻数对的数量级。会发现当我们 d 稍取大一点概率是非常高的，于是问题解决了。
最短路
单调的函数，且两个不同函数之间最多只有一个交点，想要维护单点函数最值也可以用李超树。
注意斜率优化的两种转化，一种是把转移状态看作点，另一种是看成线。但经过这题感觉其实看成线适用性更广一些？
打眼看好像可以暴力做，把距离什么的都记在边上，但实际上如果连一个菊花，一半入一半出的话复杂度就变成了 O(km^2) ，这个东西是无法接受的，但应该有一些启发。
题解是先讨论了 \text{cost}(x,y)=xy 的部分分，说是一眼斜率优化，可我不是很能“一眼”？看看具体怎么搞吧。
假设 x 边可以从 y 边转移，那么转移式子为 dis_x=\min_y\{dis_y+w_xw_y\} 。
然后这个题解里面写的斜率优化是反过来的，即我们给 y 看成一条直线而不是一个点，以 dis_y 为截距，w_y 为斜率，那么 dis_x 实际上就是横坐标为 w_x 时所有直线纵坐标的最小值。
画图可知，每一个 y 能更新的 w 范围是一段区间。而且多条直线要形成一个凸包。因为我们跑 Dijkstra 所以截距是不降的，那么此时只要让斜率单调递减就可以了，否则一定可以扔掉。
手模一下能想到，这里一个点可能不止经过一次，所以不可以先更新入边再更新出边。而是换一种思路，每一条边找到自己能更新的所有边，先更新能更新的第一条边，等这条边出队了再去更新下一条。因为出队的截距也是不降的，所以不会对答案产生影响。
然后考虑正解。说是本质没有变？所以还是考虑怎么去找决策的区间吧，而且是”像四边形不等式优化那样“？好奇怪。
！对，四边形不等式优化指的是决策点单调。那如果我按照 w_x 排序之后，对于某一个 y 我都可以去更新一下它可以更新的区间。因为不管 cost 是如何计算的，出队的点，如果看成一条线，那么它们的共同特征是，出队越晚的线截距越小，然后我们要取变化率尽量低的。
我们一定可以根据各出边的 w 来决定每一条入边可以更新哪些边。具体来讲，我们把每一条入边对应的函数看成一个奇怪的函数，这个函数显然是单调递增的，然后就可以做了。
比较好的写法是用李超树维护每个函数。因为这些函数都有优秀的性质，即函数值单调递增，导数单调递增，且两个不同函数导数始终是其一更大，不可能有两个交点。
并且对于起始点的处理，我们只要向 1 连一条权值为 0 的虚边就可以了。不要刚开始直接把 1 的所有出边入队，因为那样有可能破坏 w 从小到大处理的性质，除非重载运算符的时候考虑上。考虑了重载运算符还是有锅……不过还剩了点分，这个不用太追究……不过居然能过去全部的大样例，什么时候大样例强度能高一点啊。
最后，对于李超树的做法，我们依次加入一个点的每一条边，先按 w 从小到大排序，上一条边出队下一条边再进行各种操作。考虑为什么要这样做，我们是为了避免一个点经过多次时产生的错误。
那一个点为什么要经过两次呢？是因为我们要走下一条边和来时边乘积太大难以接受，我们需要绕一圈找一个更小的入边。那假设现在入边权值为 x ，一定要走的边为 y ，绕出去的边为 z ，那么直接走代价是 xy ，而绕出去代价是 xz+... ，看得出来必须有 z<y 否则就是越绕越劣，于是问题解决。
文学
简单来讲，就是平面上一堆点和一些半平面，可以选择一些半平面，每个半平面有相应的代价。求这些半平面覆盖所有点的最小代价。
那么有一种思路，即我们最后选出一些半平面，不被覆盖的地方要么没有，要么是个凸包。我们先只看有一个凸包没有被覆盖的情况，此时虽然一个点可能被多个半平面都覆盖到，但我们只考虑其中一个半平面的贡献，即如果它在凸包下面那么对应的就是它头顶上形成凸包的那一条直线。在凸包上的每一条直线我们都可以划定出一个其管控的范围来。
然后我们考虑对点的横坐标从小到大排序后枚举，假设当前点为 i ，我们考虑与直线 x=x_i 相交的凸包上的直线最多只有两条，即上面一条下面一条。那我们顺序枚举每一个点，每次考虑一下是否更换上下边界的一条边即可。因为最终的凸包生成方式一定存在于我们的 DP 序列中，所以是一定可以找到答案的。
注意有时可以放宽松限制，只要保证一定能包含答案并且时间复杂度允许就可以了。
JSOIP2022模拟赛11
基础概率练习题
同样，注意部分分的提示性。当 k=0 时，所有数的限制都一样，所以 a_1 是最大值的概率恰是 \frac{1}{n} 。
那么考虑 k>0 的情况呢？我们考虑，假设我们保证最终序列恰好有 i 个数 \geq k ，那么最大值不可能 <k ，并且如果我们找到了所有这样的序列，a_1 在其中是最大值的概率也恰是 \frac{1}{i} 。因为此时你只看 \geq k 的元素，相当于给这些元素都 -k 然后又做了一次 k=0 的部分分。
于是我们考虑如何求出除了 a_1 恰有 i 个数 \geq k 的方案数，我们设其为 f_i 。可以想到，虽然恰好不是很好求，但我们可以做一下二项式反演，即先钦定一些，然后容斥掉。所以我们推一下式子：
f_i=\sum_{j=i}^{n-1}{j\choose i}(-1)^{j-i}{n-1+m-(j+1)k\choose n-1}{n-1\choose j}
来考虑一下这个式子每一个部分的意义。
然后看第一个组合数，实际上是一个插板法。那我们就是把 $m-(j+1)k$ 个小球分成 $n$ 份的方案数，对应到这个题上，因为钦定了一定有 $j+1$（包括 $a_1$）是 $\geq k$ 的所以先把这些分掉，剩下的用插板法分。
那第二个组合数呢？我们考虑把那钦定的 $j+1$ 个单独提出来，把分出来的前 $j+1$ 份分给它们，然后剩下的按照顺序分。但我们发现我们实际上并不知道我们钦定的是哪些。所以这就相当于我们取出所有钦定的，两块分别计算再把钦定的插回原序列中。
于是这个式子就完美了。那么我们来考虑我们最终的答案，实际上就是：
$$
\frac{\sum_{i=0}^{n-1}\frac{1}{i+1}f_i}{{n-1+m-k\choose n-1}}
$$
分母的计算没有任何问题，考虑分子，我们把式子写出来：
$$
\sum_{i=0}^{n-1}\frac{1}{i+1}\sum_{j=i}^{n-1}{j\choose i}(-1)^{j-i}{n-1+m-(j+1)k\choose n-1}{n-1\choose j}
$$
然后我们把 $j$ 的枚举和含有 $j$ 的项提前，得到：
$$
\sum_{j=0}^{n-1}{n-1+m-(j+1)k\choose n-1}{n-1\choose j}\sum_{i=0}^{j}\frac{{j\choose i}}{i+1}(-1)^{j-i}
$$
很神奇的一步操作，把分式变换一下就是：
$$
\frac{{j\choose i}}{i+1}=\frac{j!}{(i+1)!(j-i)!}=\frac{{j+1\choose i+1}}{j+1}
$$
然后这样就又搬出来了一项，使得最后一个求和的式子：
$$
\sum_{j=0}^{n-1}{n-1+m-(j+1)k\choose n-1}{n-1\choose j}\frac{1}{j+1}\sum_{i=0}^{j}{j+1\choose i+1}(-1)^{j-i}
$$
对最后一个式子变换一下：
$$
=\sum_{i=1}^{j+1}{j+1\choose i}(-1)^{j+1-i}=(1-1)^{j+1}-(-1)^{j+1}
$$
然后问题就解决了。
## JSOI2022模拟赛12
### [发讲义](http://www.nfls.com.cn:20034/contest/444/problem/1)
感觉是一个贪心的思路？
一个可以递归处理的问题，我们可以把问题转化为两个人都在一个点，处理掉整棵子树的最小代价。
显然有两个地方需要特殊考虑，一是这个问题需要递归进哪一个子树，另一个是除了递归进的那个子树，最后一个被处理的链是哪一条。
考虑除了刚才特殊处理的两个位置，以外每一个叶子都会有其深度的贡献。但是有一点，即其中一个人往最后的叶子跑的时候，另一个接应的人就可以直接向下走了。
那么说最优的一定是除了被选中的子树外，最深的叶子最后处理，这样留给另一个点的空闲时间一定是最多的。
那考虑，但凡有分叉的点，必然需要两个点一起来处理。也就是说在另一个点跑最深的叶子时，接应的点可以一直向下，直到遇到分叉的位置然后停下来，等跑点跑完叶子之后递归进新的子问题。
所以现在的问题是怎么确定递归进哪一棵子树。
**好，上面那个做法假掉了。**
主要原因在于，如果我选中了一棵进入的子树，不一定在根的位置就不会走这个子树里面的点。我们发现，本体和分身可以同时走，当且仅当本体经过的位置没有分叉**或者分叉都被走过了**，也就是说我们可以提前用分身走掉分叉为本体“开路”，具体来讲是一组数据：
```
11
2 1
3 2
3 4
5 4
6 1
7 6
8 7
9 8
10 2
11 6
```
按照假做法最小代价是 $9$，而如果本体在 $1$ 时我们用分身走掉 $10,11$ 那么剩下的路就可以本体分身同时走。
那怎么办？先想一个暴力的做法，如果我们不考虑本题具体走哪棵子树，而是直接枚举叶子确定本题的路线，那如果这是我们再出来一个线性的转移是可以做到 $O(n^2)$ 的复杂度的。
当我们确定了本体的路线，我们实际上要确定的只有一件事：提前走掉哪些叶子。
首先不在对应子树里面的一定是要走完的，然后在对应子树里的，我们需要找到一个目标深度，并提前走掉深度上所有的叶子，然后递归进目标深度那个点继续处理。
因为确定了本体的路径，我们可以算出一段路径上所有分叉的代价之和。
$$
f_i=\min_{j}\{w(i,j)+\max(0,d(i,j)-mx(i,j))+f_j\}
$$
其中 $w(i,j)$ 表示 $i\to j$ 路径上分叉的代价之和，$d(i,j)$ 表示 $i,j$ 的距离，，$mx(i,j)$ 表示 $i\to j$ 路径上深度最大的分叉。$f_i$ 表示本体分身都在 $i$ 点的代价。
不过题解里面说这个本题的路径一定是走最深的点最优……虽然感觉是这样的但是还是不是很好证明，不过现在已经能确定有一个 $O(n^2)$ 的做法了。
因为我们已经确定了链的位置，我们把暴力转移写开，则有：
$$
f_i=\min_j\{f_j\}
$$
### [项链工厂](http://www.nfls.com.cn:20034/contest/445/problem/1)
套路题，会发现宝石的相对位置是不会变化的。
于是我们可以把询问位置对原位置作一个全局的映射，这个东西可以描述成 $y=kx+b$ 的一次函数形式，然后剩下的就是线段树直接做了。
### [生成树计数](http://www.nfls.com.cn:20034/contest/445/problem/2)
#### 行列式
注意，我们计算行列式是用高斯消元类似的运算法则，把这个行列式变成上三角的形式，然后求对角线的积即可。
观察这个行列式，会发现有数的位置很少，有点类似“带状矩阵”，很神奇的是，我们如果把中间那一截挪到最上面，就会形成一个天然的上三角，并且占据了 $n-2k$ 行。
那我们只要算一下下面的 $2k$ 行的贡献就可以了。那么现在问题是上面一些行都靠在最左边，我们需要移到最右边去。这是好办到的，因为一定要用上面那些行去移动，并且因为上面每一行都长得一模一样，所以这个操作可以用矩阵来描述，然后就变成了矩阵乘法的问题！
问题解决了！
#### 状压 DP
### [蜗牛](http://www.nfls.com.cn:20034/contest/444/problem/2)
- 注意看到这种欧氏距离的方程，如果有多个考虑差分，因为它们的二次项系数是相同的所以可以消除所有二次项，而解决一次方程组又是很方便地。
根据上面所说，我们得到了 $n-1$ 个一次方程，然后求解。如果只有一个解那么直接输出，否则要考虑最开始被差分的那个方程。
第一个方程实际上就是描述了最终的点到某一个点的距离，我们可以发现，当我们解出了这个方程组会剩下一些自由元，而每个自由元的贡献显然可以描述成一个向量。所以我们最终满足差分方程组的答案一定可以描述成从一个初始向量开始沿着若干自由元向量随意移动的结果。
显然不管怎么移动我们总能把这个距离无限变大，但是变小就不那么容易了。有一个显然的思路是我们先求出距离最小的解然后不断增大。
具体来说，如果我们想要解出最小距离解，只要保证最终向量到起点向量的连线垂直于每一个可以移动的向量就可以了。具体来讲垂直可以描述成点乘，然后列成线性方程组高斯消元就完事了。
## JSOI(P)2022模拟赛13
### [龙虾抄写器](http://www.nfls.com.cn:20034/contest/446/problem/1)
非常简单，直接主席树，回退操作就是回到之前的状态，然后这个题就做完了。
### [鱼](http://www.nfls.com.cn:20034/contest/446/problem/2)
比较难的计数。
具体思路为，我们可以发现，如果按照鱼长度从大到小排序，同一种宝石对应的鱼，只有出现最早的那一条有用。
同时，我们每考虑一条鱼，我们考虑哪些状态是以前一定取不到的。
可以发现，这种状态有两种，一种是之前考虑的那些宝石种类数量全都是 $0$，另一种是当前对应宝石种类取最多能取得情况。
第二种情况需要二分一下，看哪些位置是可以达到对应状态的，这些位置对应的宝石种类都要是 $0$，然后剩下位置任选就可以了。
我们发现这个方案比较难统计，但我们可以按照每种宝石最早出现的位置得先后顺序对宝石重标号，这样每次能产生贡献的位置就变成了一段连续的区间，然后线段树维护区间积就可以了（因为模数不是质数所以不一定有逆元）
### [二叉查找树](http://www.nfls.com.cn:20034/contest/446/problem/3)
比赛完才发现是水题。
赛时最后半小时胡了一个做法，本来想写爆搜得结果写了一个非常类似正解的 DP，即采用区间 DP 的形式，我们设 $f_{l,r,dep,tp}$ 表示考虑数据值 $l,r$ 区间内的点形成一棵树，深度为 $dep$，顶部的权值为 $tp$ 的最小代价。
然后这个东西复杂度是 $O(n^5)$ 的，可以获得 70 分。正解其实就是去掉 $dep$ 这一维，只要在上升时候加一下区间内所有点的代价之和就可以了，时间复杂度 $O(n^4)$，可以通过。
## JSOIP2022模拟赛14
### [巡逻](http://www.nfls.com.cn:20034/contest/448/problem/1)
### [梦想封印](http://www.nfls.com.cn:20034/contest/448/problem/2)
- 对于一张图，如果我们想暴力地找出所有的环，那么有一种思路是随便跑出一棵生成树，然后任何返祖边都可以对应至少一个环。
这个题也是使用类似这种暴力的思路。首先根据某年 WC 的启发，对于所有的环的权值我们都可以任意选择，因为我们一定可以从起点出发走到环走一圈然后原路返回，这样路径上的权值都被异或掉了。所以环的贡献是可以任意取的。
然后考虑如果不考虑图是可变的，我们怎么找到所有环的贡献形成的线性基。
我们可以随便找到一棵生成树，然后只需要统计所有返祖边形成的环就可以了。不难看出这样虽然没有包含所有的环，但是互相异或肯定可以异或出所有环的值。
那么我所有能得到的值，一定可以通过一条从根开始地树上路径异或上整个线性基得到。
然后这种删边的问题大概率是时间倒流变成加边的过程。
我们维护一棵一 $1$ 为根的生成树考虑我们加入一条边之后，如果这条边两个点都不在树中不进行操作。如果两个点都在树中说明成环了，更新线性基。如果只有一个点在树中，那么肯定是另一棵树和当前的树合并了，于是直接暴力 DFS，有环的维护，并更新树上路径就可以了。
我们发现，两条路径等价当且仅当两条路径塞进线性基后出来的数是相同的。知道这一点，我们每次更新线性基的时候就暴力扫一下所有树上路径更新一下就可以了。因为线性基只会被更新 $O(\log U)$ 次所以复杂度是正确的。
### [sumsum](http://www.nfls.com.cn:20034/contest/448/problem/3)
比较套路的点分治题。
我们可以发现，因为路径长度范围是固定的，所以产生贡献的路径也是固定的，所以每个点的贡献次数一定也是固定的。
如果我们求出了每个点的贡献次数那么就可以直接树剖或者树上前缀和来处理答案了。考虑每个点的贡献次数实际上是每个点被多少个长度在 $[L,R]$ 里的路径经过。对于这种“到某个点距离小于 $x$”类似的问题，既要向上又要向下考虑的问题我们通常使用点分治解决。
考虑我们在一个分治中心处理掉所有经过的路径。我们考虑计算时，进入一棵子树，我们显然可以通过树状数组得到以当前点为一端，长度合法且经过分治中心的路径数量。那么我每个点都计算这个信息，则经过每个点的路径就是这个点子树内这个信息的和。
然后就做完了。注意分治中心的贡献需要特判。
## JSOIP2022模拟赛16
所以说……失败的原因是因为没有及时放弃第一题去打剩下题的暴力？但这样搞不好第一题没分直接翻车。还是因为第一题花费时间太长了？那就是状态的问题了。
### [蛋糕](http://www.nfls.com.cn:20034/contest/451/problem/1)
一开始没想好就开始写是最大的问题。
我本可以用线段树维护删除每个点的对侧点是哪个，但我却去维护了删除点的个数，这个东西显然更不好维护，花费了太多时间。
然后正解注意到一定会成为前十大的，那么考虑到这个点之前的状态是不变的，考虑之后其实就变成了十段，直接模拟就可以了。
### [理想城市city](http://www.nfls.com.cn:20034/contest/451/problem/2)
### [袋熊](http://www.nfls.com.cn:20034/contest/451/problem/3)
这其实是一道可做的题，可惜考场上读错题了。
注意到很重要的性质就是这个不能向上走，于是就可以比较方便地转移。然后转移可以写成矩阵的形式，一次矩阵乘法是 $O(m^3)$ 的，但是可以发现这个东西具有决策单调性，于是可以优化成 $O(m^2)$。
然后用线段树维护，但空间开不下，于是线段树底层分块优化一下空间就可以了。
## JSOIP2022模拟赛19
我觉得既然不知道零散知识点往哪里写，那就写在考试笔记里面，减少题解体量。
### [璀灿光华](http://www.nfls.com.cn:20034/contest/456/problem/1)
没有什么特别的，注意要记住 `getline(cin,s,'\n');` 就可以了。
### [波浪](http://www.nfls.com.cn:20034/contest/456/problem/2)
注意对这种序列题，如果要用 DP 的话我们通常要考虑序列的生成方式，如：
- 从前往后一个一个加入数字。
- 从小到大枚举数字，去填充空位置。
- 从小到大枚举数字，保留一些极长连续段，并在段中插入数字。这种做法要保证最后恰好生成了一段，否则会有重复的计算。注意这种方法连续段的位置是不确定的，而相对关系是被确定了的。
### [星系调查](http://www.nfls.com.cn:20034/contest/456/problem/3)
主要是根本没做过类似点到直线的距离，还要拟合这种问题，于是不敢推式子……
好吧现在手推一下，好用一个很笨的方法推出来了，而且不写成 $ax+by+c=0$ 的形式式子还是很不好看，但是 $(x_0,y_0)$ 到直线 $ax+by+c=0$ 的距离的平方确实是：
$$
\frac{(ax_0+by_0+c)^2}{a^2+b^2}
$$
其实有这个公式就可以愉快地推式子了。
不过大多数情况下还是有不愿意推的情况存在……需要克服。
注意有逆元的运算做树上路径问题时就不要放在倍增数组里了，而是直接差分，否则会写得很麻烦。
另外无向图找强连通分量或者说是环，也可以写拓扑序，只要把原来判度数为 $0$ 改成判度数为 $1$ 就可以了。
## JSOIP2022模拟赛20
### [航空管制](http://www.nfls.com.cn:20034/contest/458/problem/1)
- 有顺序的题一定要想想时间倒流！可能直觉上两种情况对称，但是倒着看有可能会使已知信息产生变化。
### [千年虫](http://www.nfls.com.cn:20034/contest/458/problem/2)
考场上的 DP 基本上是对的，但是最后的正解，题解里都说打表找规律发现有用的状态很少于是就做完了……
另外题也是个错题，两边不可以独立考虑的。
### [拼点游戏](http://www.nfls.com.cn:20034/contest/458/problem/3)
好题。
- 看这种一加一减的可以尝试转化成差分，因为本来就是一些差分的形式。
然后转化到差分序列上，就是挑一些差分数，任何一种选法都能对应原来的一种选法。于是最优的肯定是全选正数。
那么对于第二问，实际上就是说，我们有一些选了的位置的极长连续段，我们可以一次扩相邻的两个连续段，只要不合并成一个。
那么显然，因为剩下的数都是负数，肯定是取整个区间并去掉最大的那个。这个东西可以用权值树来维护一下，每次树上二分就可以了，于是这个题就做完了。
## JSOIP2022模拟赛21
### [城墙](http://www.nfls.com.cn:20034/contest/461/problem/1)
### [Vim](http://www.nfls.com.cn:20034/contest/461/problem/2)
### [画图](http://www.nfls.com.cn:20034/contest/461/problem/3)
## JSOIP2022模拟赛22
### [染色](http://www.nfls.com.cn:20034/contest/462/problem/1)
### [博弈论](http://www.nfls.com.cn:20034/contest/462/problem/2)
### [错排问题](http://www.nfls.com.cn:20034/contest/462/problem/3)
## JSOIP2022模拟赛23
### [随机数生成器](http://www.nfls.com.cn:20034/contest/464/problem/1)
### [Friend](http://www.nfls.com.cn:20034/contest/464/problem/2)
### [HEDWIG](http://www.nfls.com.cn:20034/contest/464/problem/3)
## JSOIP2022模拟赛24
### [有趣的家庭菜园](http://www.nfls.com.cn:20034/contest/466/problem/1)
### [水壶](http://www.nfls.com.cn:20034/contest/466/problem/2)
### [裁剪线](http://www.nfls.com.cn:20034/contest/466/problem/3)
## JSOIP2022模拟赛25
### [ 动物园](http://www.nfls.com.cn:20034/contest/468/problem/1)
一道几乎是 KMP 模板的题目，没有什么好说的。
### [书法家](http://www.nfls.com.cn:20034/contest/468/problem/2)
刚开始没有看到每个字的横坐标范围是无交的，如果知道这一点就只剩下 DP 了，稍微有一点难写。
### [购票](http://www.nfls.com.cn:20034/contest/468/problem/3)
已经写在了知识点汇总里面的斜率优化处。
## JSOIP2022模拟赛26
### [有趣的家庭菜园 2](http://www.nfls.com.cn:20034/contest/470/problem/1)
考场上想到了最终序列的高度，一定是一段不降一段不增的序列。
这个一定可以通过正反做两次不降子序列得到。具体做法就是线段树优化 DP 于是这个题就可以了。
### [序列](http://www.nfls.com.cn:20034/contest/470/problem/2)
这题考试时不会做，于是果断暴力打满。
问题就在于**没有消除冗余信息的影响**。比如这个题，我考虑完十位，考虑到百位的时候，显然原来十个十个它们的百位一定是相同的，此时如果把这些**一定相同**的信息合并，就可以使搜索的复杂度得到保证。
就是说，这个题搜索的思路根据直觉确实没问题，但考试时最大的问题是怀疑搜索是否正确并尝试寻找优于搜索的方法然后再去想复杂度优化，而正确的思路应该是直接去看搜索的复杂度优化。因为搜索的话不进行合并仅仅是一条搜索链复杂度就是 $O(n\log n)$ 的复杂度，然后直接抛弃这个做法是不可取的。
做题时注意 $F(n)=kF(\frac{n}{k})+O(n)$ 这类的复杂度，注意有时也许直觉是正确的（？。
### [音质检测](http://www.nfls.com.cn:20034/contest/470/problem/3)
考试时不会做，于是果断暴力打满。
最终还是用**神仙 yyh 的神仙思路**才过掉的这个题。其实总结一下的话大概就是：
- 取两个向量对应的第一个位置的积，可以用第一个的列向量乘第二个的行向量。
- 取两个向量的点乘值，可以用第一个的行向量乘第二个的列向量。
根据第一条，如果我们使用矩阵快速幂处理线性递推式子，我们想知道的其实可以描述成两个向量首位的乘积。
那么就可以描述成形如 $(v_0\times v_1^T)[0][0]$ 的形式。这样做有什么好处？我们想要求的是一个区间的这个东西的和，并且**矩阵乘法对加法有分配律**，那么对区间的这些向量进行修改，只要在整体的左边或者右边乘上转移矩阵即可！于是这个题就被解决了。
## JSOIP2022模拟赛27
### [抄卡组](http://www.nfls.com.cn:20034/contest/471/problem/1)
### [江南乐](http://www.nfls.com.cn:20034/contest/471/problem/2)
### [ 日程管理](http://www.nfls.com.cn:20034/contest/471/problem/3)
## JSOIP2022模拟赛28
### [亚瑟王](http://www.nfls.com.cn:20034/contest/472/problem/1)
### [ 道路改建](http://www.nfls.com.cn:20034/contest/472/problem/2)
### [幻想乡战略游戏](http://www.nfls.com.cn:20034/contest/472/problem/3)
## JSOIP2022模拟赛29
### [好朋友](http://www.nfls.com.cn:20034/contest/474/problem/1)
### [玄学](http://www.nfls.com.cn:20034/contest/474/problem/2)
### [ 雪原](http://www.nfls.com.cn:20034/contest/474/problem/3)
## JSOIP2022模拟赛30
### [荷马史诗](http://www.nfls.com.cn:20034/contest/476/problem/1)
关于 $k$ 叉哈夫曼树。分析一下，如果按照二叉哈夫曼树的做法的话，唯一的问题就是在最后一次合并的时候实际上凑不齐 $k$ 个，就会导致有些距离只有 $1$ 的位置被浪费。
考虑，只要每次都恰好凑齐就不会有问题。考虑一下，我们逐步从小到大生成一棵树，那么每次延伸，都是找出来一个叶子，然后在它下面挂上 $k$ 个节点，也就是说叶子数会增加 $k+1$。
所以，如果我们想保证最后能凑齐 $k$ 个只要保证 $k-1\mid n-1$ 就可以了。
显然我添加一些频度为 $0$ 的点不会对答案产生影响，缺少的那些直接加一些权值为 $0$ 的点就可以了。
### [园子里](http://www.nfls.com.cn:20034/contest/476/problem/2)
首先这个题能发现可以用高斯消元做。
考虑要消元的矩阵长成什么样子。我们把点按照 $h$ 排序，这样每个柱子能跳到的地方是个前缀。
我们先考虑 $t>0$ 的情况，此时每一个方程可以描述成形如：$x_i=1+\frac{1}{p_i}\sum_{j=1}^{p_i}x_j$。
然后我们把这个东西放到矩阵里面，会发现如果不看常数项，矩阵恰好是个下三角的形式。并且对角线左侧，每一行有值的位置一定是一个前缀并且系数都相同。那我们直接给 $x$ 记一个前缀和就可以轻松求出 $x_i$。每次都要二分到当前能跳到的最靠后的位置。这样 $t>0$ 的就被解决了。
考虑 $t=0$ 的情况，如果有多根柱子 $h$ 相等并且 $t=0$ 那么这个矩阵就不是优美的下三角形式。考虑如何改变使得它仍然是个下三角。此时，这些柱子 $h$ 相等 $t=0$ 说明它们完全等价，$x$ 的值也是完全相同的！所以只要把对角线上的那个系数改一改就可以了，于是沿用上面的解法问题解决。
### [教义问答手册](http://www.nfls.com.cn:20034/contest/476/problem/3)
这个题最直接的就是 $60$ 分的 $O(nL^3+nL^2\log n)$ 的矩阵优化 DP 的做法。
考虑这个实际上用矩阵的话会造成浪费。我们采用类似的思路尝试能不能进一步降低复杂度？
矩阵本质考虑的什么？前方的每个位置对当前位置的贡献。那其实，如果我每次询问只想获得一个点的结果，完全没必要搞 $O(L^2)$ 次转移把前面 $L$ 个对后面 $L$ 个的贡献全都算出来，只需要考虑前面 $L$ 个对当前位置的贡献就可以了！
并且，有一个很好的地方，就是连续的 $L$ 个位置，对后面的贡献，每一种贡献情况最多只有一个位置产生了贡献，并且系数最多为 $1$！
这就意味着我们可以分治，算出来每个区间以每个点为左端点，右端点到 $r$ 的最后 $L$ 个分别是什么。以及每个点为右端点，区间前面 $L$ 个对当前点的贡献系数分别是什么。
这个东西显然是可以向上合并的，总复杂度就压到了 $O(nL\log n )$ ！于是本题就被解决了。
## JSOIP2022模拟赛32
### [拔河](http://www.nfls.com.cn:20034/contest/478/problem/3)
- 图论问题转化。
## JSOIP2022模拟赛33
### [手办](http://www.nfls.com.cn:20034/contest/480/problem/2)
### [防壁](http://www.nfls.com.cn:20034/contest/480/problem/3)
## JSOIP2022模拟赛34
### [ 拉面比较](http://www.nfls.com.cn:20034/contest/483/problem/1)
### [分组](http://www.nfls.com.cn:20034/contest/483/problem/2)
- 数形结合思想的应用。
考场上不太清醒做法假了。
### [打麻将](http://www.nfls.com.cn:20034/contest/483/problem/3)
- 注意调和级数复杂度。
- 利用欧拉序配合线段树可以动态维护子树直径。
刚才去补了关于欧拉序求子树直径的笔记。
首先这个题有个贪心，和考场上想的略有不同。即每次一定是找深度最大的子树直径大于等于 $m$ 的点，然后删掉它和它的子树，直到找不到。
所以考虑用线段树来快速求子树的直径。
然后我们考虑一个类似 BFS 的思路，显然一个点被选的必要条件是它子树里面没有能选的点。那我们考虑，对于每一个 $x$ 我们都找出一些点使得它子树里面没有能选的点，并且它可以选。这样的点对于同一个 $x$ 是没有祖先后代关系的，并且对于所有 $x$ 点数和是 $O(n\log n)$。
然后有一点很重要就是答案的数量级也是 $O(n\log n)$，这意味着我们只要暴力找到所有答案点就没有问题。
对于一个 $x$，我们可以挑一个可以选的点，选中它，然后倍增找到它能选的最深的祖先。如果这个点子树内没有其它可以选的点那么就把它加入队列里面，以此类推。
比较麻烦的是我们选了一棵子树之后，要考虑它的影响，这个没有问题只要打一个标记就可以表示这个子树不能被选。
额然后这题似乎就完事了？
## JSOI2022模拟赛29
### [告别](http://www.nfls.com.cn:20034/contest/486/problem/2)
- 排列看成置换环。
- “举例子”思想的应用。
注意一种**把排列看成置换环的思考方式。**
类比之前这样做于是用线头 DP 解题，这个题也是如此。
就是说，一个排列可以用一些置换环描述出来，它们大小不一。但是我们可以发现，置换环数量和对应置换环大小相同的排列在这个题里面是等价的。
想一下为什么？我们这个是在调整一些数的位置。假设这次调整以某种方式影响到了若干个置换环，那么结束后对置换环个数和大小产生的影响一定是固定的。
并且假设最终序列我们要的是 $1,2,...,n$，那么这种状态可以唯一地被表示为 $n$ 个大小为 $1$ 的置换环。
也就是说，置换环状态相同的状态本质都是相同的。那么这种状态数就是 $n$ 的有限集划分数。大概只有 $140$ 不到种，可以用矩阵优化转移。
有个问题，我只知道影响是相同的，但是这个影响很不直观，构建矩阵非常麻烦，我该怎么做？
注意这又是一种**举例子**的思想，即**既然它代表了一类排列，那我随便构造一个然后在上面进行操作后再倒回去看变化**。因为刚才本质相同的推导，我们一定是不重不漏地覆盖了所有情况，可以大大简化思维难度和代码难度。
### [现实](http://www.nfls.com.cn:20034/contest/486/problem/3)
题解的写法来自于我考场上一种假掉的做法……然后被 Hack 了，但是能过题，不想多想了。
不过还是重在对 Tarjan 思想的理解。另外学了一下 Tarjan 离线线性求 LCA，比较神奇。
## JSOIP2022模拟赛35
### [城墙](http://www.nfls.com.cn:20034/contest/487/problem/2)
- 多考虑贡献的“生成方式”，考虑哪些情况最不好考虑，并想办法更换生成方式去掉它。
- 网格图上对角线的生成方式。
- 网格图要想办法枚举一些元素然后转化为序列问题。
还是要注意，这种类似我们在格点图上找正方形，找矩形什么的问题，都可以考虑去枚举一些元素然后将它转化为序列上的问题然后据情况去优化。
这个题，考试时只想了枚举左上角，或者枚举两列，枚举一列之类的情况，但是在这个题都不适合。
以后要增加一个思考方向，对于正方形可以考虑同一条对角线的贡献。显然正方形的左上角右下角都在同一条对角线上。而且我们发现如果这样拆开，两个点的信息就变得可以维护了。
因为这种一个框的形式，维护有拐弯的地方很不方便，此时如果把信息分到两个顶点上，这时均摊到每个点上只需要维护两个方向直直地一段就可以了。此时就可以用树状数组维护。
还是要注意**贡献的生成方式要多角度地考虑**，而网格图上就要考虑一种对角线形的生成方式。
### [舞会](http://www.nfls.com.cn:20034/contest/487/problem/3)
- 数的排名问题，二分答案思想的应用。
搞我心态的二分答案题。
这个一开始看上三叉树是没有问题的。我们考虑取的是什么东西？是三个点里面的**中位数**！
还记得我们如何二分答案找中位数吗？对就是这个思路！
显然三叉树的根最后的值是答案，我们考虑答案能到达 $x$，当且仅当根下面三个子节点有两个值大于等于 $x$。
注意注意！考试时一直在想怎么处理大的和小的，殊不知一定可以对应到两个都大的情况。
对于处理**中位数或者数的排名**类的问题要有类似二分答案的思路。记住一些数中位数大于等于 $x$ 的条件是一半的数都大于等于 $x$。此时就不用费力地去分开讨论三种情况了。
另外这个题 $n\leq 19$ 的部分分是给爬山的……在 OI 赛制下随机化算法的正确性让人难以信服。
## JSOIP2022模拟赛36
### [黑客](http://www.nfls.com.cn:20034/contest/488/problem/1)
- 善用单调队列，单调栈。
不得不说 yyh 在这方面真的很强。
### [宝藏](http://www.nfls.com.cn:20034/contest/488/problem/3)
- 任意值域高维前缀和的理解及其变形。
重点是对高维前缀和的理解。不管是几维的前缀和，不管值域是多少，都可以用 $01$ 高维前缀和的思路去写是没有问题的，想象成一维一维往里面加就没有问题。并且一般情况下直接统计 $-1$ 的位置是没有问题的。
但在这个题里面需要略作修改。我们设后半段三进制状态为一定不选，一定选，可选可不选。假设它们分别是 $0,1,2$，但致命问题是 $1$ 的状态并不包含 $0$ 的状态。但我们只需要略作修改，在枚举每一位时，如果判断某个数这一维是 $2$ 的话直接把对应的 $0,1$ 的信息加上就没有问题了。于是本题就解决了。
## JSOIP2022模拟赛37
### [摸鱼否](http://www.nfls.com.cn:20034/contest/490/problem/1)
没什么好说的，真的。
只不过比赛时偷懒没写排序直接用了归并然后寄了……
### [图样](http://www.nfls.com.cn:20034/contest/490/problem/2)
期望题，一种比较好的思路是转化成所有方案的贡献和然后除以方案数。
多层的 DP 可能是有的是方案数有的是总价值这个要搞清楚。
### [螺旋](http://www.nfls.com.cn:20034/contest/490/problem/3)
做过类似的题目于是赛时五十分钟写了个单 $\log $ 做法，然后喜提 TLE。有可能是 `set` 常数太大了。
## JSOI2022模拟赛32
## JSOIP2022模拟赛38
### [第K大](http://www.nfls.com.cn:20034/contest/494/problem/1)
你跟我说这个题正解复杂度是 $O(\frac{qc\log n}{\omega})$？？我本机随机数据跑两秒钟都过去了？？？
通过这个题可以认识到一般区间贡献问题分为三种：可差分问题，可重复贡献问题，既不可差分也不可重复贡献问题。
可差分问题一般就是区间和，区间异或和，
### [博弈问题](http://www.nfls.com.cn:20034/contest/494/problem/2)
- 离线处理树上问题可以想树上启发式合并或线段树合并。
- 线段树能维护的问题特征至少都有每个点的答案只和自己的子树有关和父亲无关。
这个题实际上也不是线段树合并而是字典树合并。考试时问题实际上已经想了大半然后被 T1 坑傻了没写正解。
其中形式是分析正确的，即答案只出现在那种有一个叉点数是 $1$ 另一个不为 $0$ 的位置。先不考虑线段树合并的问题，就算一个一个向线段树里面加信息，考虑这个东西怎么维护？
如果存在一个这样的点，那么这个点的答案一定是点数是一的那边的点在另一边查的答案。可以发现这个信息是只和当前子树有关的，于是可以用线段树维护。当然这样的话 `pushup` 的复杂度就是 $O(\log n)$ 的，不过关系不大。
然后考虑可以写树上启发式合并，但这样总复杂度是 $O(n\log^3n)$ 的，不太可以。
但是想一下实际上类似线段树那样直接写个字典树合并就没问题了。
## JSOIP2022模拟赛39
### [按题目填色](http://www.nfls.com.cn:20034/contest/495/problem/1)
考场上一波分析都是正确的不多说了。
### [星际逃亡](http://www.nfls.com.cn:20034/contest/495/problem/2)
写了题解同样不多说了。
### [圆圈游戏](http://www.nfls.com.cn:20034/contest/495/problem/3)
写了题解。
## JSOIP2022模拟赛40
### [俄罗斯套娃](http://www.nfls.com.cn:10688/contest/497/problem/1)
时间充裕的话也要对拍看下复杂度是否正确。
考场上线段树写错了被卡成 $O(n^2)$。
### [网格](http://www.nfls.com.cn:10688/contest/497/problem/2)
- 不断地，不断地发掘性质。
- Tarjan 求割点。
考场上（应该是）意识到答案只有 `-1,0,1,2` 几种，并且判掉 `-1,0,1` 剩下的就是 `2`。
然后观察部分分不难发现我们可以直接写一手 $O(nm)$ 的暴力交上去就能获得 $56$ 分。然后自然，写暴力是个好习惯，在暴力的基础上，继续思考，我们发现我们实际上是在找割点，而割点可能出现的位置一定是在某个预先放蝈蝈的位置的八联通块上。因为只有边界不可能有割点，而因为割点只有一个所以到提前放蝈蝈的位置距离不超过 $1$。此时我们就可以按照暴力的思路，但是要忽略一定没用的点，只保留给出的点的八联通块内的白点做暴力就可以过去了。
其实浪费了很多时间，没有仔细分析实际上并不需要用题解的做法……真的写的太麻烦了。
另外关于 Tarjan 求割点的问题，依旧是考虑 DFS 生成树，一个点不是树根，则它是割点的充要条件是它的一棵子树中的点走不到它的祖先。就是说，它的某棵子树只走一条返祖边，最多走到当前点，那么这个点就一定是割点。语言不好表达但是不难理解。
### [连线珠](http://www.nfls.com.cn:10688/contest/497/problem/3)
- 写暴力。
- 换根 DP 递归式思考，理解应用情景。
- 对于无“起点”“终点”的问题，尝试考虑如果固定“起点“”终点“会不会简化问题，如果能的话考虑枚举”起点“”终点“然后思考优化思路。
换根 DP。但是从这道题能体会到写暴力的好处。
刚开始写一个 $O(n^2)$ 的暴力，这通常是在有大体思路但是不确定做法正确性时的最好选择。
另外这个题有助于加深对换根 DP 的理解，要以一个递归的思考方式看换根 DP 问题。
换根 DP 一般适用于对于一棵树以每个点为根的情况都会产生一定贡献的 DP 问题。当然在写正解之前可以先按照思路写一个枚举每个根的暴力也是没有问题的，而且方便对拍。
## JSOIP2022模拟赛41
一般……某场考试该写暴力还是正解应该是可以感觉出来的吧。
### [IOI 馒头](http://www.nfls.com.cn:10688/contest/499/problem/1)
- 交换状态和答案可以是 DP 中的一个启发思路。
首先想到的思路是那个可以买背包的背包，把背包的体积看成负数，但这样复杂度是 $O(m^2)$ 的，但是 $m$ 只有 $10^4$，兴许能跑。
但是还是没看到所有物品大小都是固定的，所以朴素的想法是设状态为花多少钱能获得的最大空间。
但是，总钱数是 $O(m^2)$ 级别的，然后乘个 $n$ 就很难做。考虑，我们发现空间的值域不是很大，交换两维照样能做，那么我们设状态为达到某个空间的最小花费，于是时间复杂度就是 $O(nm)$ 的了。
### [机器人实验](http://www.nfls.com.cn:10688/contest/499/problem/2)
- 在维护类似同余系的信息时，要把状态储存了什么给想清楚，并尽量找最好写的状态记录方式，既可以减少后期思考量也可以降低错误率。
水题，因为不可能走出去所以是个基环树森林。答案上界是环大小之和。
于是建出图来，每棵树上考虑可以激活的机器人，如果还有空位就直接找到对应时间激活就可以了。
### [人烟之山](http://www.nfls.com.cn:10688/contest/499/problem/3)
- 线段树上二分也不一定是对全局的二分，一般线段树二分所依赖的是能够通过区间信息判断这个区间内是否存在答案。朴素地写，如果在一个区间上二分，那么可以直接先对着 $\log$ 个区间挨个判一遍，然后找到存在的区间再深入二分是完全没有问题的。
- 李超树是可以维护线段的。但是注意李超树储存的最优势线段必须覆盖整个区间，所以如果是线段插入的复杂度可能就是 $O(\log ^2 n)$ 了，可以理解为找到对应区间的线段树节点，然后在每个节点上进行插入操作。
- 凸壳是可以线性归并合并的。注意即便是合并之后，所有的直线也是按照斜率排序的，所以归并时，插入的顺序也是按照斜率插入的。斜率相同的看截距，矮的先插入。插入时的操作就类似单调队列，或者说是一般的斜率优化做法，判断要插入的直线和队尾前一条直线的交点，以及最后两条直线的交点关系，判断要不要踢掉就可以了。
- 寻找单点最优势直线时，可以考虑维护凸包或使用李超树。
有了上面这些知识，这题就好做多了。
当然考场上一个重要的思路在于想到只有相邻的两个拐点才可能有贡献，也就是产生贡献的是所有的折线。这点有点类似 NOIO，要强化记忆。
然后可以可持久化李超树，不过因为维护的是线段所以空间复杂度是两只 $\log$ 的，很不好搞，考虑维护凸包。
然后剩下的都在题解里了，于是本题终结。
## JSOI2022模拟赛36
### [奶油蛋糕塔](http://www.nfls.com.cn:10688/contest/500/problem/1)
主要还是欧拉路这一块的问题。
- 无向图存在欧拉路的充要条件是图连通且存在 $0$ 或 $2$ 个点度数为奇数。如果是有向图那就是图联通且每个点入度出度相等或存在两个点一个多入度一个多出度。
- 对图论模型敏感。
### [计数](http://www.nfls.com.cn:10688/contest/500/problem/2)
- 好好读题，考试时把至多读成了恰好导致题目根本做不下去……
- 注意部分分的启发性。
- 状态设计规范化，而且要尝试不同的设计方式，应用在本题上可以显著降低代码复杂度。
### [彼岸蔷薇](http://www.nfls.com.cn:10688/contest/500/problem/3)
原来部分分有原题啊……怪不得完全想不出来。受益匪浅了属于是。
- 对于给定若干个元素，一些元素之间可能有互斥关系，但是只要求选出最多，也就是每个元素价值相同，那么通常这是有贪心思路的。
- 注意线性离线求 LCA 的做法。
- 有时不要把实现复杂化，想想某些东西是否可以均摊。
- 对于树上问题，可以先尝试转化为链上问题，然后再推广到树上（虽然这题没用上）
总之是很妙的一道题。
对于给定若干树上路径，要求选出最多的不相交路径是可以贪心的。
即把路径按照 LCA 的深度排序，从大向小选，如果可以选，就把 LCA 所在子树删除，然后继续判断。这样显然是正确的，因为每条路径权值相同，当我们选了一条路径，对于 LCA 子树以外的部分，变化就只有不能再走进 LCA 所在子树里面了。所以就尽量选较深的路径即可。只要能选那么选哪个都是无所谓的。
在实现上，因为每个点只会被删一次，所以可以直接 DFS 删除，不用考虑各种麻烦的情况。
具体做法直接参考拜傅里叶教传教帖吧，没有详细写的必要了。
## JSOI2022模拟赛37
### [划分串](http://www.nfls.com.cn:10688/contest/501/problem/1)
正常做法是结合 KMP，复杂度直接是 $O(nmk2^k)$，算一下可能都达到 8e8 了，真的不相信这东西能跑 1s。然后打表发现很多前缀状态都是一样的，于是进一步发现 $k=7$ 时等价类最多 $10$ 个，于是打个表预处理一下，就完事了。时间复杂度 $O(10nmk)$，跑得很快。
### [降落伞环](http://www.nfls.com.cn:10688/contest/501/problem/2)
代码能力差劲。
另外不要再用那个在 DFS 树上，用返祖边覆盖来判断某个点删掉能不能断环的做法了，无论是有向图还是无向图，都！是！假！的！
另外经常缺少找到像暴力的做法的灵感。
这里当我发现出现度数大于 $2$ 的点之后，可行的点不超过 $4$ 个，此时就该意识到，四个点分别建图分别处理是完全可行的，只能说要更加敏感。
当你意识到自己的做法非常复杂时就该进一步想想有没有什么地方的做法能替换成更好写的做法？多在这里花时间，通常比赛都不会有那种巨大讨论的问题。
## POI2015
### [[POI2015] LOG](https://www.luogu.com.cn/problem/P3586)
好像之前在 QBXT 模拟赛做过一道类似套路的，这种问题只要单独讨论那种大小超过操作次数的，这一部分一定每次操作都要取到，剩下的部分只要总和可以就一定合法。于是这些信息直接线段树维护即可。
因为每次都是询问整个序列所以维护一棵值域线段树就完了。
### [[POI2015] KUR](https://www.luogu.com.cn/problem/P3589)
有个地方写假了但是不太想改。
这个要从给出的 01 串开始考虑，考虑实际上每一个数都能转化为起始位置的一段区间，那么合法的位置必然是这些位置的交。于是求交，看交的大小即可，记得减去那些最后 $m-1$ 个位置的贡献，因为它们后面不足 $m$ 个自然不会成为起始位置。
为了方便求交其实可以转化为差分的形式，排序之后就能得到某段区间被覆盖多少次了。另外这个最终合法区间可能不止两段，需要排序之后判一判。
### [[POI2015] KWA](https://www.luogu.com.cn/problem/P3583)
打表发现，超过 $128$ 的数都可以被表示出来，具体能想到这里是因为对于 $[1,n]$ 以内的整数的平方而言，能组成的数的值域是 $O(n^3)$ 的，但是组合方案数是 $O(2^n)$ 的，那就有可能 $n$ 到了一定程度后每个数都有方案。于是可以打表。
然后对于求 $k$ 这一块，对于一个较大的数 $x$，一定要找到最小的平方的和大于等于它的数 $n$，然后考虑 $\frac{n(n+1)(2n+1)}{6}-x$ 是否能被组合出来，如果可以在前面去掉就可以了，$k(x)$ 就恰好是 $n$，否则是 $n+1$，因为数较大的时候 $(n+1)^2$ 加上刚才的数一定能被组合出来。
并且不难发现，如果 $k(x)=n+1$ 的话 $x$ 就是超重的，因为 $\frac{n(n+1)(2n+1)}{6}$ 比它大并且 $k$ 一定是 $n$。
于是本题解决。
### [[POI2015] WYC](https://www.luogu.com.cn/problem/P3597)
都快忘记这个东西的存在了……
正常如果是边权为 $1$ 的话直接矩阵快速幂就可以了。
如果不是 $1$，我们发现边权最多为 $3$，那么转移的时候 $f_{i,j}$（$j$ 步走到 $i$ 的方案数）最远可以从 $f_{i,j-3}$ 转移过来，于是矩阵开三倍然后依旧矩阵快速幂。要求和的话单独放一个位置每次记录所有的和就没有问题。
### [[POI2015] KIN](https://www.luogu.com.cn/problem/P3582)
这种问题显然是枚举一个端点考虑另外在每个位置的贡献。
每次移动右端点考虑每个左端点会获得什么贡献就可以了。
### [[POI2015] ODW](https://www.luogu.com.cn/problem/P3591)
[P3591 [POI2015] ODW 题解](https://www.luogu.com.cn/blog/SDNetFriend/solution-p3591)
### [[POI2015] MYJ](https://www.luogu.com.cn/problem/P3592)
复杂度玄学的区间 DP。
如果我们设状态为某个区间，最小值是多少并且枚举最小值的位置，此时跨过最小值的所有人的贡献是固定的，最小值两侧也是互不影响的子问题所以可以 DP.
### [[POI2015] POD](https://www.luogu.com.cn/problem/P3587)
环上问题可以考虑把序列复制一份做能省事很多。这里写了一手线段树，1s 跑 $10^6$ 没过去……
正解是哈希，按照环上问题思路，先复制，然后对于每一种颜色，开一个前缀和数组，不过这个前缀和是模意义下的，模数是当前这种颜色的数量。此时我们发现如果一个区间是满足条件的，它左右端点所有颜色的前缀和数组一定是相同的，于是可以哈希。
### [[POI2015] LAS](https://www.luogu.com.cn/problem/P3584)
刚开始以为可以谈心实际上是个 DP。
状态设为考虑到第 $i$ 个人，这个人向左吃/向左平分/向右吃/向右平分时，前一个人的状态是什么样的。
注意转移时四种状态并不等价，比如如果一个人向左吃的话是无法确定他向右吃能获得的价值的，在考虑下一个位置时连带着一起判断就可以了。
### [[POI2015] TRZ](https://www.luogu.com.cn/problem/P3590)
[P3590 [POI2015] TRZ 题解](https://www.luogu.com.cn/blog/SDNetFriend/solution-p3590)
### [[POI2015] MOD](https://www.luogu.com.cn/problem/P3596)
[P3596 [POI2015] MOD 题解](https://www.luogu.com.cn/blog/SDNetFriend/solution-p3596)
### [[POI2015] PUS](https://www.luogu.com.cn/problem/P3588)
线段树优化建图没什么问题。
这个题看起来像差分约束，不过因为边权全都是 $1$ 所以直接跑拓扑序也没有问题。
## POI2014
### [P3577 [POI2014]TUR-Tourism](https://www.luogu.com.cn/problem/P3577)
无向图跑 DFS 生成树后，没有横叉边！
### [P3564 [POI2014]BAR-Salad Bar](https://www.luogu.com.cn/problem/P3564)
### [P3580 [POI2014]ZAL-Freight](https://www.luogu.com.cn/problem/P3580)
先想朴素做法。
因为车之间只有出发时间的差异，故一定是先发出发早的。而开到对面的车是完全等价的，就算记状态也只记数量就可以了。
一个可行的方案即尽量早发车，最后所有的车到对面去后一起发回来，但这样可能有问题，比如两辆车最早发车时间间隔极长，此时可以利用这段时间把对面的车发回来。甚至可以把多辆车的空余时间拼起来把对面的车多发回来一些，所以可能？不存在贪心方案，考虑朴素 DP 吧。
奥对了，可能复杂度 $O(n^2)$ 的 DP 只有一维的状态……刚才无耻地去看了一眼 TJ。
根据刚才的思路，我们每次其实要考虑用多少车的发车时间去拼成一段来发返回的车。对了显然是把对面的车全发回来是最优的，因为这一分钟早晚都要消耗。
我们设 $f_i$ 表示前 $i$ 辆车完成往返需要的时间，那么转移即从 $j$ 转移到 $i$，把 $(j,i]$ 段的车尽量早地发出去，然后在第 $t_i+s$ 时把这些车全发出去就可以了。
所以转移写一下就是：（注意这里要把 $t$ 给搞成互不相同的，这显然是可行的）
$$
f_i=\min_{j<i}\{\max(f_j+i-j-1,t_i)+2s+i-j-1\}\\
f_i-2s-i+1=\min_{j<i}\{\max(f_j+i-j-1,t_i)-j\}
$$
可以看出，$t_i$ 的增长率恒大于等于 $i$ 的增长率，也就是说对于 $j$，越大的 $i$ 越有可能使 $t_i$ 取到最大值。对于已经取到 $t_i$ 的，显然只要找最大的 $j$ 就可以了。
否则这个点贡献是固定的，同样取个最大值就可以了，于是可以用单调队列优化。
其实大多数时候，单调队列都可以被一些带 $\log$ 的算法或数据结构代替。
用一句话描述它的使用场景：动态维护序列区间最值，并且区间两端点移动方向一致。看这个题，$\max$ 的限制实际上就是左端点右移，加入新元素实际上是右端点右移，而且我们还要取区间最值，故使用单调队列。
### [P3578 [POI2014]LAM-Solar lamps](https://www.luogu.com.cn/problem/P3578)
一般来讲只是对坐标系旋转的话是很好找出逆运算的，但是如果不只是旋转，即最终坐标系不是直角坐标系，并且还是逆变换，即求原坐标系的向量在新坐标系的坐标，那没什么办法，只能手推，要么就很麻烦写个高斯消元求逆矩阵。
求出这个之后，就变成了偏序问题。考虑对一维排序后从小到大考虑，那判断每个点能不能被某个点影响，就要考虑它的另一维的范围和被点亮的时间，这是个二维问题，可以写树套树但是常数太大了估计跑不过去。
其实树套树最后也是二分，这里可以考虑一下整体二分，问题也满足整体二分的性质，于是两只 $\log$ 一只二分一只树状数组，就会快很多。
### [P5904 [POI2014]HOT-Hotels 加强版](https://www.luogu.com.cn/problem/P5904)
重新考虑这个加强版，数据范围开到了 $10^5$ 显然要改做法，不能换根了。
实际上我们考虑三个点的关系，其实只需要考虑两种情况：
1. 三个点两两之间 LCA 是同一个点，那么在它们 LCA 处统计答案。
2. 三个点两两之间有两个 LCA，此时在较浅的 LCA 处统计答案。
首先可以记 $f_{i,j}$ 表示 $i$ 子树内深度为 $j$ 的点数。
对于第一种情况，长剖之后每个点合并轻儿子就可以了。
第二种情况，记 $g_{i,j}$ 表示 $i$ 的子树内，剩余深度为 $j$ 的点对数，这个剩余深度，指对于一对点 $a,b$，它们的深度相同，LCA 在 $i$ 子树内，且二者到 LCA 的距离减去 LCA 到 $i$ 的距离为 $j$，此时和别的树的 $f$ 更新答案即可。
#### 实现细节：
可以采用动态内存池的方式，因为长链剖分过程中，继承重儿子信息一般需要整体平移，实际上就可以看成是指针的移动，就会好写很多。
## 联合省选2022
### [P8294 [省选联考 2022] 最大权独立集问题](https://www.luogu.com.cn/problem/P8294)
## NOI2022模拟赛1
### [好序列](http://www.nfls.com.cn:10688/contest/505/problem/1)
有时候 DFS 的复杂度也会很玄学地正确掉？
另外做这个题的时候还是把问题复杂化了。当我想到从小到大枚举质数然后找地方乘上去的时候，就该意识到是不是质数无所谓，直接从小到大枚举数就可以了。
### [简单数据结构](http://www.nfls.com.cn:10688/contest/505/problem/2)
对于一般数据结构中出现的很小的新东西，比如这个题的行数，可能是直接乘在复杂度上的，也可能是 $k^3,2^k$ 之类的复杂度，从复杂度角度判断算法这些要考虑到。
另外这种套路确实是一种船新的思路，记住就好。
### [ 送分题](http://www.nfls.com.cn:10688/contest/505/problem/3)
## NOI2022模拟赛2
### [滑冰](http://www.nfls.com.cn:10688/contest/506/problem/1)
- **全局变量不要起名 y0 y1 ！！**
- 图论问题无路可走时要想想优化见图规则。
分析一波可以发现，最优方案下，不可能在一行横着走两次，也不可能在一列竖着走两次。
经过一通分析后发现，前面操作放下的冰块只对当前行或者列走一次有贡献，对后续显然没贡献。
然后也就是说，我们在一个位置选择转移，我们可以考虑选一个方向，利用冰块我们可以到达任何可达的位置，不过权值不同，直接 Dij 跑就可以了。
但是这样复杂度是 $O(n^3\log n)$ 的，过不去。
得益于 yyh 神仙提供的优化建图策略，即考虑向某个方向走，走到的尽头权值一定是 $1$，向那个方向走一格的权值一定是 $2$，然后发现剩下的位置按照这种规则走，算出来的权值都是正确的，于是每个点就只有两条出边了，复杂度优化到 $O(n^2\log n)$，可以通过。
### [ 距离之和](http://www.nfls.com.cn:10688/contest/506/problem/2)
啥也不用说，记一个容斥：
$$
\min(a,b)=a+b-\max(a,b)
$$
证明很简单，把 $\max$ 移项就可以了。这个的用途就在这题上有体现，最终答案可以描述为：
$$
\max(\min(A_0,B_0),\min(A_1,B_1))
$$
这种情况下如果我们把 $\min$ 转化成 $\max$，那么就全都是 $\max$，方便处理。这样就变成了：
$$
\min(A_0,B_0)+\min(A_1,B_1)-\max(A_0,B_0,A_1,B_1)
$$
于是本题就解决了。
### [括号序列](http://www.nfls.com.cn:10688/contest/506/problem/3)
## NOI2022模拟赛3
### [我的名字](http://www.nfls.com.cn:10688/contest/507/problem/1)
一种罕见的求某串在原串种出现次数的做法，应用场景很广范。基本特征：
- 字符值域不大，一般为字母，当然稍微大点无所谓。
- 询问串长度总和有保证。
- 可以带修，可以在线，可以有通配符。
- 数据范围是 $10^5$ 不能再大了。
其思路为，用 `bitset` 同时维护所有可能的位置，比如拿到一个串，从第一个字母开始考虑，显然此时原串中所有该字母出现的位置都可能是合法的，这个直接用预处理每个字符的 `bitset` 求就可以。
考虑第二个字符，可以把合法位置统统后移，后移后字符与第二个字符匹配的位置是可行的，同样也是一步与的操作就可以了。通配符可以多挪几位就能处理了。
### [Measure](http://www.nfls.com.cn:10688/contest/507/problem/2)
### [Permutation](http://www.nfls.com.cn:10688/contest/507/problem/3)
容斥菜鸡。
一般来讲这种生成排列的题目，不太好直接生成最终的排列，因为一般无法状压确定哪些数用过了。通常思路是划分为若干段或者维护别的信息（？）
我们分析可以得出，最终的排列一定可以划分为若干个极长值域连续段，而限制可以描述为每个数所在的极长连续段长度不超过 $a$。
也就是说，我们可以考虑把值域划分为若干段，满足 $a$ 的限制，并且这些段可以任意交换顺序。
但有个问题，可能存在某一种排列方式使得被划分出来的两端紧挨着合并了，也就是说原来的划分方案此时并不是最长段。
那实际上我们就多了个限制，要求不存在这种“拼接”的方案数。
然后我们发现，如果钦定一些拼接，然后转而求最小，似乎比较好处理。
我们把问题想成恰好产生 $0$ 个拼接，就可以二项式反演了。
为啥可以？感性理解显然没问题，非要写一个式子，那就是：
设 $f_i$ 表示对于某种划分方案，恰好产生 $i$ 个拼接的方案数，$g_i$ 表示钦定 $i$ 个拼接，剩下随便放的方案数，于是有：
$$
g_i=\sum_{j=0}^i{i\choose j}f_i
$$
于是我们可以确定这个要容斥做。
具体如何做呢？我们还是考虑划分一段一段的基本思路不变，那么钦定拼接就相当于我们划分的若干段的位置关系又给固定下来了，也就是说我们原来的段叫小段，多个用“拼接”连起来的小段叫作大段，那么显然最后我们可以任意放这些大段，因为大段内部的关系是固定的。
于是便可以 DP。
## NOI2022模拟赛4
### [围墙](http://www.nfls.com.cn:10688/contest/508/problem/1)
中规中矩数据结构，2A 可还行。
### [失落神庙](http://www.nfls.com.cn:10688/contest/508/problem/2)
谁能想到，随机数据居然那么强呢……
分析后得知，每个点被腐蚀的时间实际上是它到所有边界**曼哈顿距离**的最小值。
我们知道二维平面上到某个点曼哈顿距离相等的点形成一个菱形，所以我们判断某个位置答案能否达到 $x$ 只要判断是否存在位置能塞下距离为 $x$ 的菱形就可以了。
对于二维平面上的曼哈顿距离，可以**根据两点之间的方位来单独考虑两个点的贡献**。
于是分类讨论四个方向，考虑如果要放下大小为 $x$ 的矩形，中心在当前列的上下边界是什么，这个可以用单调队列求区间最值得到。
并且相邻列答案相差不超过 $1$ 所以暴力试答案即可。
另外，虽然说单调队列端点移动方向要一致，但如果出现反向移动也不要僵住，比如这个每次反向移动距离最大为 $2$，反正求最值，用那两个位置的答案更新一下就可以了。
### [开会](http://www.nfls.com.cn:10688/contest/508/problem/3)
- 根据中国剩余定理，一组模数互质的同余方程，在模模数之积的意义下，解是唯一的，并且是一个双射，即两个不完全相同的同余方程组答案不会相同。
有了这个知识点，我们可以处理互质的情况，直接 DP 就可以了。
然后考虑不互质，题解给了种很高妙的思路，即取一个周期 $m$，把时间按照模 $m$ 分类，此时显然可以分别计算各个同余类的答案。
这有什么好处呢？假设 $m$ 可以整除所有的 $l$，那对于一个 $l$ 在考虑一个同余系的时候，其长度变成了 $\frac{l}{m}$，此时如果除 $m$ 之后的 $l$ 互质的话，又可以转化为互质的问题做了！
所以已知我们复杂度大概是 $O(mn^2)$ 的，我们考虑如何最小化这个 $m$。
首先一定可以取 $2^4\times 3^2\times 5\times 7$。操作前，先把每个数变成 $\text{LCM}(m,l_i)$，其实就是把周期复制几次，防止不整除的情况发生。
然后我们可以发现，此时任意输入时在 $[1,50]$ 范围内的 $l$，除去 $m$ 后一定是互质的。
此时复杂度已经可以了，但复杂度还可以更优秀，即我们 $m$ 取 $2^2\times 3\times 5$。此时进行上述操作后，剩下的 $l$ 一定是质数的幂，此时只要把低次的复制几份，使得对于每个质数，长度都相同，然后就可以 DP 了。
说起来简单但是实现还是有点东西的。多次提到的“复制”操作也没有真的复制，只不过是取用的时候模一下长度罢了。
## 0508省选集训1
### [ 铁路票价](http://www.nfls.com.cn:10688/contest/511/problem/1)
- 注意用桶的时候，无穷大的设定不要越界！
一种想法是离线，标记一下每条边被修改的时间。
然后转化成求 1 到某点所有最短路上最小时间的最大值。
这个应该可以直接 BFS，每个点存下最短距离以及所有最短路的最大值。这样显然对于后续的状态转移是最优的。
### [ 领地](http://www.nfls.com.cn:10688/contest/511/problem/2)
大毒瘤 STL 题。
考虑每次新增一轮的贡献，显然也需要考虑前几轮。而前几轮实际上是当前轮平移得到的。
我们考虑把能平移到一起的点放到一个系里面，然后求出和当前轮相关的所有方格，每个格子的贡献区间，这部分细节巨大多就不展开说了。
然后假如和当前轮有关的最早的轮是前 $mx$ 轮，那么 $mx+1$ 轮后新增贡献都是一样的直接乘就可以了，并且 $mx$ 的范围和 $n$ 一样。
### [ 棋盘游戏](http://www.nfls.com.cn:10688/contest/511/problem/3)
问题根本没有分析透彻。问题在于写 T2 太久了……
- 对于这种和四连通相关的问题可以考虑分成连通块来做。
首先无解情况，即四角没棋子，或者上下两行存在连续的两个空位。
然后分成连通块，可以分析出实际上连通块都是由中间提前放置的棋子分隔的，然后每个块单独考虑。
实际上我们主要考虑中间那一行，因为上下两行如果有解，每个位置什么时候放棋子都是无所谓的，于是考虑中间一行，是左右放的还是上下放的。
设状态为 $f_{i,j,0/1}$ 表示考虑到第 $i$ 列，中间的位置在当前连通块第 $j$ 个放，且是上下放/左右放的方案数。注意这个 $j$ 考虑的是第 $i$ 列以前的连通块，而不是最终的位置，否则就变成了生成排列题没法做了。
于是分别讨论三种情况：（$siz$ 为第 $i-1$ 列之前的连通块大小，$c$ 为当前列上下两行空位数）
1. 当前列和前一列都是上下放：
$$
f_{i,j,0}=\sum_{k=1}^{siz}f_{i-1,k,0}\times A(j-1,c)
$$
2. 当前列上下放，前一列左右放，要求当前列在上一列之前放：
$$
f_{i,j,0}=\sum_{k=j-c}^{siz}f_{i-1,k,1}\times A(j-1,c)
$$
3. 前一列上下放，当前列左右放，要求当前列放的时候不能上下放，并且前一列在当前列之前放：
1. 当前列有一个空格：
$$
f_{i,j,1}=\sum_{k=1}^{j-1}f_{i-1,j,0}\times (s+2-j)
$$
2. 当前列有两个空格：
1. 两个一前一后：
$$
f_{i,j,1}=2\sum_{k=1}^{j-2}f_{i-1,k,0}\times(j-1)\times(s+3-j)
$$
3. 两个都在后面：
$$
f_{i,j,1}=\sum_{k=1}^{j-1}f_{i-1,k,0}\times A(s+3-j,2)
$$
### [ 断层](http://www.nfls.com.cn:10688/contest/511/problem/4)
也是一个时间倒流的思路。
这里时间倒流原因是，假设我正常模拟和我最终询问的信息量级别完全不同，最终我只关注最顶上那些土层是什么而不关心其他位置。
所以考虑时间倒流，看最终最顶上的土层在最开始在哪个位置就可以了，于是考虑反向模拟最终顶层的运动路径，此时只需要维护一个序列就可以了，复杂度大大降低。
然后下一步转化是旋转坐标系，这个考试时已经想到了，即因为操作全都是斜 45 度角，所以旋转一下操作就全都变成了水平和竖直的移动，此时维护一个序列表示原来每个位置顶层的土现在的横纵坐标，然后就可以用线段树区间修改了。
！注意一点！因为坐标系转过来了，所以原来相邻的两层之间不能紧挨着，中间隔一层需要，否则就变成了“插空站”，不同层之间就对不齐了，也就是说每次移动要移动两步才可以。
## 0508省选集训2
今天这场难度比昨天低不少。
### [JOIOJI](http://www.nfls.com.cn:10688/contest/512/problem/1)
很水的题，不解释了。
### [邮戳拉力赛](http://www.nfls.com.cn:10688/contest/512/problem/2)
分析一下可以发现这是个“序列上的复杂路径问题”，可以意识到这个要用线头 DP。
先写出 $O(n^3)$ 的暴力转移之后，观察式子发现可以优化到 $O(n^2)$。
### [足球](http://www.nfls.com.cn:10688/contest/512/problem/3)
还是有些性质要观察的。
注意 BFS 在网格图上时一定要判边界！Windows 下可能根本不会出错！
分析一阵发现可以直接搞分层图，一拆五，然后这题就解决了。
其中，转移过程中也运用了一些移动分解的思想，大概是某天受 yyh 的启发才知道的！
### [绳](http://www.nfls.com.cn:10688/contest/512/problem/4)
有很多性质，但分析不够。
注意这种限制看起来很复杂，某些判别类问题没有多项式复杂度解法时，可以考虑打表或者推一下是否有什么更简单的结论。
考场上分析出了染色只需要最开始染一次，但没分析出序列合法的条件，或者说根本没想着分析。观察到这个 $f$ 就是个判别用的东西时就该想到去分析什么情况是合法的。
然后会发现，考虑所有极长同色连续段，除了开头结尾长度必须是偶数，分类讨论一下就能证明充要性。
于是就可以随便做了。
## 0508省选集训3
难度中规中矩。
### [ 团子制作](http://www.nfls.com.cn:10688/contest/513/problem/1)
第一眼看上去很像之前做的模拟退火的那个传说团子师傅，实际上这个限制要强很多。
画出来所有冲突的情况，发现中间的丸子的位置关系除了相同就是一个在右上一个在左下间隔一格。
于是可以按照对角线 DP 了！
### [月票购买](http://www.nfls.com.cn:10688/contest/513/problem/2)
考场上做的问题不大。
还是要看部分分，看了第一档部分分之后，意识到需要先跑 Dij 然后找到所有可能在路径上的点。
那么完整的做法，其实就是找两个可能在路径上的点，这两个点要保证存在一条路径同时经过它们两个，因为跑了 Dij 之后，转移图是个 DAG，于是直接来一手拓扑排序 +DP 就可以了。
### [毒蛇越狱](http://www.nfls.com.cn:10688/contest/513/problem/3)
很……经典的思路。
首先想暴力怎么做，枚举每个问号的状态，我们设 $0,1,?$ 的个数分别为 $a,b,c$，那么复杂度就是 $O(2^c)$ 的。
然后我们想，假设我们求了高维前缀和数组，此时每个位置，某一位如果是 $1$，那么就包含了这一位为 $0,1$ 的情况，如果是 $0$ 就只是 $0$，也就是说这个数组和我们要求的最大的差别就是不存在某一位一定是 $1$ 的情况。
那我们其实可以去掉所有那些必须是 $1$ 的位成了 $0$ 的情况，也就是说，高维前缀和数组这些位原本是随便选，现在我们钦定一些位置为 $0$ 去减掉，可以直接容斥一波，这样复杂度就是 $O(2^b)$。
同样，如果我们用高维后缀和做类似操作，复杂度就是 $O(2^a)$ 了！
于是我们对于每个询问，都在三种方式里面找到耗时最小的，显然单词询问复杂度不超过 $2^6$，于是总复杂度 $O(n2^n+q2^6)
开荒者
很麻烦的一个题，不过能凸显部分分的启发作用。
还是先进行转化，发现实际上就是要求一个以每个点为中心的矩形，最终覆盖所有位置，代价就是矩形上下左右宽度之和。
所以朴素思路是枚举四个方向的宽度然后求，但那样复杂度是 O(r^6) 的，与暴力没什么差别，考虑进一步考虑。
发现有一档分 r 很小 c 很大，于是我们考虑枚举一维，就比如枚举上下的宽度，来求左右符合要求的最小宽度。
枚举上下宽度之后，考虑每一行会涉及到若干个 y 不同的位置，那我们要满足这一行填满就需要填满左右边界和两两之间的空位。
两两之间的空位考虑的是左右宽度之和，最后答案对着间距最大的空位取 \max 即可，而对于左右边界则是分别取 \max 然后加起来，于是问题解决，时间复杂度 O(r^3n) ，可以得到 30 分。
后来我们想，其实本质不同的行不会很多，是 O(n) 级别的，我们把行给离散化，算一下每个关键位置，如果从上到下考虑就是最上面的位置和最下面的位置的下一个位置都要考虑一下，类似扫描线，这样枚举上下界的复杂度就变成了 O(n^2) 了！
然后我们发现，如果上下宽度之和固定，那么相交关系也是固定的，如果没有上下的边界那么形状也是一样的。
但是考虑上下界影响怎么办？上下宽度之和固定，我们减少上界增加下界，相当于整体平移！既然是平移我们自然可以换个东西移，即我们移动上下界！
考虑先把所有的宽度都分配给下面，然后把边界从上向下移动，每移动一次都统计一下答案，取最小值就可以了！
并且我们考虑，先考虑两两块之间的空隙，我们显然要取最大值，那实际上这个就变成了区间最大值，就可以滑动窗口一样用单调队列解决了。
于是三个单调队列分别维护块之间，左边界右边界的最大值即可。
然后代码很难写，细节很多，考试时一般就打 30 或者写一个带 \log 的做法就走人了。
0508省选集训4
注意！在写初始化列表的时候不要用强制类型转换！{1e9,0} 如果赋值给两个整形的结构体会 CE！！！
幽深府邸
长途巴士
我坚信思路是没问题的，只不过细节有点多搞不好写挂了。
实际上需要考虑的东西就是哪些人需要踢，在什么时候踢，或者是每个服务站之前踢多少人。
首先可以想到，我们踢人一次踢的是一个连续段，那我们设一个一维的 DP 状态，f_i 表示考虑了前 i 个人的最少花费。当然这里的人是已经按照 d 从大到小排序之后的。
然后有两种转移，一是选前面的一个 j ，计算出在一个服务站踢掉 [j+1,i] 这些人的最小花费，另一个是从 f_{i-1} 加上全程不踢 i 的代价。
显然第二个是好算的，那么对于第一个转移，我们把服务站也按照模意义下从大到小排序，那为了求踢掉这些人所需要的最小代价，显然是找最早出现的服务站最好，并且这个服务站取模后必须在 (d_j,d_{j+1}) 范围内，那我们维护一个 v_j 就表示这个范围内最早出现的服务站所在的轮数，同时维护一个 s_i 表示 c 的前缀和，于是有转移：
f_{i}=\min_{j=0}^{i-1}\{f_j+s_i-s_j+(i-j)w\times v_j\}
然后这个式子显然可以斜率优化。但是有个问题就是如果按照一般斜率优化的方式，斜率单调了但是横坐标不单调，于是不能线性做，那么就用好写的李超树这题就解决了！
港口设施
二分图染色时，区间连边相当于将整个区间颜色确定为一样的，可以视为合并了整个区间的点，所以可以选择合适的考虑方向，并用某种方式（nxt 数组或线段树）来维护区间的合并。
思路比较独特的一道题。
首先转化题意，变成把所有区间分成两份，要求每一份里面不存在相交的区间，但是允许包含。
所以朴素的思路就是建边判二分图并求出连通块数量 x ，则答案就是 2^x ，但是直接建边边数是 O(n^2) 的，考虑优化。
首先处理序列问题，考虑方向很重要。
我们把所有区间按照左端点从小到大排序并枚举，也就是说其实是维护了一个左端点的序列，枚举到左端点时在尾部加入，枚举到右端点时删除。这个删除操作可以用并查集维护下一个没有被删除的位置。
然后我们考虑在枚举到某个右端点时，此时我们需要建边，需要连上所有在当前区间左端点右边的，还没有删除的区间，这样看没什么用，但是还可以发现一个特点即这些区间的颜色一定是一样的。
而且我们考虑在连接新的边时，如果向多个颜色已经确定一样的点连边是没有意义的，只要连其中一个就可以了。于是我们需要考虑用某种方式来合并已经确定颜色一样的点。
考虑我们正常处理时，实际上就是不断地在并查集上面跳找到下一个没有删除的点，那么我们能不能一下子跳过所有无需连接的点呢？显然是可以的。
我们对每个点维护一个 nxt_i 表示 i 向后的同色块最大的范围，当然这个是指在左端点数组中而言的，此时如果我们连边之后，需要跳并查集，那就不是直接跳 i+1 的并查集了而是直接跳 nxt_i 的并查集，这样我们就能快速找到需要处理的位置了。
但是实际上这个 nxt 的更新还是有问题的，比如我先是把一个区间里面的每个点的 nxt 都放到了 t ，此时我某次连边，左端点在这个区间的中间，我把这个点的 nxt 改成了当前的右端点的位置，那么问题来了，实际上这个区间右半边的 nxt 严格来说也需要修改，为什么可以不改呢？
我们考虑，这种情况特点是什么？第一个找到的位置不是它对应连续段的第一个点。而这种位置每次操作最多只有一个！所以我们每次找到哪个点就修改哪个的 nxt 就没有问题了！
当然不放心的话可以直接写一手线段树，区间修改 nxt 。这个因为考虑顺序的问题，前面删掉的点后面也一定不会被考虑，直接覆盖就可以了。
所以我考试时如果想到这里真的会写线段树。
听了 yyh 神仙的做法后，我发现……
其实是一个线段树做法，规约成一个模型即：
二分图染色问题，可以删点，连边方式是由一个单点向一个区间内所有未删的点连边，判断是否是二分图。
做法即，我们建一棵线段树，同时用并查集维护序列上每个点向后没删的点。
每次连边，我们可以拆成若干个线段树上的区间。可以发现，当我们第一次连某个区间的时候，需要连到每个包含的点上，但第二次再连这个区间只需要连其中一个就可以了，因为这个区间里的点颜色已经确定相同了。这样我们可以在节点上打一个标记就可以了。
另外第一次连的时候借助并查集找到所有没删除的点，暴力连就可以了。如果要优化复杂度，考虑到某个区间的父节点颜色确定的话也可以只连一个。总体复杂度 O(n\log n) 。
独特的城市
这个题感觉做过？不过最后一档部分分当时肯定做的没有这么顺利，而且好像是我没补这个题？
首先能想到，独特的点一定出现在当前点的最长链上，即当前点到两个直径之一的路径上。考虑先找到两个直径端点然后分别作根进行考虑。
我们 DFS 遍历整棵树，先想如何处理每个点颜色不同的情况，考虑如何会使得路径上的点不独特，其实就是有另外不在路径上的分叉，占据了路径的某些位置。
那我们其实可以考虑，非路径上的子树深度最深的链会占据一些位置，而这些位置对应的深度是连续的，所以我们可以维护一棵深度线段树，最后要找的就是所有没有被覆盖的位置的数量，也就是求最小值数量，于是这个问题解决。
正解怎么做呢？在考虑树上问题时，可以先放到序列上来考虑 。
想一下我们操作的本质，如果是一个序列，我们从左向右考虑，每次都覆盖当前点向前 的一段区间。通常我们考虑这种区间颜色数问题，是需要在每个颜色中钦定一个点产生贡献的。我们发现既然是向前的区间，那么越靠前的点越难被覆盖，如果某次覆盖把某个颜色当前所保留的最前面的点给覆盖了，那这个颜色就一定全都被覆盖了，而如果没有覆盖到最前面的点那么当前颜色一定会产生贡献。
于是我们考虑只使每个颜色的第一个点产生贡献，每次加入新点时，判断一下对应颜色上面是否有点，有的话就不产生贡献，否则当前点就是最靠前的点，需要考虑贡献。
当然这个过程是一个惰性删除的过程，我们记录每个点最前面的贡献点的位置，如果它被覆盖了我们不急着去更新，直接在线段树上修改仍然是正确的。直到我们需要更新某个颜色的状态，即考虑当前点对应的颜色时，我们才需要更新一下当前颜色最靠前的点。
于是这样问题就解决了，在前面部分分的基础上改一点就可以了。
又是 yyh 神仙的神仙做法
这个题实际上可以线性，刚开始实际上可能想到了？但是还是按照题解走了。
还是先放序列上考虑，我们实际上是要维护一个深度序列，假设左侧深度最小，那么我们实际上是从左到右枚举，枚举到某个位置之后会删除从这个位置向前的一段。
那考虑上树，决定我们删除的深度的，是除进入子树外的最大深度，那我们考虑长剖一下，进重儿子时，要从当前点删除最长的轻儿子，进轻儿子的时候就要删重儿子。如果我们每个点都先跑重儿子就会发现一个点只会被删一次！
然后用栈维护没有被删除的点，删点就是弹栈，于是这个题就线性了！
NOI2022模拟赛8
不打暴力吃大亏。
啊，我满脑子都是打暴力。
智慧树
思路二十分钟，调题三小时（还没调出来）。
首先这种树上启发式合并优化的 DP，把贡献下放到叶子上其实是个不错的选择，省去了各种 map 或者动态开空间之类的麻烦事。
最后败在细节上，关于一个全局取 \min 没处理好，应该分析出每次用的时候直接取就好了。
极限火花
可以写线段覆盖，但是因为精度什么的问题太大，于是果断随机撒点。
美元巨大二的二
好题！
注意扩展欧拉定理的应用，质数塔每一层的模数都不同，但是至多有 O(\log p) 层。
一种神奇的均摊复杂度，像这种一个区间被修改若干次后等价的问题可以用势能分析。
首先是扩展欧拉定理要记住，用的时候一定要特判那个 +\varphi(p) 。然后对于质数塔而言，每一层的模数就是套一个 \varphi ，那么层数是 \log 的，我们就可以对每个位置维护一个质数塔然后就可以写暴力了！
然后快速幂这里太慢了，直接用光速幂，预处理每个模数下，每个底数的幂次，当然是像 BSGS 那样分块维护，即维护每一个底数的 0,1,2,3,...,B,2B,3B,... 次，然后求快速幂的时候就可以 O(1) 了！
然后对于这个区间修改，可以发现一个性质，如果两个位置被相同的修改覆盖了 O(\log p) 次，二者就会变得完全等价。
那我们考虑，设 h_i 表示 i-1 和 i 之间的势能，每一次修改 [l,r] 时，就把 h_l,h_{r+1} 设为 O(\log p) 并且把 [l+1,r] 之间的 h 减一。
我们可以发现 h\le 0 的一串位置是等价的。考虑每次修改，会将整体势能减少区间长度，又增加 O(\log p) ，那么在修改区间较长的情况下，整体势能是在下降的。
如果修改区间较短影响又不会很大，那么只要用 set 维护相同的连续段，线段树维护每个点的值就可以了。
所以均摊下来复杂度就是 O(n\log^2n) 。
ZJOI2022 Day1
自己来练一练，先打暴力。
P8329 [ZJOI2022] 树
会不会同构的树不是很多？先写十分暴力然后看一下。
诶可以先写状压，也是个不错的选择。
诶好像没必要考虑两棵树？其实就是两个状态乘起来啊，互为补集！
状压每一位代表是否是叶子，好了，现在得到了 20 分。
暴力还能接着打吗？有没有多项式复杂度的做法。
好了以上是赛时想法，下面是正经做法：
O(n^4) 以前没碰到过 DP 还有平方项的东西直接给整不会了……
其实也可以不考虑这个平方项，因为我们需要平方是因为有两棵树情况分别对应，平方才能得到答案。
那我们干脆不考虑这个平方的东西，直接把两棵树的信息都搞在状态里面，就省去了平方的麻烦。
按照之前有一个思路，我们可以把一棵树的状态描述成考虑了几个点，有几个点被钦定为叶子，有几个点被钦定为叶子但是还没有子节点。
那么我们可以直接把两棵树的这个信息存到状态里，就是一个 O(n^5) 的 DP。但实际上，我们要保证两棵树每个点状态相同，所以被钦定为叶子的点数一定是一样的，于是状态就是 O(n^4) 的了，可以拿到 60 分。
O(n^3) 比较好懂的就是那位拿平方做的神仙
P8330 [ZJOI2022] 众数
这个题 40 分的暴力显然是好打的。
首先枚举一种取值作为外部取值，找到其对应的点，然后对颜色进行前缀和，计算贡献后取最大值。
时间复杂度 O(na^2) ，可以获得四十分。
注意对于区间众数类似的题目一般是没有 polylog 的做法的，通常要想想根号分治等根号算法。
P8332 [ZJOI2022] 面条
前 15 分直接模拟，因为第三个点只需要折 k 次就全都一样了，所以特判一下就可以了。
然后还有第四五个点看起来都不大，考虑下是否有什么多项式做法？怀疑这个东西有循环节，先写 15 分试一下。
NOI2022模拟赛10
链式进化
mex 类问题较适合以确定答案求存在性的方式解决。
仪式
[随机捕食](