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

From EOJ Wiki
Jump to navigation Jump to search
Line 8: Line 8:
  
 
Solved by kblack. 01:16 (+1)
 
Solved by kblack. 01:16 (+1)
 +
 +
题意:博弈,每人轮流选择可以 $+a_i$ 或 $-b_i$ 或 $*(-1)$,两个人分别要最终大于或小于某个数,求结果。
 +
 +
题解:记忆化搜索,状态是 (当前轮次, 当前分数)。
  
 
== Problem C ==
 
== Problem C ==

Revision as of 10:19, 9 September 2018

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 E

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