建议去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)∗(sumi−ai,x)+f(i−1,j−1,k−1)∗ai,x
其中sumi=∑jai,j 。注意转移时需要满足下标非负。最后x的贡献就是∑nj=0∑jk=j/2+1f(n,j,k) [HTML_REMOVED]
这样复杂度是O(n3m),有88pts。
考虑k>⌊j2⌋⇔2k>j⇔k−(j−k)>0
所以存个差值就好,即f(i,j)表示前i行,x的数量减掉别的菜数量为j的方案数。复杂度O(n2m).
T2
一个暴力的dp是,令f(i,j)表示考虑前i个的划分且最后一段是(j,i]的最小代价。
f(i,j)=min
其中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
当高精,然后卡一下空间。
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)