ACM-ICPC 2018 Xuzhou Online Contest

ECNU Foreigners

Problem A

Solved by ultmaster. 01:19 (+)

Problem B

Solved by kblack. 01:16 (+1)

题意：博弈，每人轮流选择可以 $+a_i$ 或 $-b_i$ 或 $*(-1)$，两个人分别要最终大于或小于某个数，求结果。

题解：记忆化搜索，状态是 (当前轮次, 当前分数)。

Problem C

Solved by ultmaster. 02:56 (+2)

Problem D

Solved by zerol. 00:59 (+2)

题意：求 $\sum_{i=1}^m \mu(in)$

题解：如果 $n$ 中有平方因子，那么显然答案是 0。否则相当于求 $\mu(n) \cdot \sum_{i=1}^m \mu'(i)$，其中 $\mu'$ 是在 $\mu$ 的基础上不把 $n$ 的质因数当质数。类似于求 $\mu$ 的前缀和的方法（任意一种亚线性筛），改一改就能过了。

Problem F

Solved by ultmaster. 00:26 (+)

Problem G

Solved by kblack. 00:34 (+)

题意：堆叠若干个以原点为左下角的矩形，求看得到的右边界和上边界的总长度。

题解：从后往前，添加矩形时计算向下和向左露出的边界长度，这个部分可以用 bit 或线段树维护后缀最大值做。

Problem H

Solved by zerol. 01:16 (+)

题解：单点修改，询问区间内所有前缀和的和。

题解：用 BIT 维护前缀和的和和前缀和，就好了。

Problem I

Solved by kblack. 00:16 (+)

温暖的签到 A。

Problem J

Solved by kblack. 02:42 (+3)

题意：造一个最便宜的迷宫，求一个最短路径。

题解：造一个最贵的生成树，求一个树上距离。

Problem K

Solved by zerol. 02:51 (+6)

题意：求模 2 意义下很多次二维卷积的结果。

题解：类似快速幂，但需要求出一次卷积的效果（每一个位置由所有位置中若干个位置 1 的个数的奇偶性唯一决定），总复杂度 $O(n^4 \log t)$。