ICPC 2019 Shanghai Online Contest

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

题意：对 $1 \le a_i \le m$ 的所有序列 $\{a_n\}$，求出其中每个偶数出现次数都是偶数的序列数量。

题解：令 $p,q$ 为 $1$ ~ $m$ 中奇数，偶数的数量。对于 $q=0$，答案 $f_0(n)=p^n$。

考虑 $q=1$ 的情况，答案 $f_1(n)=\sum_{i=1}^{\lfloor \frac{n}{2} \rfloor}C_n^{2*i}f_0(n-2*i)=\sum_{i=1}^{\lfloor \frac{n}{2} \rfloor}C_n^{2*i}p^{n-2*i}$。

我们发现，这相当于 $(p+1)^n$ 中指数与 $n$ 同奇偶的项之和，等于 $\frac{(p+1)^n+(p-1)^n}{2}$。

我们要做的，相当于迭代这个式子 $q$ 次。因为每一个 $p^n$ 在经过一次迭代后都会变成 $\frac{(p+1)^n+(p-1)^n}{2}$，很容易发现 $q$ 次迭代后会变成 $\sum_{i=0}^{q}C_q^i \cdot (p+2\cdot i-q)^n$。

Problem F

Solved by Kilo_5723. 02:02 (+)

题意：将 $n$ 个物品划分为数个集合，按集合第一个元素出现的顺序把物品编号，求所有划分方案编号中字典序第 $k$ 大的方案。

题解：考虑 $dp[i][j]$ 代表当前有 $i$ 个集合，之后还要加入 $j$ 个元素的方案数，初始位置是 $dp[0][n]$。

对于 $dp[i][j]$ 的状态，枚举枚举下一个数的填法。填 $1$ ~ $i$ 方案数和转移目的地都是 $dp[i][j-1]$，而填 $i+1$ 时是 $dp[i+1][j-1]$。每次输出转移时填的数，转移到 $j=0$ 时就输出了第 $k$ 大的序列。

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)

题意：长度为 $n$ 的错误代码，可以花费 $b$ 的时间在一行代码之后添加检查语句，也可以花费 $a$ 的时间运行一边程序，求最少花费多少时间可以找到错误发生的位置。

题解：我们发现，每次添加 $k$ 条检查语句后运行可以把 $n$ 的规模缩小到 $\lceil \frac{n}{k+1} \rceil$。考虑枚举运行次数，则在运行次数固定的情况下，则为了在和尽可能小的情况下最大化乘积，每次添加的检查语句数量最小值和最大值之间最多相差 $1$。

又因为每次至少能把 $n$ 的规模缩小一半，运行程序的次数不会多于 $100$。因此枚举运行次数，每次由刚才推出的性质计算出最少添加检查语句的数量求出花费，答案取全局最小值。

计算过程中会爆 long long。

Problem J

Solved by Kilo_5723. 01:16 (+1)

题意：给出 $\{a_n\}$，求其子集，满足子集和不小于总和，但去掉任一元素后不大于总和，求方案数。

题解：排序后枚举子集中最后一个元素。依次加入背包，每次加入一个数时同时对其作为最后一个元素时的合法方案数求和。

Problem K

Unsolved.

Problem L

Solved by Xiejiadong. 00:06 (+)

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