AGC004 做题记录
A¶
边长中有偶数就可以平分输出
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
B¶
妙贪心(.
假设我们吟唱了
时间复杂度:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
|
C¶
构造题通常需要用上给定的玄学条件。比如这道题中的「保证边界上不会被涂色」。因为我们想找通解,并不能依赖于紫色格子的位置。所以想到先构造没有交集的红色和蓝色格子,并且要保证四连通且与紫色格子连通。最上面一行和所有奇数列填红色,最下面一行和所有偶数列填蓝色(像两把梳子上下卡在一起)。这种构造显然满足四连通,最后取颜色集合与紫色格子的并集即可。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
|
D¶
给了一个基环内向树,并且保证
剩下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
|
E¶
dp神题。
首先观察到出口在棋盘上的相对位置不变,不妨把机器人的运动转化成出口带着棋盘的运动,掉下棋盘的棋子就没了。不妨观察一下出口第一次移动带来的影响,向上走一步会把最下面一行的机器人消除,同时有可能救到当前位置的机器人。其他方向移动的结果也是类似的。
第二个重要的观察是我们并不需要知道出口运动的全过程,只需要知道四个方向分别走到过多远。具体地,我们设四个方向分别走了
定义
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
|