2017ACM萧山训练第2场(NWERC 2008)

2017年8月8日6021

A:Equilibrium Mobile

最终天平平衡的状态下, 每个结点x满足w[x]*(2^dep[x])相等

统计所有的w[x]*(2^dep[x]),答案是叶子数减去出现次数最多的个数

B:Proving Equivalences

答案是max{入度为0的连通块个数,出度为0的连通块个数}

特判连通块为1的情况

每个连通块,出度0的点,向其它入度为0的连边,使得形成一个环

C:Cat vs. Dog

找出所有相互不兼容的人,将他们连边,求最大独立集的个数

二分图匹配

D:Disgruntled Judge

枚举所有的 a,根据 x1和 x3 可以用扩展欧几里得求出 b,再验证一下

E:Easy Climb

发现最后有效的高度只有所有的h_i + k * d (-n <= k <= n)

离散化后只有 n^2 种高度

然后可以设计一个 O(n^3) 状态的 dp,f(i, j) 表示考虑前 i 座山,最后一座的高度是离散后的 j

f(i, j) = max{f(i – 1, k)}(其中 j 和 k 离散前的差不超过d)

用一个单调队列来优化到 O(1)转移

H:Matchsticks

最小值可以直接 dp 出来,最大值是11…11,或者71…11,根据奇偶性直接输出

J:Shuffle

首先预处理从第 i 个位置向前的 n 个数字中有没有重复的,不重复的打上标记

然后枚举第一个分段点 x,则 x + k * n 都带有标记

注意两侧不完整的分段要验证一下有没有相同的

 

  • 最可爱的Prim2017年8月8日 下午11:21 回复

    黄学长最棒啦!

    #1