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$。
我从赛中搞到赛后，搞了起码三个小时才写对。这题过的人还特别多。。。
kblack: 把路灯放到右边的操作一样，建立状态 f[i][j][k] 表示照亮前 i 个，准备了 j 个小路灯，假装用了 k 个大路灯，且第 i 个位置的路灯是大路灯或直接用的路灯，然后枚举下一个路灯的位置，枚举中间的路灯当作小路灯，下一盏是大路灯还是小路灯进行转移，常数优化，好了。
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.