建议去My blog 查看

CSP2019 Day2 题解

[HTML_REMOVED]

T1 Emiya 家今天的饭

考虑容斥，答案为每一行至多取一个的总方案数减掉每一行至多取一个且存在一种食材做了超过一半的方案数。

超过一半的食材只能有一个，那么可以枚举这个食材$x$，然后做dp：[HTML_REMOVED]
令$f(i,j,k)$表示考虑前$i$行，共做了$j$道菜，其中$x$做了$k$个的方案数。[HTML_REMOVED]
$f(i,j,k)=f(i-1,j,k)+f(i-1,j-1,k)*(sum_i-a_{i,x})+f(i-1,j-1,k-1)*a_{i,x}$

其中$sum_i=\sum_{j}a_{i,j}$ 。注意转移时需要满足下标非负。最后$x$的贡献就是$\sum_{j=0}^n\sum_{k=j/2+1}^jf(n,j,k)$ [HTML_REMOVED]
这样复杂度是$\mathcal O(n^3m)$，有88pts。

考虑$k>\lfloor\frac{j}{2}\rfloor\Leftrightarrow 2k>j\Leftrightarrow k-(j-k)>0$

所以存个差值就好，即$f(i,j)$表示前$i$行，$x$的数量减掉别的菜数量为$j$的方案数。复杂度$\mathcal O(n^2m)$.

My code

T2

一个暴力的dp是，令$f(i,j)$表示考虑前$i$个的划分且最后一段是$(j,i]$的最小代价。
$$ f(i,j)=\min_{k<j,s_{i}-s_j\ge s_j-s_k}f(j,k)+(s_i-s_j)^2 $$
其中$s_i=\sum_{j\le i}a_j$。复杂度$\mathcal O(n^3)$.

下文中若$k<j,s_i-s_j\ge s_j-s_k$则称$k$合法。 接下来一个比较困难的地方就是发现对于合法的$k1,k2,$若$k1<k2$,则$f(j,k1)\le f(j,k2)$.

证明：（参考https://matthew99.blog.uoj.ac/blog/5299）

$\text{Lemma 1:} $对于一个单调不降序列$A(a_i\ge 0)$,若两个位置$x_1,x_2$满足$x_1<x_2,a_{x_1}-1\ge a_{x_2}+1$,则令$a_{x2}$加上1，$a_{x1}$减去1，$A$仍满足单调不降，且$\sum_{i}a_i^2$减少。

这个比较显然了。

$\text{Lemma 2:}$ 对于两个单调不降序列$B,C(b_i,c_i\ge 0)$（长度为$n$，短的可以在开头补0）且$\sum_{i=1}^nb_i=\sum_{j=1}^n c_i,\forall i,\sum_{j=1}^ib_j\ge \sum_{j=1}^ic_j$，则有$\sum_ib_i^2\ge \sum_ic_i^2$ .

$\text{Proof:}$ 考虑用Lemma1的调整，将$B$变为$C$.

也就是在满足$\forall i,\sum_{j=1}^ib_j\ge \sum_{j=1}^ic_j$的前提下，令$\sum_{j=1}^nb_j-c_j=0$

找到第一个$\sum_{j=1}^ib_j>\sum_{j=1}^ic_j$的位置$i$.（若不存在，则$B,C$相等）找下一个位置满足$\sum_{j=1}^ib_j=\sum_{j=1}^ic_j$ （记为$p$) 。容易发现这段区间中一定存在两个位置$p1,p2$满足$(b_{p1}-c_{p1})-1\ge b_{p2}-c_{p2}+1$.那么就可以上调整了。

所以最后可以将$B$变成$C$，也就得证$\sum_ib_i^2\ge \sum_ic_i^2$.

有了这玩意，在记录一个$g(i)$表示$i$的最优解的最后一个决策点到$i$的和。
$$ f(i)=\min_{j<i,S_i-S_j\ge g_j} f(j)+(S_i-S_j)^2 $$
直接做是$\mathcal O(n^2)$,把条件变成$S_i\ge S_j+g_j$,用单调队列维护即可，复杂度$\mathcal O(n)$.会爆ll，要两个ll当高精，然后卡一下空间。

My code

T3

先说一下我瞎搞的做法，复杂度2log但是5组数据在loj上最长点也就1100ms。

令$u$的父子树表示，将$u$作为树的根后，$u$原本的父亲构成的子树大小。

首先问题分为求子树重心编号和父子树重心编号。[HTML_REMOVED]
子树重心编号是个简单的问题。首先重心要么在当前点，要么在重子树中。那么记录重儿子的重心，然后暴力往上跳就好。复杂度不超过所有重链长度之和，即$\mathcal O(n)$.

对于父子树重心编号，假设当前考虑$u$,我们要求出其所有儿子的父子树重心编号。父子树的重儿子、重心可能变化很大，我们通过简单的性质和分类讨论简化这个过程。

记重儿子为$Ms,$轻儿子集合为$L$

• 首先重心在重子树中（或当前点），归纳可得重心在重链上，我们只需维护重链。
• 对于$v\in L$，其父子树的重儿子要么是父亲，要么是$Ms$，且这个重儿子的重链可以继续延伸（之后的部分不变）。
• 对于$Ms$，反正只有一个重儿子，我们暴力找。父子树的重儿子的重链同样可以继续延伸（之后的部分不变）。

那么就有一个暴力的想法，已知父子树重链，就在上面一步一步跳，若符合条件就加入答案。

但显然不能直接维护重链。考虑重链是链，我们可以在重链上倍增 找到重链上第一个点满足子树大小$>\lfloor\frac{n-size(v)}{2} \rfloor$.这里涉及到一个问题，如何求以一个点为根，另一个点的子树大小？这个可以分类讨论+LCA解决（类似换根树剖那种）。

接下来又有一个问题（然而不考虑这个问题能过样例。。还好对拍出错了）：

轻重儿子处理的顺序。 轻儿子的父子树的重儿子可能是$Ms$，即求解轻儿子的答案需要先求解$Ms$,而$Ms$的父子树的重儿子又可能$\in L$,这时候后面的重链我们还没有处理。我的解决办法是，先做$L$或$Ms$但不计入答案，只是把重链调整对（重链指向其重儿子）。考虑Dsu on tree的原理，所有轻子树大小之和为$\mathcal O(n\log n)$.所以先做轻儿子但不计入答案，再做重儿子并计入答案，再做轻儿子并计入答案。注意这个点做完之后重链要指向重儿子。

复杂度$\mathcal O(n\log^2 n)$

My code