ACM-ICPC 2018 Xuzhou Online Contest

From EOJ Wiki
Revision as of 10:13, 9 September 2018 by Kblack (talk | contribs) (→‎Problem I)
Jump to navigation Jump to search

ECNU Foreigners

Problem A

Solved by ultmaster. 01:19 (+)

Problem B

Solved by kblack. 01:16 (+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 E

Problem F

Solved by ultmaster. 00:26 (+)

Problem G

Solved by kblack. 00:34 (+)

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)$。