场上被干烂了

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\) 。在手牌满的情况下，每次打牌都相当于抽出下一张牌，并替换掉打出的牌，那么我们可以通过考虑下一张牌出什么，以及根据下一张牌是什么来写出状态转移方程（情况太多了，直接贴代码了）：

for(int i = m - 1; i >= 0; i--) {
    for(int j = 0; j <= n + m; j++) {
        if(disk[i + 1] == 2) {
            f[i][j] = min(f[i][j], max(f[i + 1][j + 1] + 1, 1));
            if(j) f[i][j] = min(f[i][j], f[i + 2][j]);
        } else if(disk[i + 1] == 1) {
            f[i][j] = min(f[i][j], max(f[i + 1][j], 1));
            if(j) f[i][j] = min(f[i][j], max(f[i + 2][j - 1] - 1, 0));
        } else {
            f[i][j] = min(f[i][j], max(f[i + 1][j] + 1, 1));
            if(j) f[i][j] = min(f[i][j], f[i + 2][j - 1]);
        }
    }
}

这部分主要是注意两点：

要打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的个数。对于每个状态，我们也可以计算出不同手牌的个数，于是可以得到状态转移为：

for(int i = 0; i < m; i++) {
    for(int j = 0; j <= n + m; j++) {
        if(g[i][j] == 0) continue;
        int c2all = hcnt[2] + sum[i][2] - j;
        int c1use = i - c2all * 2;
        int c1 = hcnt[1] + sum[i][1] - c1use;
        if(c1) {
            g[i + 1][j + (disk[i + 1] == 2)] = 1;
        }
        if(j && i + 2 < m) {
            g[i + 2][j - 1 + (disk[i + 1] == 2) + (disk[i + 2] == 2)] = 1;
        }
    }
}

求出 \(g_{i,j}\) 之后，我们就可以补完上述的条件了，只需再加上 \(g_{t,c_2}=1\) 即可断定该情况可行，总复杂度为 \(O(nm)\) 。

最后别忘了把G牌算进去，答案要+1的。

THC

2nd Ucup Stage 11 Nanjing场题解

D

K