场上被干烂了
D
有一个朴素dp,记 \(f_{u,x}\) 表示节点 \(u\) 下子树下每条路径上有 \(x\) 个黑点的最小操作次数, \(g_{u,0/1}\) 表示点 \(u\) 的颜色变为红/黑的代价,转移显然:
\[ f_{u,x}=\min_{i\in\{0,1\}}\left(g_{u,i}+\sum_{v\in Son(u)}f_{v,x-i}\right) \]
注意(注意力涣散)到 \(f_{u,v}\) 是由一个 \(\{\min,+\}\) 卷积得来的,而 \(g_u\) 是凸的,而两个凸序列的 \(\{\min,+\}\) 卷积仍然是凸序列,那么可以归纳证明 \(f_u\) 也是凸的。
那么我们考虑维护差分 \(d_{u,x}=f_{u,x}-f_{u,x-1}\) 满足 \(d_{u,x}\ge d_{u,x-1}\) ,记 \(D_x=\sum_{v\in Son(u)}d_{v,x}\) 则上述转移可以表达为:
\[ d_{u,x}=D_{x-1}+\min\{g_{u,0}-g_{u,1}+D_x,0\}-\min\{g_{u,0}-g_{u,1}+D_{x-1},0\} \]
考虑按大小分类讨论:
\[ d_{u,x}= \begin{cases} D_x & D_x\le g_{u,1}-g_{u,0} \\ g_{u,1}-g_{u,0} & D_{x-1} \le g_{u,1}-g_{u,0} \le D_x \\ D_{x-1} & g_{u,1}-g_{u,0} \le D_{x-1} \end{cases} \]
于是我们只需要维护一个单调序列,支持动态插入 \(\pm1\) 与整体加,那么可以维护两个vector,一个存正数,一个存负数,再加一个cnt存0的个数,就可以维护这个单调序列。
点 \(u\) 的答案就是 \(f_{u,0}+\min\{presumd_u\}\) , \(f_{u,0}\) 就是 \(u\) 子树中黑点个数。
K
真恶心啊。
记WQB分别为012。
考虑出牌的过程,一定有一个时刻手牌数量到达了上限 \(k\) ,在到达上限之前等价于无上限,到达上限之后这个上限也没有用了,那么可以把整个过程分成2个部分,分别进行处理。
先考虑手牌满了之后,那么可以有一个dp,记 \(f_{i,j}\) 表示已经抽完了前 \(i\) 张牌,手上有 \(j\) 张2时,足够抽完所有牌的最少的1的数量。初始状态是 \(f_{\ge m, j}=-\infty\) 。在手牌满的情况下,每次打牌都相当于抽出下一张牌,并替换掉打出的牌,那么我们可以通过考虑下一张牌出什么,以及根据下一张牌是什么来写出状态转移方程(情况太多了,直接贴代码了):
1 | for(int i = m - 1; i >= 0; i--) { |
这部分主要是注意两点:
- 要打1的时候手上必须要有1,于是就有了上面代码中的 \(\max\) 。
- 打了1或者2都要在状态上进行正确的加减
考虑已经有了一个 \(k\) ,如何判断其是否合法,那么朴素想法可以枚举第一次手牌满的位置 \(t\) ,也即我们摸完了 \(t\) 位置的牌后我们的手牌恰好满了。由于摸上来的牌是固定的,而只有打出2才能使手牌数量增加,于是我们可以计算出当前手上每张牌的数量。记 \(cnt_i\) 为所有已经摸上来的 \(i\) 种牌的数量,于是0的数量为 \(cnt_0\) ,总共使用了 \(n + t - k\) 张牌,其中2使用了 \(k-n\) 张,于是2的数量就是 \(cnt_2-(k-n)\) ,1的数量就是 \(cnt_1-t+2*(k-n)\) 张,以上三种手牌数量记为 \(c_i\) 。
考虑什么条件下这种情况是可行的,首先必须 \(c_{1/2} \ge 0\) ,其次需要 \(f_{t,c_2}\le c_1\) ,然后我们还需要能摸到这个时候,于是我们又考虑一个dp,记 \(g_{i,j}\) 表示摸完了前 \(i\) 张牌,手上有 \(j\) 张2是否可能,初始状态为 \(g_{0,hcnt_2}=1\) , \(hcnt_2\) 表示初始手牌中2的个数。对于每个状态,我们也可以计算出不同手牌的个数,于是可以得到状态转移为:
1 | for(int i = 0; i < m; i++) { |
求出 \(g_{i,j}\) 之后,我们就可以补完上述的条件了,只需再加上 \(g_{t,c_2}=1\) 即可断定该情况可行,总复杂度为 \(O(nm)\) 。
最后别忘了把G牌算进去,答案要+1的。