2018 Multi-University, HDU Day 2

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 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}。逆序对数量用树状数组或者归并可以求出。