- easy: FJKI
- medium-easy: AE
- medium: BCL
Problem A. Artful Paintings
solved by F0_0H (91 min, +1)
二分答案后差分约束，SPFA 判负环。(O(nmlogn))
Problem B. Binary Numbers
solved by F0_0H (297, +2)
做法一：
- (F(a,b)) 为 (a) 和 (b) 的 LCP。
- 注意到，(Lcp(x, y))，当 (y>x) 时，随着 (y) 增加，dep 深度递减。
- 注意到，比 (r_i) 大的点，一定在 (lca(a_i,r_i)) 子树外，比 (l_i) 小的点，一定在 (lca(a_i,l_i)) 的子树外。
- 施展 DP，依次决策每段该选择什么元素，到第 (i) 段的转移，一定是来自于第 (i-1) 段的一个区间。
- (O(2^m * m))
做法二：
更直接了当。
- (dep(lca(a_i,r_i)) geq dep(lca(a_{i+1},r_i)))
- (dep(lca(a_i,l_i)) geq dep(lca(a_{i-1},l_i)))
- (dp[i][j][k]) 第 i 段中, (lcp(a_i,r_i)=j,lcp(a_i,r_i+1)=k) 的方案数。
Problem C. Competition in Swiss-system
solved by sdcgvhgj (208 +2)
Problem D. Driverless Car
Problem E. Exchanging Gifts
solved by sdcgvhgj (99 +1)
x，y 向 i 连边，第 u 个字符串中，一个字符的贡献为，u 到 n 路径方案数。
Problem F. Fixing Banners
solved by sdcgvhgj (16 +1)
implement。
Problem G. Game Store
Problem H. Highway Buses
Problem I. Interesting Permutation
solved by rdc (30)
- 逐位考虑。
- 决策和之前已经放好的元素的大小关系，乘法原理即可。
Problem J. Justifying the Conjecture
solved by sdcgvhgj (6)
- 2 + ?
- 3 + ?
- GG
Problem K. Keeping Rabbits
solved by rdc (10)
- 猜测，按初始体重等比例分配。
- 数理统计没学好，不会证明。
Problem L. LRU Algorithm
- 暴力模拟每步操作，hash 每个前缀。
- 比赛时，不算复杂度，真是怠惰。
summary and replay
medium 依然推进困难。
RDC 从 90 min 后，开始梦游。