经过之前四场内掉了超过 250 分
其中一场还只写出两题暴扣 144 分
最近这两场状况终于回来了
总算重新回到 1900+ 变回紫色
这一场好像还是我表现最好的一次
七题写了五题排在 75 名
而且这次还第一次成功 hack 到人 舒服
https://i.imgur.com/cnL4mcB.png
A. Two Towers
https://codeforces.com/contest/1795/problem/A
https://codeforces.com/contest/1795/submission/193839884
可以看成是将两座塔头对头接起来找分割点
相邻颜色一样就必须切
如果必须切的边界超过一个就会失败
B. Ideal Point
https://codeforces.com/contest/1795/problem/B
https://codeforces.com/contest/1795/submission/193845093
可以发现如果没通过 k 不选一定 optimal
如果有通过 k 选下去一定 optimal
直接维护一个阵列纪录每个人被选的次数
看 k 选的次数是不是唯一的最大值即可
因为 n <= 50 所以 O(n^2) 就会过了
不过用维护 adjacent difference 的技巧可以 O(n)
这题我成功 hack 了六个人，基本上都是写成 O(n^3)
我觉得是没注意到 python 的 `in` 做在 list 上会要遍历整个 list
C. Tea Tasting
https://codeforces.com/contest/1795/problem/C
https://codeforces.com/contest/1795/submission/193859409
比完才发现很多人是用 binary search 做的
我是用 min heap (priority_queue) 去做
这个 priority_queue 里存的是还有剩的茶
且在第 i 轮时，priority_queue 里存的是
a_j + (b_1 + ... + b_{j-1}), for j <= i
第 i 轮时，我们想找出 taster i 总共能喝的数量
能喝光 j 的条件是
a_j <= b_j + ... + b_i (第 j 个茶是从 第 j 个 taster 开始喝)
也就是
a_j + (b_1 + ... + b_{j-1}) <= b_1 + ... + b_i
如果不合法就 pop 掉并计算喝掉的数量
而那些留在 priority queue 的都一定 >= b_1 + ... + b_i
所以他们可以喝整个 b_i 的量
D. Triangle Coloring
https://codeforces.com/contest/1795/problem/D
https://codeforces.com/contest/1795/submission/193870666
这题其实就是在考排列组合而已
首先，每个三角形最多能选两个边
因为 n 是偶数，所以一定可以让每个三角形都恰选两个边
总共会有 n/2 组 RRB 及 n/2 组 RBB
有 C(n, n/2) 种分法
对固定好是 RRB 或 RBB 的三角形而言
要获得最大分数等价于挑掉最小值
所以最小值有几个就是这个三角形的选择数
最后乘回 C(n, n/2) 即可
E. Explosions?
https://codeforces.com/contest/1795/problem/E
https://codeforces.com/contest/1795/submission/193897368
因为爆炸必须在最后使用
可以发现，假如我们想要在点 i 使用爆炸
全死光的条件是
H_1 < H_2 < ... < H_i
H_i > H_{i+1} > ... > H_n
所以我们只要分别作出 L, R 让
L[i] := 使 H_1, ..., H_i 合法的最小 cost
R[i] := 使 H_i, ..., H_n 合法的最小 cost
因为是对称的所以看 L 怎么做就好
对 H_1, ..., H_{i-1}
把相邻且差一的聚集起来，形成很多个梯形
例如是 [a, a+1, ..., b], [c, c+1, ..., d] 这样
当 H_i 进来，如果 d < H_i - 1 当然就没事
但如果 d >= H_i - 1, 则 d 必须变成 H_i - 1
且 [c, ..., d] 内的每个人都要减少一样的量
如果 c 变得比 b 小就继续往前合并
所以可以用 stack 来维护一堆梯形
每个梯形只需要纪录头尾
因为只要某个梯形必须下降的话就会和其他梯形合并
所以对每个 i 而言，以 i 结尾的梯形最多只会进出stack 各一次
还是可以 O(n) 完成
后面两题 F G 就没时间做了