Difference between revisions of "ICPC 2019 Shanghai Online Contest"

From EOJ Wiki
Jump to navigation Jump to search
Line 16: Line 16:
  
 
Solved by Xiejiadong && Kilo_5723. 03:45 (+1)
 
Solved by Xiejiadong && Kilo_5723. 03:45 (+1)
 +
 +
题意:给出三个长度为 $n$ 的数组,在三个数组中任意挑选一个数,求有多少方案能够组成三角形。
 +
 +
题解:考虑,所有的情况,由四部分构成:
 +
 +
* $a+b>c,a+c>b,b+c>a$
 +
 +
* $a+b\le c,a+c>b,b+c>a$
 +
 +
* $a+b>c,a+c\le b,b+c>a$
 +
 +
* $a+b>c,a+c>b,b+c\le a$
 +
 +
其实还有另外三种情况,可以发现是不存在的。
 +
 +
于是我们发现,如果分别计算 $a+b\ge c$ , $a+c\ge b$ , $c+b\ge a$ ,只有第一种部分计算了三次,其余部分都计算了两次,于是剪掉全集两次即可,全集显然就是 $n^2$ 。
 +
 +
对于计算 $a+b\ge c$ , $a+c\ge b$ , $c+b\ge a$ ,利用 FFT 解决加法部分,然后对另一部分前缀和预处理,就能直接计算了。
 +
 +
FFT 的复杂度显然只和值域相关,题目只保证了 $n$ 的大小,所以对于 $n\le 1000$ 的部分,需要 $O(n^2)$ 来做。
  
 
== Problem D ==
 
== Problem D ==

Revision as of 02:17, 16 September 2019

Problem A

Unsolved.

Problem B

Solved by Xiejiadong. 00:20 (+1)

题意:一开始灯都是关着的,每次操作一个区间的灯使其状态相反,求最后开着的灯数量。

题解:卡内存,没法把所有灯的状态开下来。

于是离散化,记录操作的区间端点,扫一遍就好了。

Problem C

Solved by Xiejiadong && Kilo_5723. 03:45 (+1)

题意:给出三个长度为 $n$ 的数组,在三个数组中任意挑选一个数,求有多少方案能够组成三角形。

题解:考虑,所有的情况,由四部分构成:

  • $a+b>c,a+c>b,b+c>a$
  • $a+b\le c,a+c>b,b+c>a$
  • $a+b>c,a+c\le b,b+c>a$
  • $a+b>c,a+c>b,b+c\le a$

其实还有另外三种情况,可以发现是不存在的。

于是我们发现,如果分别计算 $a+b\ge c$ , $a+c\ge b$ , $c+b\ge a$ ,只有第一种部分计算了三次,其余部分都计算了两次,于是剪掉全集两次即可,全集显然就是 $n^2$ 。

对于计算 $a+b\ge c$ , $a+c\ge b$ , $c+b\ge a$ ,利用 FFT 解决加法部分,然后对另一部分前缀和预处理,就能直接计算了。

FFT 的复杂度显然只和值域相关,题目只保证了 $n$ 的大小,所以对于 $n\le 1000$ 的部分,需要 $O(n^2)$ 来做。

Problem D

Solved by Xiejiadong. 02:14 (+1)

Problem E

Solved by Kilo_5723. 04:01 (+)

Problem F

Solved by Kilo_5723. 02:02 (+)

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Solved by Kilo_5723. 00:46 (+2)

Problem J

Solved by Kilo_5723. 01:16 (+1)

Problem K

Solved by Xiejiadong. 00:06 (+)