ACM-ICPC 2018 Jiaozuo Online Contest

ECNU Foreigners

终于一机了。发现可能还是浪费了一点时间。（某些题花的时间太久了）

比赛体验很不好，卡读入，卡内存，卡常，数据范围不写清楚。

Problem A

Solved by zerol. 00:07 (+)

温暖的签到。

Problem B

Solved by ultmaster. 01:03 (+)

题意：要求从 $n$ 个数中挑出 $m$ 个数，然后用加减乘除等规定的运算符号依次作用在当前的这个数上，结果尽可能大。

题解：最小可能不一定，但最大应该就是维护一个最大一个最小就好了。DP。

Problem D

Upsolved by ultmaster.

题意：由 $1$ 到 $n$ 组成的长度为 $m$ 的不严格单增数列，求众数出现次数的期望。

题解：单增数列的个数其实就是 $\binom{n+m-1}{n-1}$（插板法）。接下来只要算出众数出现次数不超过 $1,2,3,4,\ldots,m$ 的方案数，就可以算出答案。

考虑计算众数出现次数不超过 $k$ 的方案数，那么根据容斥，答案就是 $\sum_{i=0}^n (-1)^i \binom{n}{i} \binom{n+m-1-(k+1)i}{n-1}$（有 $i$ 个数出现次数超过 $k$，然后把 $(k+1)i$ 减掉之后，剩下的就是插板法）。这里的 $i$ 其实只要枚举到 $m/(k+1)$ 就够了（后面的全是 0）。算组合数的时候用递推预处理。

最后要求浮点（如果取模的话 kblack 大概现场就过了）。由于数据规模较大，浮点会挂掉，需要高精。

Problem E

Solved by kblack. 02:02 (+1)

题意：树上路径加乘、位取反、求和。

题解：位取反相当于用全 $1$ 减，可以和加乘标记合并，然后就是模板时间了。

Problem F

Solved by zerol. 04:25 (+)

题意：有若干条线段，每条有一个价值，要求选其中的一些，使得同一个点至多被覆盖 k 次，价值和最大是多少。

题解：线性规划，单纯形过了。

ultmaster: 一直不上的原因是 一直认为单纯形会出现解（方案）是分数的问题。后来构造（猜测）了一下好像根本不会出现。然后一下子就过了。

Problem G

Solved by zerol. 00:25 (+)

题意：略（反正是签到）

题解：$2^{n-1}$

Problem H

Solved by zerol. 03:26 (+2)

题意：求一个字符串中出现次数在 L~R 之间的子串个数。

题解：后缀自动机裸题。但是交了 MLE 才发现 2E6 的范围只给了 64MB 内存，若干小时后，发现几百个人过了，于是把数组改小了，assert 一个字符串不超过 2E5 大小，结果就过了。

zerol: 数据范围不写清楚，内存又给得那么吝啬，比赛中还不更正题面。出题人你过来，保证不打死你。

Problem I

Solved by zerol. 00:15 (+)

题意：问 A×B×C 的立方体能否被 1×1×2 完全填充。

题解：当且仅当 A×B×C 为偶数时可以（证明显然）。

Problem J

Solved by ultmaster. 02:27 (+1)

题意：问一个数是否是完全平方数，问 $1+2+\cdots+k$ 是否是完全平方数。

题解：二分，大数。有点卡常，后面一问优化了常数才过。

另解：模质数做二次剩余，但是被队友拦住了。

Problem K

Solved by kblack. 00:46 (+2)

题意：$n$ 种硬币，求凑单方式。

题解：经典的生成函数/容斥（喜欢叫什么就叫什么）就好了。

ultmaster: kblack 居然被卡读入了。。。

Problem L

Solved by kblack. 00:19 (+)

题意：求长度为 $n$，字符集大小 $3$ 的，且不包含特殊模式的串。

题解：上两个字符作为 DP 状态，用矩阵乘法优化。

One,Two,Three,AK

Xiejiadong：全程划水，抱紧大腿。

Problem A

Solved by oxx1108. 0:10:55 (+1)

题意：签到

题解：签到

Problem B

Solved by oxx1108 1:34:30 (+2)

题意：要求从 $n$ 个数中挑出 $m$ 个数，然后用加减乘除等规定的运算符号依次作用在当前的这个数上，结果尽可能大。

题解：DP维护一个最大值一个最小值就好了，一开始写了平方的T了……

Problem C

Unsolved.

Problem D

Unsolved.

Problem E

Solved by Xiejiadong. 4:23:20 (+1)

题意：支持树上链的加、乘以及取反运算。

题解：取反运算其实就是$\times (2^{64}-1)-1$

那么，接下来所有的运算都变成了加和乘

树链剖分模板题+线段树维护加乘模板题。

Problem F

Solved by oxx1108. 4:35:30 (+4)

题意：有若干条线段，每条有一个价值，要求选其中的一些，使得同一个点至多被覆盖 k 次，价值和最大是多少。

题解：单纯形，被卡常了，最后极限卡过去了…… 费用流也可以做，训练指南上有类似的建图模型。

Problem G

Solved by dreamcloud. 0:22:20 (+)

题意：输出$2^{n-1}$

题解：如上

Problem H

Upsolved by dream_cloud.

题意：求一个字符串中出现次数在 L~R 之间的子串个数。

题解：建立后缀自动机。求出$cnt[i] = 1 + \sum_{fa[u] = i}cnt[u]$, 对于$cnt[i]$在L~R范围内的答案加上$len[i] - len[fa[i]]$

由于某些人读错题目读成了字符串只含A,B字母，wa的不要不要的。

Problem I

Solved by dreamcloud. 0:11:05 (+)

题意：给你一个$A\times B \times C$的长方体，问你能否用$1 \times 1 \times 2$的长方体铺满

题解：签到题，判$A \times B \times C$是否是偶数

Problem J

Solved by dreamcloud && oxx1108. 3:36:42 (+10)

题意：判一个大数是否为平方数。

题解：牛顿迭代优化一下初始值大约在根号附近即可，跑得还飞快。

正解：取若干素数判是否都为二次剩余，都为则是平方数。

Problem K

Solved by dream_cloud. 0:53:47 (+1)

题意：有$n$个码头，第$i$码头有$c_i$艘同样的船,每艘船都能运$w_i$吨的货物，问你运$s$吨的货物有多少种不同的对船的安排。

题解：dp式子,$dp[i][j]$,只用前$i$个码头的船运$j$吨的货物有多少种不同的方案数，$dp[i][j] = \sum_{k = 0}^{k <= min(c_i,\lfloor \frac{j}{w_i}\rfloor)} dp[i-1][j-k\times w_i]$,虽然乍看上去是三方式子，但是每次枚举$j$的时候，不是直接$++j$，而是$j+=w_i$,用单调栈维护$ dp[i-1][j-k \times w_i], (k <= min(c_i,\lfloor \frac{j}{w_i}\rfloor))$

Problem L

Solved by oxx1108 && Xiejiadong. 0:31:53 (+)

Xiejiadong：我就是打了个dfs。划水。

oxx：我就是套了个模板。划水。