2018-2019 XIX Open Cup, Grand Prix of Korea
ultmaster:依然是签到选手 U。
Problem A
Solved by zerol. 03:42 (+2)
Problem B
Unsolved.
Problem C
Unsolved.
Problem D
Unsolved.
Problem E
Solved by kblack. 01:00 (+)
Problem F
Solved by zerol. 01:13 (+)
Problem G
Solved by kblack. 04:48 (+2)
Upsolved by ultmaster.
ultmaster: 后半场一直在做这个题。结果还是依靠稳健的 kblack 才过了这题。
我的思路(经过反复的修改以后)是这样的:为了方便考虑先把路灯的位置放到最右边。f[i][j][k][x] 表示到 i 为止,i-x 已经完全被覆盖(也就意味着 i-x 上面一定放了路灯),已经捐了 j 盏路灯,已经免费用了 k 盏路灯的最小代价。那么答案就是 min(f[n][k][k][0], f[n+1][k][k][0], f[n+1][k][k][1]) 对于 $1 \le k \le K$。考虑转移:
- 对于 $x>0$,f[i][j][k][x] 可以从 f[i-1][j][k][x-1] 转移而来(表示当前位置不放路灯);也可以从 f[i-1][j-1][k][x-1]+w[i] 转移而来(表示把当前位置的路灯捐掉);
- 对于 $x=0$,f[i][j][k][0] 可以从 f[i][j][k][1], f[i][j][k][2], f[i][j][k][3] 转移而来(把路灯放在“当前位置不放路灯”的状态之上,同时允许把当前位置的路灯捐掉);最后一种是路灯给自己用,注意,如果当前位置的路灯要立即使用的话,就不能把当前位置的路灯捐掉了(否则会偷税,我也没想清楚),所以是从 f[i-1][j][k][0], f[i-1][j][k][1], f[i-1][j][k][2] 转移而来。
- 把 w[1] 初始化成 $\infty$,f[0][x][x][x] 除了 f[0][0][0][x] 初始化成 $\infty$。
我从赛中搞到赛后,搞了起码三个小时才写对。这题过的人还特别多。。。
Problem H
Solved by zerol. 00:35 (+)
Problem I
Solved by ultmaster. 00:40 (+1)
刚开始不会博弈,以为要 SG 函数。
好不容易会博弈了,发现根本不需要 SG 函数。
然后 WA 了,仔细一看题,发现还是需要 SG 函数。
Problem J
Unsolved.
Problem K
Unsolved.
Problem L
Solved by kblack. 00:24 (+)
Problem M
Unsolved.