2018 Multi-University, HDU Day 2

From EOJ Wiki
Jump to navigation Jump to search

Problem C

Upsolved by ultmaster.

题意:给一个无向图,求用最少的路径(可以非简单),覆盖无向图的所有边。

题解:把这个图补成一个有欧拉回路的图,然后找到欧拉回路,在补的虚边的位置把回路断开。由于要输出方案,所以实现起来有一定代码量,但想清楚并不复杂。(吐槽吐在下面)

ultmaster: 这题因为我们没有一个人会欧拉回路,凉了。kblack 提出了任意找圈 + 合并的野鸡解法,然后甩锅给 zerol 写。不仅难写得一批,而且写完发现情况很多根本讨论不完。

然后赛后 kblack 在电梯里提出了加虚边的想法。(其实到此为止才基本是对了)

赛后查了查(其实赛程中也查了,只是没看清楚),发现欧拉回路居然是 $O(E)$ 的,震惊了。。。

吐槽:

  • SB 出题人说好了没重边,居然有重边。辣鸡。assert 了半天,一点都不有趣。
  • SB 出题人卡时间常数,辣鸡。听说 std 不带 log 的,很感兴趣啊?
  • SB 杭电卡空间常数,辣鸡。只给 32 MB 空间。然后一会儿空间换时间,一会儿时间换空间。。。

杭电就是日常这种「就给你 32MB 你必须接受」的态度。都想给杭电捐款买内存条了。。。

Problem D

Solved by ultmaster. 00:16 (+)

题意:给 $[n]$ 每次操作删除一个数和它所有的因数,求先手胜还是后手胜。

题解:好像只有 Yes。证明不详。

Problem E

Solved by zerol. 02:06 (+1)

题意:构造 2000×2000 的 01 矩阵,使得 1 的数量不少于 85000,且不存在 (x1, y1), (x1, y2), (x2, y1), (x2, y2) 同时为 1。

题解:构造 $k^2 \times k^2$ 的矩阵包含 $k^3$ 个 1。首先每列都放 k 个数,将 1~k^2 写成一个 k×k 的数字矩阵 M,每列的 k 个数来自于 M 的每行各一个。k×k 列的选取方法的不同之处在于首项和公差至少有一个不一样(都从 0~k-1 枚举一遍)。正确性依赖于 k 是素数。但是 43^3 不够 85000,所以选取 k=47,取左上角 2000×2000 恰好 1 的个数超过 85000。正确性证明,如果某两列有两个数对应相等,那么这两个数来自于 M 中不同的行,它们的公差是那两个数的距离除以行的距离(模 k 意义下),但根据构造,如果公差一样,那么首项不一样。

Problem F

Upsolved by ultmaster.

题意:棋盘染色。要求至少 $a$ 行 $b$ 列全黑,求方案数。

题解:大量公式预警。

Problem G

Solved by kblack. 00:39 (+1)

题意:给出排列 $b_i$,对 $a_i$ 区间 $+1$,维护 $\lfloor \frac{a_i}{b_i} \rfloor$,区间求和。

题解:注意到 $b_i$ 是一个排列,每个位置总计最多 $+q$,值会总共最多变化次数是对数级的,故只要线段树记录 $ a_i - (a_i \bmod b_i) $,对于要突变的值暴力维护即可。

Problem J

Solved by zerol. 00:14 (+1)

题意:给一列数,可以花 y 交换相邻两个元素,最后要为每个逆序对付出 x。

题解:显然交换两个相邻元素一定能减少一个逆序对且至多减少一个,所以答案就是 逆序对数量 × min{x,y}。逆序对数量用树状数组或者归并可以求出。