AtCoder Grand Contest 004 简要题解

比赛地址

Divide a Cuboid

如果有一边长为偶数，答案为 $0$。
否则找到最长的边切开。
代码

Colorful Slimes

枚举循环右移的次数，相当于每种颜色都可以通过选择某个范围内的颜色得到，直接取最小的即可。
代码

AND Grid

我们只需要想办法造两个矩阵使得整个图连通且两个矩阵不交。
通过人类智慧可以想到造成这样

#####.     .....#
#.....     .#####
#####.     .....#
#.....     .#####
#####.     .....#
#.....     .#####

把左边并上原图作为第一个矩阵，右边并上原图作为第二个矩阵。
代码

Teleporter

显然 $1$ 城市的目的地只能为自己。
那么剩下的只有 $n-1$ 条边了，相当于一棵树，直接 DFS 一遍，子树高 $\geq k$ 时就断掉父边接到 $1$ 城市去。
代码

Salvage Robots

推荐食用官方题解。
考虑将所有机器人移动转化一下，变为出口以及边界移动。
设 $dp_{u,l,d,r}$ 表示出口已经到过的范围是以 $(u,l)$ 为左上角、$(d,r)$ 为右下角的矩形，最多能救的机器人数。
转移考虑一下往哪边扩大，容易算出能救的机器人（排除掉已消失的）所在的范围，通过前缀和即可算出数量，然后就可以转移了。
这么讲非常的不清楚，再次推荐使用官方题解。
我真的讲不清楚 /kel
$dp$ 开 int 开不下，可以开 short。
代码

Namori

戳这里