Difference between revisions of "ACM-ICPC 2018 Xuzhou Online Contest"

From EOJ Wiki
Jump to navigation Jump to search
Line 34: Line 34:
  
 
Solved by zerol. 01:16 (+)
 
Solved by zerol. 01:16 (+)
 +
 +
题解:单点修改,询问区间内所有前缀和的和。
 +
 +
题解:用 BIT 维护前缀和的和和前缀和,就好了。
  
 
== Problem I ==
 
== Problem I ==

Revision as of 10:01, 9 September 2018

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 (+)

Problem J

Solved by kblack. 02:42 (+3)

Problem K

Solved by zerol. 02:51 (+6)

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

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