AtCoder AISing Programming Contest 2019 小结

同学们都去WC了,就我一条咸鱼还在学校准备期末考…
学考放假在家打的,第二场ATC,因为第一场只切了一题,所以这次涨的比较多。
今天复习期末考不是很想学习,于是就来机房把E题补了。

D – Nearest Card Game

这题调了我一个多小时,比赛最后两分钟才A,呜呜…

分析

显然这题不是数据结构。注意到其实取的顺序是有一定规律的,我们可以二分两人取的卡片数恰好相等时 Aoki 取的卡上权值的范围,这样后面就可以方便地计算了。但是注意到不一定真的存在这个范围,所以二分如果最后出锅还需要一些操作补救一下(我就是因为搞这个才WA了好多次的)。当然,其实仔细想一想要怎么办还是想得出来的。

E – Attack to a Tree

分析

这是道树形DP,可能我做的 DP 题还是太少,所以一开始并不知道怎么做。

考虑对于一个连通分量,如果要接电脑,那么 battery 的供电能力一定是越小越好。我们从这个入手设计DP方程:

DP[u][i][0/1] 表示以u为根节点的子树中,disconnect 了i条 cable,当前u属于的分量是否包含电脑的最小A之和。

转移考虑两种情况:

  • 切断当前连向子树v的边,那么需要保证DP[v][j][0]合法或者$DP[v][j]1<0$
  • 不切断,那么判断一下合法状态取最优者即可

其实这样想也不是很难,主要就是把切断的边数作为状态来跑背包这一转化。

另外注意转移时需要增加辅助数组维护(见Code)。

Code

void dfs(int u, int fa) {
    sz[u] = 1;
    DP[u][0][A[u] > 0 ? 0 : 1] = A[u];
    /* DP[u][j][0 / 1] - u is root, disconnect j cable(s), 
     * whether there's a computer in the connected component
     * 0 - no, 1 - yes
     */
    LL (*nxt)[2] = DP[5005];    // 辅助数组
    for (auto v : G[u]) {
        if (v == fa) continue;
        dfs(v, u);

        for (int i = 0; i < MAXN; i++) nxt[i][0] = nxt[i][1] = INVALID;
        for (int i = 0; i < sz[u]; i++)
            for (int j = 0; j < sz[v]; j++) {
                // let v be alone,第一种转移
                if (DP[v][j][0] != INVALID || DP[v][j][1] < 0) {
                    upd_min(nxt[i + j + 1][0], DP[u][i][0]);
                    upd_min(nxt[i + j + 1][1], DP[u][i][1]);
                }
                // 第二种转移
                for (int su = 0; su <= 1; su++)
                    for (int sv = 0; sv <= 1; sv++)
                        if (DP[u][i][su] != INVALID && DP[v][j][sv] != INVALID)
                            upd_min(nxt[i + j][su | sv], DP[u][i][su] + DP[v][j][sv]);
            }
        for (int i = 0; i < MAXN; i++) {
            DP[u][i][0] = nxt[i][0];
            DP[u][i][1] = nxt[i][1];
        }
        sz[u] += sz[v];
    }
}

总结

最近感觉就像在风浪中行船,沉、浮、沉、浮…有时候,真的可能一时想得过了,想不通了,不要太急躁。要一直保持那颗初心,不要因一时贪玩而放弃努力。不要再重蹈覆辙了,日后,别再为自己叹息。

About The Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注