ICPC 2019 Shanghai Online Contest

From EOJ Wiki
Revision as of 16:37, 16 September 2019 by Xiejiadong (talk | contribs) (→‎Problem G)
Jump to navigation Jump to search

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)

题意:求 $n\ge 2$ 的时候,有多少方案满足 $a_1+a_2+\cdots +a_n=a_1\cdot a_2\cdot \cdots \cdot a_n$ 。

题解:先打了个表大概看了看,发现当 $n$ 大了以后 $1$ 会很多,于是可以从 $(n-x)+2x=2^x$ 得到 $x$ 最多 $12$ 。

也就是说,非 $1$ 的数最多 $12$ 个,于是考虑直接 dfs 来做。

dfs 需要剪枝,我们默认 dfs 搜出来的序列必须是有序的,交换位置的部分,直接通过排列组合算出来。

对于 dfs 还有一个显然的可行性剪枝,假设当前和为 $sum$ ,乘积为 $mul$ ,即将加上数 $x$ ,如果 $sum+x=x\cdot mul$ ,于是有 $x=\frac{sum}{mul-1}$ ,显然 $x\ge 1$ ,于是有 $sum\ge mul-1$ 。于是这个条件一旦不满足,就可以 return 了。

另外就是针对每一个数枚举的上限,如果不考虑最大的数,每一个数一定满足 $\le log_x(n^2)$ ,$x$ 表示非 $1$ 的个数,最大的一个数可以通过已有的和和乘积直接算出来。

Problem E

Solved by Kilo_5723. 04:01 (+)

Problem F

Solved by Kilo_5723. 02:02 (+)

Problem G

Upsolved by Xiejiadong.

题意:给出一个主串和一些模式串求匹配数量。匹配的要求是字符串长度长度相同,首尾相同,中间可以任意交换位置。

题解:考虑用 hash 来搞。

hash 记录 $28$ 个信息,前两个信息表示首尾的字母,后面的 $26$ 位信息表示整个一段的每个字母出现的数量。

可以发现,询问的总长度不超过 $100000$ ,所以不同的字符串长度是 $\sqrt{100000}$ 级别的,也就是不同长度的不会很多。

于是对于同一长度的,我们可以一起处理,确定长度以后, hash 我们可以用类似于滑动窗口来 $O(1)$ 计算。

有一个需要的优化是, hash 可以用 map 来存,但是不要把所有的 hash 存下来,因为需要用到的 hash 是有限的,只有询问需要的位置才用 map 来存,其余的不要存,如果没有这个优化,根本卡不过去,加了以后甚至会比 std 快上好多。

Problem H

Unsolved.

Problem I

Solved by Kilo_5723. 00:46 (+2)

Problem J

Solved by Kilo_5723. 01:16 (+1)

Problem K

Unsolved.

Problem L

Solved by Xiejiadong. 00:06 (+)

大力预处理。温暖的签到。