九省联考2018乱写
省选联考题比ZJOI阳间得多。。。
鸣谢red的“遗产”
Day1T1
首先直接记忆化最右侧的轮廓就能有$O(m^n)$.
然后有用的状态一定是最右侧单调不增的，有效状态数仅为$\binom{19}{9}=92378$.随便hash/std::map 记忆化一下即可。
Day1T2
$d_i$互不相同的随便贪就行，所以直接讲正解了：
依次考虑1～n.对于当前考虑的$i$，若其能填$x$那么$\forall y<x,y$一定也能填，即有单调性。那么考虑二分。考虑每个已经确定了填的数字的点的要求形如：至少要留有$a_i$个不小于$b_i$的数字（$a_i$为其所有未确定的儿子的子树大小之和）。那么就是单点修改，询问全局最小后缀和。用线段树维护之。复杂度$\mathcal O(n\log^2n)$.
Day1T3
比较nb，另外写了篇文章：Link
Day2T1
写了个暴力Dinic只有60分。
正解是利用$C$较小的性质。
第一问只需对每个人枚举过去求就好了，$O(n^3).$
第二问可以二分，但更优的做法是，做第一问时就顺便处理掉：若$i$无法与第$p$志愿匹配，那么考虑一条无法增广的交错路，我们一定可以顶掉上面某个人然后就能匹配了，显然顶掉编号最大的人最优。对所有$p$取一个最小值即可，复杂度不增加。
Day2T2
题面看起来非常阴间，实际上就是要选恰$k+1$条不相交的链（允许退化成点），最大化权值和。
那么我们容易有个dp，$f(u,x,0/1/2)$表示考虑$u$的子树，已经选了$x$条链，且$u$与子树中连了0/1/2条边 的最大权值和。
这样是$O(n^2)$,限制上界似乎可以做到$O(nk)$.
这样没啥优化前途。考虑如果我们一条一条的选链（允许反悔），那么权值的增量是递减的（如果不是，即存在某次$+a$,下一次$+b$,我们可以变成这次$+b,$下次$+a$），也就是$\max f(1,x,0/1/2)$关于$x$是凸的。
那就呼一个wqs上去，变成选若干条链，最大化权值和-链数量×某个常数。还是可以dp的，$f(u,0/1/2)$表示考虑$u$的子树，且$u$与子树中连了0/1/2条边 的最大权值和，顺便要统计一下选的链的数量。
复杂度$\mathcal O(n\log w)$.
Day2T3
这题超级没有素质，SAM上线段树合并谁都会，却偏要来个毒瘤分类讨论。
代码是没有的。