Difference between revisions of "ICPC 2019 Shanghai Online Contest"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
| 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 (+)