Day 1
有点烦。2h 只会 D 的次低档暴力。
T1
答案和连续段有关，所以是一堆卡特兰数乘起来。
T2
可以发现 $SG_x(i)=i\bmod {(x+1)}$。现在就是要对于每个 $x$ 求出 $\displaystyle \bigoplus_{i=1}^n a_i\bmod {(x+1)}$。
首先扔到桶里，然后考虑倍增，预处理 $f_{i,j}$ 表示 $\displaystyle \bigoplus_{i\leq k<i+2^j} t_k\times (k\bmod{(x+1)})$。然后就可以对于每个 $x$，暴力跳查询了。查询就是把长度为 $x+1$ 的段分成 $\log$ 个区间用倍增数组差，然后总查询次数是调和级数 $\mathcal O(n\log n)$ 级别，所以总复杂度是 $\mathcal O(n\log^2 n)$。
T3
先枚举第一个不同位置，然后枚举这个位置填什么，限制是 $a_{fa_x}<v<a_x$。预处理 $f_i$ 表示 $i$ 子树内相对顺序的方案数。考虑所有填了的位置 $[1,i]$，每个点上会挂一些子树，子树的要求就是全部 $\geq a_x$。
值域从大到小扫一遍，初始令 $tot=0$，如果这个值没有填过则令 $tot+1$，遇到一个 $[1,i]$ 中出现过的值就乘一个 $\binom{tot}{siz-1}$，然后 $tot-siz$。这样复杂度是 $\mathcal O(n^3)$。
考虑优化，不需要枚举 $x$ 这个位置填什么，只需要做一遍差分，令 $v>a_{fa_x}$ 的方案数减去 $v>a_x$ 的方案数即可。这样就把 $v$ 分别挂在 $a_{fa_x}$ 的位置和 $a_x$ 的位置做两遍即可。还需要乘上父亲确定了但是自己没有确定的点的 $f$ 以及挂在同一个父亲上的子树的相对顺序。复杂度 $\mathcal O(n^2)$。
对于输出方案，可以先通过计数这一部分确定出 LCP，然后第一个位置填的不同。考虑新开一个数组 $b_i$ 表示 $\geq i$ 的值能用几个。初始 $b_i=n-i+1$。
这样新填了一个数就令 $b[a_{fa_i}+1,a_i]$ 全部减 $siz_i$。只需要保证 $b$ 非负。复杂度也是 $\mathcal O(n^2)$。
T4
全错了。
考虑确定了一个答案 $x$ 之后如何 chk。做一遍前缀和，则对于操作完的数组的前缀和，要求就是 $\forall i<j,s_j-s_i\leq x$ 并且 $\forall i<n,s_{i+1}-s_i\leq a_i$。
注意到操作次数就是 $\sum_ia_i-s_n$，其中 $a$ 是原数组，所以需要最大化 $s_n$。这是差分约束的形式，就是需要连边跑最短路。
操作次数关于答案 $x$ 显然是一个分段凸函数。随着 $x$ 的减小，操作次数先 $+1$，然后 $+2$……最后 $+n$。只需要求出来具体的分段函数就能得到答案。
设 $f_i$ 表示经过 $i$ 条 $x$ 边的最短路。看成是选择 $i$ 个区间删掉使得删掉的区间和最大，这是经典反悔贪心问题，拿线段树维护最大子段和，每次选最大的段乘一个 $-1$ 即可。
求出来 $f_i$ 之后分段函数也比较好求了。复杂度是 $\mathcal O(n\log n)$。
感觉就是眼高手低，首先做不到一眼全看透。然后想到一点正解，感觉没救就不想了，然后就开始对着错误做法乱弄。说不定把思路写写，写出来就会了。
Day 2
T1
建一个图表示大小关系的限制，求一下拓扑序即可。
T2
先删开头结尾相同的字符。然后剩下的串分成四部分 $A_1,A_2,A_3,A_4$，假设 $A_2+A_4$ 是选择的回文串（正反做两遍这个就考虑到了所有情况）。
先跑一遍 manacher 预处理每个点为回文中心的最长扩展长度 $f_i$。
假设回文中心在 $A_4$，则枚举回文中心 $i$，要求 $i-(n-i)$ 前面存在一个 $j$ 满足 $[j,n]$ 的 border 长度 $\geq n-i-f_i$，可以求一遍 kmp 解决。
假设回文中心在 $A_2$，还是枚举中心 $i$，要求 $j+nex_j\geq i-f_i$，其中 $nex_j$ 是 $[j,n]$ 的 border 长度，求满足这个的最小的 $j$。这个可以看成是每个 $j$ 都做了一个前缀 chkmax，也可以简单解决。
T3
正数一定全选，那就是要花最小的代价走到终点。设 $f_{i,0/1}$ 表示当前走到了 $i$ 的上/下列上的最短路，可以转移到 $f_{[i-m,i_m],opt^1}$。
因为是点权最短路，所以只有第一次激活某个点才是有用的。所以不需要什么优化建图，只需要简单维护两个指针表示当前激活了两个前缀，每次向右移即可。复杂度 $\mathcal O(n\log n)$。
T4
感觉我太菜了。
首先预处理 $f_i$ 表示点 $i$ 的期望深度。
$d(u,v)$ 拆成 $dep_u+dep_v-2dep_{lca(u,v)}$，前两者容易统计，考虑如何统计后者。
希望能够处理出 $g_i$ 表示以 $i$ 为 $lca$ 的点对数。但是两个点向上走，以 $i$ 为祖先的概率是不独立的。考虑一种统计方式：两个点都是任意往上走，在第一次相遇的位置把他们统计。
先统计 $h_j$ 表示 $i$ 是 $j$ 祖先的概率。初始令 $g_i=(1+\sum_j h_j)^2$。然后考虑每个点对在第一次相遇的位置归类，需要的是第一次相遇恰好在 $i$ 的点对，所以需要减去在其他地方相遇的点对。那就是要减去所有 $h_j^2g_j$。平方是因为有两个点，走的是两条可能不同的路径。复杂度是调和级数（？）
Day 3
T1
懒得喷。
是若干个斐波那契数乘起来，暴力记忆化搜索处理 $f_i$ 表示 $i$ 是否合法，这样可以求出来 $nex_i$ 表示 $i$ 拼的第一个斐波那契数最大是多少。
T2
搞不懂。
暴力是 $\mathcal O(n\log^2 n)$。考虑一维以 $L$，第二维是 $F$，这样就是要找到 $y$ 后面 $R\geq x$ 的第一个位置状物，可以线段树上二分。这样就是一个 $\log$。
T3
我傻逼。
答案是若干个段，一段内部是连续的给很多人理发，段之间不交。现在要处理从第 $i$ 个人开始，连续给 $j$ 个人理发的最大收益。
从前向后扫，每一时刻只保留 $m-1$ 个人，人多了就删去收益最小的。然后取出收益最大的人拼在后面继续加入新的人。可以拿一个堆维护，复杂度 $\mathcal O(n^2\log n)$。
正确性就是当前时刻最多就只有 $m-1$ 个人对未来有贡献。然后如果先给后来的人理了再给前面的人理发可以看成是进行了一次类似反悔的东西，在前面插入了这个人。
T4
还是我傻逼。
设 $f_i$ 表示点 $i$ 的答案，则：
\[f_i=\min(\max_{(i,j)}f_j,\min_{(i,j)}f_j+1)\]考虑逐层确定答案，即先确定答案为 $0$ 的，然后是为 $1$ 的……首先 $t$ 的答案为 $0$。然后假设处理到了第 $i$ 层，则能一步走到答案为 $i-1$ 的点的点答案就是 $i$。这是考虑了第二种转移。
然后考虑第一种转移，这个就是怎么走都只能走到答案 $=i$ 的点的点。可以先把答案 $<i$ 的点删掉，然后答案 $=i$ 的点的出边删掉，然后在这个图上跑 SCC，做一遍拓扑排序就行了。复杂度 $\mathcal O(n(n+m))$。
Day 4
赢！
T1
转移方程：
\[\begin{aligned} f_i&=\sum_{j=1}^i f_{i\bmod j}+1\\ &=\sum_{j=1}^i f_{i-\lfloor\frac i j\rfloor j}+1 \end{aligned}\]对于 $j\leq \sqrt n$，可以暴力计算。对于 $j>\sqrt n$，$\lfloor\frac i j\rfloor$ 只有 $\sqrt n$ 种不同的取值并且都 $\leq \sqrt n$。对于 $\lfloor\frac i j\rfloor$ 相同的一类，就是一个间距为 $\lfloor\frac i j\rfloor$ 的一个区间求和，可以简单预处理 $s_{i,j}$ 表示 $f_i+f_{i-j}\dots$ 就能 $\mathcal O(1)$ 查询了，复杂度 $\mathcal O(n\sqrt n)$。
T2
把每个点拆成两个点表示 $x$ 和 $-x$ 的取值，连边 $(x,y)$ 表示 $x$ 点的值小于 $y$ 点。无解当且仅当有环。然后瞎写个拓扑排序啥的就对了（？）
T3
从 $a$ 中生成一个子序列 $b$，就是从 $0$ 开始不断找到 $a$ 中第一次出现 $b_1$ 的位置，然后找到这个位置之后 $b_2$ 第一次出现的位置……对这个东西进行 DP。
设 $f_{i,j,k}$ 表示当前在区间 $[l,r]$ 选了 $k$ 个子序列，并且第 $k$ 个子序列在区间 $[l,r]$ 只选了 $l,r$。转移就是若干段 $f_{x,y,k-1}$ 拼起来，并且每个 $a_y$ 都不等于 $a_r$（不然可以生成一个更有前途的子序列）。暴力做转移是 $\mathcal O(n^5)$。
考虑优化一下，先预处理 $h_{l,r,k}$ 表示用 $f_{x,y,k-1}$ 拼出来区间 $[l,r]$ 的方案数。然后初始令 $f_{l,r,k}=h_{l,r,k}$，然后做一个容斥，枚举 $[l,r]$ 中的段第一个 $a_y=a_r$ 的位置，即减去所有满足 $a_i=a_r$ 的 $f_{l,i,k}h_{i,r}$，这样复杂度就是 $\mathcal O(n^4)$ 了。
T4
考虑生成三个大小为 $2$ 的可逆矩阵 $f_0,f_1,f_2$ 并求出他们的逆 $f’_0,f’_1,f’_2$。
这样判定一个序列是否合法，如果是奇数位置则该位置的矩阵是 $f_{a_i}$，偶数是 $f’_{a_i}$，只需要判断整个序列矩阵的乘积是否为 $I$。
这个题也能做，拿一个 map 存下所有前缀把一个字符 $i$ 替换成一个字符 $j$ 的所有矩阵。$i+1$ 的时候应当里面所有元素统一乘一个矩阵，用懒标记实现。查询也是求逆之后直接查询，复杂度 $\mathcal O(n\log n)$，可以 $\mathcal O(n)$。
Day 5
小赢不算赢。
T1
给 $\mathrm{\color{black}{d}\color{red}{efinieren}}$ 咔了。
暴力 DP 就是先二分答案然后 $f_{i,j}$ 表示考虑了高 $i$ 位，当前剩了 $j$ 个 $2^i$ 的最大收益，转移是一个卷积，但是可以发现他是凸的，所以可以归并排序，这样是 $\mathcal O(n\log^2 n)$。
然后考虑从低向高做，先二分答案，如果这一位是 $1$ 就选一个元素。
然后向上一位的时候把当前所有剩的从大到小排序，不断吧两个相加合并上去。只剩一个的话也要合并上去。这样就是对的，复杂度 $\mathcal O(n\log V)$。
T2
唐氏题。
先二分答案，然后 $f_{i,j,0/1}$ 表示前 $i$ 个数，有 $j$ 个 $1$，当前连续段是 $0/1$ 并且保证前面都合法时，当前连续段的最短长度。这样是 $\mathcal O(n^2\log n)$。
打表可以发现一些性质：一定是一个区间合法，并且区间形如：
\[f_0:x\;y\;y\;y\;y\;y\;y\;y\;y\;y\;*\\ f_1:*\;y\;y\;y\;y\;y\;y\;y\;y\;y\;z\]别的位置都没有值，星号表示也没有值。转移可以通过分类讨论实现，一层的信息是 $\mathcal O(1)$ 的可以全都存下来，复杂度 $\mathcal O(n\log n)$。
T3
挺套路的但是我挺傻逼的。
首先环长相等。简单观察之后可以发现只会走边权为 $0$ 和 $1$ 的边。这样环数很少就可以暴力跑一个 Floyd 之类的。
如果环长比较小，观察 $x$ 怎么变到 $y$ 的：$((((((x\times K)\times K)+1)\times K)+1)\times K)$。
注意到只有一开始乘若干个 $K$ 和 $x$ 有关，后面 $+1,\times K$ 都和 $x$ 无关，所以先枚举 $x$ 乘了多少个 $K$。然后预处理 $d_i$ 表示 $0$ 到所有点的最短路，之和差值有关。
设块长为 $B$，环长 $>B$ 的时候用第一种，否则用第二种，复杂度是 $\mathcal O(\frac{n^3}{B^3}+qB)$。取 $B=2000$ 就挺优秀的。
T4
很唐氏的数据结构，但是来不及写。
考虑暴力做操作 $3$ 怎么做：正着倒着扫一遍就行了。
维护连续段，记录当前连续段是上升段还是下降段。一次区间加的操作只会分裂出来 $\mathcal O(1)$ 个区间，并让 $\mathcal O(1)$ 个相邻位置的差大于 $k$。操作 $3$ 的时候，找到区间中所有可能不合法的位置，发生了 chkmin 就一定会让连续段数减一，所以复杂度是对的。需要支持区间赋值成等差数列啥的，比较恶心。
Day 6
T1
$f_{i,j}$ 表示 $i$ 子树内留下来的人水平是 $j$ 的概率，暴力转移。
T2
考虑给定了串如何 chk：$f_{i,j}$ 表示前缀 $i$ 能否被 $S[1,j]$ 和 $T[1,i-j]$ 拼出来。
DP 套 DP，把第二维压下来就行了。状态数很少。
T3
分治，$x_{i,0/1}$ 表示 $mid$ 选和不选的时候 $[i,mid]$ 的最大收益，$y_{i,0/1}$ 表示右边 $mid+1$ 选没选，$[mid+1,i]$ 的最大收益。都把选了的对不选的取一个 $\max$。
要求 $\sum \max(x_{i,0}+y_{i,1},x_{i,1}+y_{i,0})$。都减一个 $x_{i,0}+y_{i,0}$，变成 $x_{i,0}+y_{i,0}+\max(x_{i,1}-x_{i,0},y_{i,1}-y_{i,0})$，排序之后求一下就行了。
T4
BIT 扫四遍求出来 $d_i$ 表示 $i$ 到最近传送阵的距离。
性质是如果 $d_i>d_j$，并且 $i$ 用了传送阵那 $j$ 也一定用。所以可以二分答案，枚举前缀。曼哈顿距离转切比雪夫距离之后，求出后缀矩形的交。
再把后缀矩形扩大 $mid-d_i$，看一下内部是否有传送阵即可。复杂度是 $\mathcal O(n\log^2 n)$。
比较牛的做法：设 $ans_i$ 表示选取前缀 $[1,i]$ 走传送阵的最小答案。先把序列 random-shuffle 一下，那 $ans_i$ 的前缀最小值期望个数就是 $\mathcal O(\log n)$ 级别。
扫到一个点，维护当前最小答案。如果当前最小答案在这里进行检查的时候不合法就直接跳过，否则在这个点上二分一遍，每次暴力矩形数点。复杂度是 $\mathcal O(n\log n+log^3 n)$。
Day 7
T1
如果 $n$ 是奇数，选一个最大的 $k$ 满足 $3^k\leq n$。
如果 $n$ 是偶数，将 $n$ 除二，并把以后的答案都乘 $2$。
T2
唐氏题。手玩一下发现是初始位置右边的 $1$ 的位置和减去左边的 $0$ 位置和，拿线段树瞎维护一下就行了。
T3
唐氏题。容斥，变成选若干个区间不被覆盖，转移可以用线段树优化，懒得写了，反正是答辩。
T4
不难。首先同一种颜色所在两个柱子连边，就会有若干个链和若干个环。
考虑一个颜色，两个出现位置都在柱子顶端的话是不好处理的。称这个东西为坏位。
如果一个链没有坏位，他就不需要占据额外的空位，并且可以自己内部操作来创造一个空位。称这个为好链。
如果链上有坏位，则可以找到第一个坏位，用一个当前的空位吧这个消掉，然后坏位左边就是一个好链，可以消掉来新增一个空位。称这种为坏链，则坏链能被消空的条件就是存在至少一个可用空位。
如果换上没有坏位或者一个坏位，则需要一个可用空位。否则先拆一个坏位，就变成了坏链，一样处理即可。
Day 8
我咋这么傻逼啊。
T1
构式题。通过分类套路可以转化为 $\mathcal O(1)$ 次以下问题：每个点有一个目标位置，需要匹配使得移动步数不变，并且字典序最小。
对于一个连续的，都向左走的段，把他们缩在一起。然后从由往左扫，遇到原位置就加入可用点，遇到要删的位置就删去一个最大的可用点。
都向右的同理，从左往右扫，加点一样，删点就删去最小的可用点。拿一个堆维护一下就行了。
T2
感觉我还是有点唐了。
考虑从 $1$ 走到 $x$ 的过程中的点 $a_1,a_2\dots a_k$，边权 $b_1,b_2\dots b_{k-1}$。其实只关心的是 $b$ 的后缀最小值。
假设 $b_x$ 是后缀最小值点，$b_{y}$ 是上一个后缀最小值点，则 $a_{y+1}\sim a_x$ 旁边，大于 $b_x$ 的边需要全部被走到。
对这个东西跑最短路，$f_{i,j,k}$ 表示当前走到了 $i$，上一个后缀最小值的 $b$ 是 $k$，当前的最小值是 $j$。
发现第三维是没有用的，选到了错的一定不优秀。可以删掉。
T3
凸的。差分值很小。暴力自卷积 $\log$ 次，拿桶维护差分值。
T4
挺唐的。考虑枚举 $j$，维护每个左端点 $f_i$ 表示，最大的右端点使得 $[j+1,r]$ 内的数都在 $f_i$ 里面出现过。维护 $g_i$ 表示，最小的右端点使得 $[i,j]$ 里的数都在 $[j+1,r]$ 里出现过。
$g$ 是好维护的，是 $\max_{i\leq k\leq j}nex_k$。$f$ 不是很好维护，但是可以反着维护另一边的东西，可以把 $f$ 也变成 $\mathcal O(n)$ 次线段树区间加的操作。
要求的是 $\sum \max(f_i-g_i,0)$。注意到 $f$ 是递减的，$g$ 是递增的，可以线段树上二分找到合法区间。复杂度 $\mathcal O(n\log n)$。
Day 9
T1
维护前缀和，看成是找 $i,j$ 使得 $\abs(f-\frac{s_i-s_j}{i-j})$ 最小，维护一下凸包啥的就行了。
T2
连接若干个点之后，手玩发现两个点之间的最短路比较简单。先二分答案，$f_{i,j}$ 表示第 $i$ 个点上用了第 $j$ 次合并，此时 $[1,i]$ 所有点到 $i$ 最短路的最大值最小是多少。需要处理转移系数啥的。
T3
不会。
T4
唐氏题。
找到 $i$ 后面 $k$ 个颜色相同的东西，然后去除最小值到每种重复的颜色只剩一个就行了。
Day 10
T1
从小到大加入树中的边，维护 $f_i$ 表示，只保留 $[1,i]$ 中的点，此时树有多少个连通块。这样新加入一条边的时候，就是取删除这个边左右连通块中点编号最小值的较大值 $x$，然后令 $f[x,n]$ 全部减一，可以差分。
然后每次形如，$g_i\overset +\leftarrow f_i\times \min(i-1,m)$，可以差分之后摁维护一下。
T2
太难了。
先生成一个 $[1,50]$ 的递增序列，然后钦定后面填的互不相同，那就是要求上升子序列个数是 $n$。
从小到大填数，填在开头是 $+1$，填在结尾是 $\times 2+1$，可以递归做。
T3
困难。
只能有一个 SCC。求出 dfs 树，对于一条返祖边，他覆盖的点以外的点全部都不合法。
对于一条后向边或者横叉边，假设其为 $(x,y)$，如果 $y$ 能通过一条返祖边到达 $\text{LCA}(x,y)$ 的祖先，则 $(x,y)$ 路径之间的点都是不合法的。
可以先处理所有返祖边，然后 dfs 一边算贡献。
T4
感觉比 BC 都简单。纯代码题。
答案是好算的，找到最高的，不完全相同的位，分两边做，一个 trie 就能支持找最小值。
然后是输出方案，瞎贪心一下，如果左边还有剩的点则要求两边至少有一条通路，维护这个就行了。
Day 11
T1
上界是 $S$ 到 $T$ 的最短路。构造可以达到上界：先 bfs 一遍，边 $(u,v)$ 的颜色是 $\min(d_u,d_v)$。
T2
容斥维护一个段不出现一个颜色的方案数。对于一种颜色，若相邻两次出现位置是 $a_i$ 和 $a_{i+1}$，则其对长度为 $j$ 的区间 $(j<a_{i+1}-a_i)$ 的贡献是 $a_{i+1}-a_i-j$，拿 BIT 瞎维护一下就行了。
T3
首先核心性质是，从 $i$ 出发开车到 $j$ 的时候，要么油箱是满的，要么油箱里装了恰好够到达 $j$ 的油。这个可以简单贪心证明。
然后就可以再每个点上把油量离散化一下，跑 DP 就行了。
T4
容斥，钦定若干个点度数是 $0/1$，可以只考虑钦定度数是 $1$ 的最后做一遍类似高维前缀和的东西。
钦定度数是 $1$ 的内部会有若干匹配，可以预处理 $f_S$ 表示 $S$ 内部两两匹配的方案数。
然后没有内部匹配的，假设 $S$ 是没有限制的点集，$T$ 是钦定度数为 $1$ 的，需要 $T$ 中每个点都向 $S$ 中连一条边，暴力可以做到 $3^n$。