Day -？？
被告知来 mx。
Day -2
放了 48h 历时 3 天的暑假。
Day 0
玩径人踪灭，千山鸟飞绝。
晚上闲的没事去 wc 搓差分宇宙，结果 tm 忘带纸了，给 4 个人发 wx 没一个人回我，最后急中生智上 luogu 才把 KinNa 摇过来。
Day 1
考试。
没啥说的，菜。
T1 写了 70，T2 写了 40，T3 一眼秒了，T4 写了 20。
本来还是有很多分可以写的，但鉴定为脑子瓦特和时间不够就没写，摆摆。
最后交的时候发现 T4 code 不见了（？，发现是之前删文件时删了（？？
出场和大家一合计觉得 70+80+100+40=290 是大众分，被踩爆了。
结果一出榜就两个 290 以上的，还是小学生（？？？
rk3 的也就两个还是 KinNa 和 PC。（upd：PC 在 T3 改时限后豪取 290
一分没挂，但是只有 210，但但是是能排 15。
以下是题解。
T1
一直在想用线段的左右端点做下标转移，最后发现优化不能。
令 \(f_{i,j}\) 表示以 \(i\) 为最右端点，最多选出 \(j\) 条不交线段的方案数，考虑转移至 \(f_{k,j+1}\)。
显然能加的线段有 \(k-i\) 条，故转移系数先乘上个 \(2^{k-i}-1\)。
然后考虑能新增的无用线段，有 \((n-k)\times (k-i)\) 条，故再乘上 \(2^{(n-k)\times (k-i)}\) 即可。
T2
首先爆搜能拿 80，嗯。。。
考虑 DP，令 \(f_{i,j}\) 表示在 \([1,i]\) 中，能被 \(a_1,a_2\dots a_j\) 整除的数的个数，考虑静电容斥，那么有：
\[f_{i,j}=\lfloor \frac{i}{a_j}\rfloor+f_{i,j-1}-f_{\lfloor \frac{i}{a_j}\rfloor,j-1} \]T3
线段树，没啥好说的。
人傻自带 14 的常数但是没被卡，那么又是谁被卡了呢/tx
维护右端点最长 1 段、最长 0 段，左端点最长 1 段、最长 0 段，右端点最长 10 段、最长 01 段，左端点最长 10 段、最长 01 段，全局最长 10 段、01 段即可。
T4
咕
Day 2
练习。
上午梦熊加了 8 道题，于是变成了找原题大赛，通过数最少的两道题是因为找不到。。。
以下是题解。
CF379D
md 洛谷恶评。
考虑造成贡献的只有 \(s1,s2,s1+s2,s2+s1,s2+s2\)，所以使用 fib 的方式算出系数，再暴力求解即可。
AT_arc171_d
考虑把 \(\text{hash}(l,r)\) 变为 \((\text{suf}_l-\text{suf}_{r+1})\times B^{n-r}\)。
所以 \(\text{hash}(l,r) \ne 0\)，当且仅当 \(\text{suf}_l \ne \text{suf}_{r+1}\)。
所以对于每队 \(l,r\)，连边 \(l\to r+1\)。
然后对图进行 \(p\) 染色即可。
P3977
观察到 \(m\) 很小，所以对每行状压，1 表示插眼，设 \(f_{i,j}\) 表示第 \(i\) 行状态为 \(j\) 的方案数。
发现 \(n\) 有 \(10^6\)，所以考虑矩阵。
令 \(A_{i,j}\) 表示上一行的状态 \(i\) 是否可以转移到下一行的 状态 \(j\)。
矩阵快速幂即可。
CF757D
直接状压，设 \(f_{i,j}\) 表示 \(i\) 处切了一刀，切完后数集为 \(j\) 的方案数，刷表法转移即可。
PS：不知道为啥填表法寄了 link
P4359
发现 \(k\) 很小，考虑第 \(k\) 大的经典求法，每次取出堆顶，再塞入一些比他小的数。
考虑如何不重不漏地塞数。
考虑对每个数分组。
这里我们按照最高次幂和 \(k\) 分组，每次取出后将其某一项由最高次幂修改为小于上次操作的质数，每次最多扔入 \(P\) 个，\(P\) 为质数个数。
CF906C
朴素状压。
令 \(f_i\) 表示将状态 \(i\) 变为全部认识的最小步数。
\(O(n)\) 转移即可。
Day 3
考试。
nm 以后不冲题了，md 本来阳历全过了，因为 sb subtask 爆单了，nm。
以下是题解。
T1
赛时没仔细看，其实就是欧拉回路，字典序最小即可，用 set 或者 vector 存个点就行。
T2
被期望骗了。
其实不是期望，是分数规划。
只写了 60，A 了再来补。
T3
直接退。
T4
我与 subtask 不共戴天。
做法比较神秘，只能处理 \(|B|\ge|P|\) 的情况（其实另外一种应该也能做，懒得想了）。
对于 \(P\) 的正反串建 SAM，把 \(A\) 的正反串的每一位和 \(B\) 的正反串扔上去跑匹配，跑出匹配位置 \(pos\)，和匹配长度 \(len\)。
最对于正反串的 SAM 使用线段树合并，但是由上到下，正串是是前缀下标加 1，反串是 \(len-i-1\)。
然后扫一遍 \(A\)，对于每一位把 \(B\) 插进去使用线段树上按点与算贡献，注意一些边界问题。
我真是天才。
Day 4
练习赛。
上午七道题，切了中心对称的 4 道题，赛后补了 6 道（懒
以下是部分题的题解。
CF623B
比较厉害啊。
考虑 \(a_1\) 和 \(a_n\) 总会有一个被剩下来，所以对于 \(a_1-1,a_1,a_1+1,a_n-1,a_n,a_n+1\) 分解质因数，然后对于每个质因数去跑 DP。
具体的，设 \(f_{i,0/1/2}\) 表示到第 \(i\) 位，删前、删中、删后的最优值，正常转移即可。
CF1139D
神笔期望。
大力推狮子：
\[E(len)=\sum_{i\ge1} P(len=i)\times i \\ =\sum_{i\ge1} P(len\ge i) \\ =1+\sum_{i\ge1} P(len>i)\\ \]又因为 \(P(len>i)=1-P(len=i)\)，所以有：
\[E(len)=1+\sum_{i\ge1}1-\sum_{d=1}^m\mu(d) \dfrac{(\lfloor \frac{m}{d} \rfloor)^i}{m^i} \\ =1-\sum_{i\ge 1}\sum_{d=2}^m\mu(d)\dfrac{(\lfloor \frac{m}{d} \rfloor)^i}{m^i}\\ =1-\sum_{d=2}^{m}\mu(d)\dfrac{\lfloor \frac{m}{d} \rfloor}{m-\lfloor \frac{m}{d} \rfloor} \]直接算即可。
CF1260E
显然 \(n\) 是必然要买的，考虑让他收益最大化，也就是消灭 \(\dfrac{n}{2}\) 个人，那么剩下 \(n-1\) 个人中，会剩下 \(\dfrac{n}{2}\) 个人，我们需要让最强的人花费最小即可。
递归下去就是最优答案。
所以开一个堆，里面存打不过的人的花费，依次加入，每次遇到 \(2\) 的整数次幂取出堆顶即可。
Day 5
考试。
怎么说呢，
咱就是说，
能不能，
害，就是说，
别卡常了行不行啊！！！！！
T1
数位 DP 赛事胡了个 70 就走人了，然后被卡成了 40。。。
\(O(n)\) 但是带 \(2^{10}\) 巨大常数做法很显然，现在考虑真正的 \(O(n)\)。
容易发现状压的原因是因为在有上界限制下，之前选了哪些数对当前状态是有后效性的，所以需要状压。
但是。
在没有上界限制下，是无后效性的，所以只记忆化无上界即可。
T2
比较神秘。
赛时考虑了一个线段树上维护 3 值的做法，巨大难写。
实际只用一个维护区间最值的线段树即可。
考虑现在有一个长为 \(n\) 的递增序列，显然从后往前暴力扫一遍相邻的三个数就行。
那么在无法形成三角形的情况下，肯定有 \(b_{i-2}+b_{i-1}\le b_i\) 又因为 \(b_{i-2}\le b_{i-1}\) 所以有 \(b_{i-2}\le \dfrac{b_i}{2}\)，非法情况的下降速率是 \(\log V\) 级别的。
暴力查找最大值即可。
T3
多项式，不会。
T4
神秘，还卡常。
赛前 tby 说是园方树，直接给我唬住了，以为是园方树上容斥之类的神秘东西，结果发现直接建边双树然后淀粉质即可。
Day bleem
我也不知道为什么加在 4 后面了。
今天是 noi Day2。
本来觉得 HE 能来个 Au 的，但看来还是差一点。
看到了很多强大选手退役了也是很惋惜，但是自己明年可能连队都进不了，更加惋惜。
但但是是明年 hsr 联动 fsn ✌。
但是如果退役的话小 ez 会给你提前开学，可能玩不上。
没退役的话，会给你补课，也玩不上。
唉，玩不上，哎。
拜谢 APJ，fsl，耳朵龙，LAP，haosen，ReTF，Estelle_N，yswn，jijidawang，5k（排名不分先后）。
标签：线段,sum,邮寄,len,Day,rdf,即可,考虑,mx From： https://www.cnblogs.com/NtYester/p/18314861