• easy: I
  • medium-easy: BDEGJ
  • medium: F
  • medium-hard: A

A.

B.

按 x 排序,\(dp[i][j][k]\) 表示考虑前 \(i\) 个物品,level 1 经验为 \(j\),level 2 经验为 \(j\) 最小花费时间。

C.

D.

E.

F.

  • 考虑更 general 的情况。 给一个图,先手选择一个点删除之,然后轮流操作,每次删除一个和上一次删除的点相连的节点,不能操作的人输。
  • 若存在完美匹配。先手必败,因为后手可以沿着完美匹配的边移动。
  • 否则先手必胜。先手可以先选择一个不在最大匹配里的点,后手一定会选择一个在最大匹配里的点,否则,还有更大的匹配【flip 路径上的边,最大匹配会变大】
  • 接下来考虑最大匹配的求解,\(f[u]\) 表示考虑 \(u\) 的子树,最少失配的点,转移不难推出。

G.

独立考虑行和列。

H.

I.

\(b_i\) 向 \(arg_{j}\ min(|b_i - a_j|)\) 连边。若 Alice 留下的元素集合为 \(S\),Bob 可以保留 \(N(S)\) 的所有元素,因此不管 Alice 保留什么,Bob 一定能留下,与 Alice 保留原始差的绝对值最小的元素。

J.

考虑 \(u\) 点的贡献,设 \(u\) 的邻居按连向 \(u\) 的边权降序排序为 \(d_1,....,d_k\),让 \((d_1,u),(d_2,u)\) 在一个简单环上,\((d_3,u),(d_4,u)\) 在一个简单环上 ......

summary and replay

被 medium 爆了。

国内的 medium 风格更偏向于 “trick + implement”,这里的 trick 多为套路,或者是套路套套路。这种风格,比较适合 “知识面广 + 代码实现能力不错” 的队伍发挥。

而国外特别是欧洲的 medium 风格更偏向于 “observation + implement”,这里的 observation 对想象力以及证明能力都有较高的要求。

05-11 22:19