0%

九省联考2018乱写

九省联考2018乱写

省选联考题比ZJOI阳间得多。。。

鸣谢red的“遗产”

Day1T1

首先直接记忆化最右侧的轮廓就能有$O(m^n)$.

然后有用的状态一定是最右侧单调不增的,有效状态数仅为$\binom{19}{9}=92378$.随便hash/std::map 记忆化一下即可。

My code

Day1T2

$d_i$互不相同的随便贪就行,所以直接讲正解了:

依次考虑1~n.对于当前考虑的$i$,若其能填$x$那么$\forall y<x,y$一定也能填,即有单调性。那么考虑二分。考虑每个已经确定了填的数字的点的要求形如:至少要留有$a_i$个不小于$b_i$的数字($a_i$为其所有未确定的儿子的子树大小之和)。那么就是单点修改,询问全局最小后缀和。用线段树维护之。复杂度$\mathcal O(n\log^2n)$.

My code

Day1T3

比较nb,另外写了篇文章:Link

Day2T1

写了个暴力Dinic只有60分。

正解是利用$C$较小的性质。

第一问只需对每个人枚举过去求就好了,$O(n^3).$

第二问可以二分,但更优的做法是,做第一问时就顺便处理掉:若$i$无法与第$p$志愿匹配,那么考虑一条无法增广的交错路,我们一定可以顶掉上面某个人然后就能匹配了,显然顶掉编号最大的人最优。对所有$p$取一个最小值即可,复杂度不增加。

My code

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)$.

My code

Day2T3

这题超级没有素质,SAM上线段树合并谁都会,却偏要来个毒瘤分类讨论。

代码是没有的。