\(\text{Day1}\)，\(12.11\)
上午被 \(\text T1\) 整破防了，用 unordered_map 被卡常了。
- \(\text{T1}\)
记答案是 \(f(h,n)\)，考虑怎么转移。
\[f(k,n)=-\sum_{d|n,d \neq 1} f(\dfrac{h}{d},\dfrac{n}{d})\mu(d)-\sum_{d|h,d \neq 1} f(\dfrac{h}{d},n)\mu(d) \]具体意义就是考虑最早拼凑出的前缀长度，第一个 \(\sum\) 是考虑 \(\text{ minprefix}=h\) 的情况，枚举循环节数量，第二个则是枚举最短前缀。
发现边界是 \(h=n\)，考虑转移过程，设 \(g(h,n)\) 表示第二种转移的 \(\prod d=h\)，第一种 \(\prod d=n\)。
\[g(h,n)=-\sum_{d|n,d \neq 1} g(h,\dfrac{n}{d})\mu(d)-\sum_{d|h,d \neq 1} g(\dfrac{h}{d},n)\mu(d) \]答案就是 \(g(\dfrac{h}{n},n)\)。
容易发现状态数是 \(O(\sqrt h)\)，预处理 \(\mu (d) \neq 0\) 的因子然后记忆化就可以过了。
值得一提的是，你发先上面那个式子之所以转移里面有一个 \(\mu(d)\)，是因为连续转移相同的两次，那么考虑将 \(\dfrac{h}{n}\) 和 \(n\) 质因数分解之后容斥会简单的多。
- \(\text T2\)
考虑对于一个守望者拆分到线段树上 \(O(\log n)\) 个区间。
线段树上每一个节点开一个单调栈，维护守望者，相同的守望者缩在一起处理，这一部分可以用并查集实现。
考虑一个加法操作的影响。
对于一个节点而言，如果作为叶子被递归到，那么相当于全局 \(+v\)，否则需要从左右儿子 \(\text{pushup}\) 上来。
对于每一个守望者维护 \(h_i\) 表示历史最大值。
\(\text{pushup}\) 和 \(\text{pushdown}\) 都挺好写的。
- \(\text T3\)
建出后缀自动机。
考虑一个节点 \(p\)，相邻的 \(\text{endpos}\) 的最大值是 \(m\)，那么 \(\text{str}(p)\) 中符合条件的字符串需要满足 \(\text{len} \geq m\)。
考虑正反串分别跑一次 KMP，设得到的数组是 \(a_{1\dots n}\) 和 \(b_{1 \dots n}\)。
设节点 \(p\) 最左边的 \(\text{endpos}\) 是 \(L_p\)，最右边的是 \(R_p\)。
那么需要满足 \(\text{len}\geq L_p-a_{L_p}\)，设最严的限制是 \(\text{len} \geq T\)。
然后相当于查询区间 \([R_p-\text{len}(p)+1,R_p-T+1]\) 中 \(b_i \leq R_p+1\) 的有多少个。
二维数点就做完了。
\(\text{Day2}\)，\(12.12\)
小根堆咋做啊？？？麻了。
- \(\text T1\)
建出大根堆的笛卡尔树，然后考虑每次操作会删掉儿子数量没有达到满的状态的电。
设 \(f_{i,j,0/1}\) 表示子树大小为 \(i\)，删了 \(j\) 次，再删一次可以全删掉，最后剩下的是不是边界点。
推推转移。
- \(\text T2\)
设 \(f_{i,j,k,0/1}\) 表示第一条路径到了 \(i-j\)，第二条到了 \(i-k\)，\(i-2,i-1,i\) 三个位置中剩下的那个有没有被占。
太妙了！！！
然后注意转移不要重复就行了。
- \(\text T3\)
对于每一个颜色建出虚树，然后二维数点，有情况要用重剖。
\(\text{Day3}\)，\(12.13\)
讲 dp，但是体验很差。
- \(\text{QOJ7649}\)
设 \(f_{i,j}\) 表示序列长度是 \(i\)，出现了 \(1 \sim j\) 中的数每一个至少一次的不存在 120 的方案。
dp 可以通过枚举最大值位置和左边最大值实现。
- \(\text{AGC022F}\)
坐标极大，考虑每一个点最后对于答案的贡献。操作 \(a,b\)，那么我们就连边 \(b \to a\)。
可以发现 \(x\) 对于答案的贡献是 \(A_x2^{B_x}x\)。
其中 \(B_x\) 是 \(x\) 的深度。
考虑 \(A_x\) 变化——被儿子和兄弟影响。
一种方案只会被这一层的奇数儿子节点数量最少的情况计算。
设 \(f_{i,j}\) 表示考虑完了 \(i\) 个点，目前最后一层有 \(j\) 个儿子数量是奇数的点。
考虑枚举这一层点数和最后和父亲节点符号相同的点数量 \(k,p\)。
\[f_{i,j}\times \binom{n-i}{k}\times \binom{k}{p} \to f_{i+k,|\frac{k-j}{2}-p|} \]每一层的奇数节点符号一定相同，不然就违背了奇数儿子数量最少的原则。
可以优化到 \(O(n^3)\)。
- \(\text{CF1500F}\)
考虑设 \(d_i=h_{i+1}-h_i\)，那么 \(w_i=\max\{|d_i|,|d_{i+1}|,|d_i+d_{i+1}|\}\)。
设 \(f_{i,j}\) 表示考虑完了 \(d_{1\sim i}\)，\(|d_i|=j\) 是否可行。
转移如下：
\[f_{i,w_i} \to f_{i+1,x \leq w_i} \]\[f_{i,x\leq w_i} \to f_{i+1,w_i} \]\[f_{i,x \leq w_i} \to f_{i+1,w_i-x} \]发现对于 \(f_{i,*}\)，值为 \(1\) 的是一段区间肯定是一段区间加上若干个单点。
用 set 或者 deque 维护即可。
- \(\text{P7213}\)
设 \(c_{0/1}\) 表示后缀有多少个不留下/留下的点。
设 \(f_{i,j}\) 表示考虑完了后面 \(i\) 个数，\(\text{mex}=j\) 的方案，\(g_i\) 表示拿 \(1,1,2,2,3,3\dots i,i\) 选 \(i\) 个最后构成 \(1 \sim i\) 的方案数。
如果，\(i\) 最后没有剩下来，也就是说 \(a_i \leq j\)，选数方案是 \(j-c_0\)。
否则，考虑 \(a'_i =j+1\) 的话，我们枚举一个 \(k\) 作为最后的 \(\text{mex}\)，方案数是 \(\binom{c_1-j}{k-j-1}\times (k-j+1)\times g_{k-j-1}\)。
\(g\) 的转移比较简单。
- \(\text{AGC021F}\)
考虑设 \(f_{i,j}\) 表示 \(i\) 行的矩阵，有 \(j\) 列，且没有非空行的方案数。
自己推式子去。
\(\text{Day4}\)，\(12.14\)
考试时估分：\(100+100+35=235\)，最后 \(100+10+15=125\)。
挂了快一半的分（
- \(\text T1\)
考虑设 \(a_i\) 表示 \(i\) 的覆盖次数。
显然只需要考虑 \(a_i \leq 2k\) 的位置。
拿出来 dp，设 \(f_{i,j,S}\) 表示考虑了前 \(i\) 个位置，选了 \(j\) 个区间，集合为 \(S\)，转移可以做到 \(O(1)\)。
- \(\text T2\)
发现欧拉图和完全图无解。
然后可以通过构造不改变其连通性，然后最后树是好做的。
注意下细节。
- \(\text T3\)
不想改正解（
\(35\) 就直接考虑枚举一个点分裂开环然后三分就行。
\(\text{Day5}\)，\(12.15\)
考场估分：\(80+60+25=165\)。
最后 \(80+30+25=135\)。
怎么写了个线段树和倍增 LCA 被卡了 \(20+30=50\) 分啊。
- \(\text T1\)
复杂度 \(O(n \log n)\) 被卡常了。
把区间加区间求和线段树换成树状数组就过了。
考虑枚举 \(\text{mex}\) 然后统计贡献。
然后问题就变成了矩形加，然后矩形求和的形式，线段树维护历史版本和即可。
- \(\text T2\)
考虑第一问实际上需要求 \([i+1,n]\) 中距离 \(i\) 最远的点的距离。
然后第二问要找一个距离最大且权值最小的点。
可以线段树维护直径，考虑以权值为下标，然后线段树二分即可。
- \(\text{T3}\)
还挺妙的。
考虑建图，如果一个 \((x,y)\) 选了，分讨右边和上面是否有障碍连通块，然后连边求路径数。
不是很会描述啊，虽然是不想写就是了。
\(\text{Day6}\)，\(12.16\)
听字符串。
感觉又学了一遍 exKMP。
复习了下 SAM，感觉字符串不会一点，得找个时间加训。
- \(\text{CF1801G}\)
对于每一个前缀处理出答案，容易用 AC 自动机实现。
然后线段树上二分找到最靠右的跨过去的字符串然后发现是要查询一个后缀包含的字符串数量。
一样用 AC 自动机预处理出来就好了。
\(\text{Day7}\)，\(12.17\)
THUPC，YZJ 太 C 了！！！
感觉没啥贡献，最后 \(85\) 名。
\(\text{Day8}\)，\(12.18\)
\(\text{T1}\) 不会构造方案，彩笔实锤了。
YZJ 切了 \(\text{T2}\) ！！！膜拜了。
- \(\text T 1\)
考虑答案是 \(\binom{n}{2}-\sum \binom{d_i}{2}\)。
容易用 \(O(m \ln m)\) 的容斥求出 \(d_i\)。
构造考虑找一个度数最大的点和一个连向它的点必然有解。
- \(\text T2\)
u1s1 没怎么听懂 YZJ 那个做法。
只好补 zak 的做法了。
考虑容斥掉 \(\texttt{<}\)。
然后每一个段之多有一个 \(p_i=i\) 的位置，考虑以此为分界，每一段拆为前半部分和后半部分，如果不存在 \(p_i=i\) 的，那就 \(p_i>i\) 是前半部分，剩下的是后半部分。
在两部分之间来回转移即可，转移式子有点多。
- \(\text T3\)
神秘，直接用了 unputdownable 的做法。
大概是 dfs 出来一颗树，然后可以接起来。
\(\text{Day9}\)，\(12.19\)
我们的场啊。。。那不说了。
\(\text{Day10}\)，\(12.20\)
水+水+？场了这下。
- \(\text T 1\)
直接容斥，设 \(f_i\) 表示容斥了 \(1 \sim i\) 的区间，然后 \(i\) 容斥了的贡献，转移 \(O(k)\)。
- \(\text T2\)
找出直径中心，然后找出每一个部分的合法点数，发现本质不同只有 \(O(\sqrt{2n})\) 种，对这个矩阵快速幂即可。
- \(\text T3\)
啊？
\(\text{Day11}\)，\(12.21\)
dx 讲 ds。
最后就学了下 KTT。
\(\text{Day12}\)，\(12.22\)
字符串不会一点实锤了。
- \(\text T1\)
简单题，找到度数最大的点的度数即可。
- \(\text T2\)
一波推式子之后发现可以 FWT 优化 dp。
然后这个可以过。
- \(\text T3\)
建一个 SAM。
然后对于一个节点 \(x\)，我们只关心 \(\text{endpos}\) 集合里最大的和最小的，然后发现贡献是区间取 \(\max\) 和区间对一个等差数列取 \(\text{max}\)。
\(\text{Day13}\)，\(12.23\)
没挂一分的场！！！
- \(\text T1\)
建出 Kruskal 重构树，然后贡献随便算一算就行了。
- \(\text T2\)
考虑答案不超过 \(O(n \ln n)\)。
我们可以暴力找答案，每次贪心选取能选的最长的。
如果发现选取的全是 \(0\)，那么有问题，我们需要调整，那么我们找到前面选取的第一个有 \(\geq 3\) 个 \(1\) 的段，然后从中分裂出两个 \(1\)，然后容易证明这样调整是最优的。
- \(\text T3\)
比较两个区间可以主席树。
然后考虑随机 \(n\) 个区间然后找一个离 \(k\) 最近的，然后做完了。
期望复杂度 \(O(n \log^2 n)\)。
\(\text{Day14}\)，\(12.24\)
OMG，XJ 场。
- \(\text T1\)
随便 dp 一下。
联考总结如下：
总而言之，感觉联考的时候并没有处于一个考试的状态，策略上也有问题，经常出现死磕一个题然后一整场都崩掉的状态。
然后发现自己在 dp、构造、字符串方面还有些欠缺，要自己查漏补缺。
标签：text,T2,T3,然后,T1,考虑,杭州,集训 From： https://www.cnblogs.com/OccasionalDreamer/p/18012061