0%

2nd Ucup Stage 11 Nanjing场 题解

场上被干烂了

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
2
3
4
5
6
7
8
9
10
11
12
13
14
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的个数。对于每个状态,我们也可以计算出不同手牌的个数,于是可以得到状态转移为:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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的。