ACM-ICPC 2018 Nanjing Online Contest

ECNU Foreigners

本场贡献最佳：场外选手 zerol。

ultmaster 和 kblack 两个人组团在机房吃大便。

听说计蒜客会吃账号，所以搞了一个仓库。本场代码 地址点这里。

Problem A

Solved by Mathematica. 00:13 (+)

Simplify[Mod[Sum[i!*i, {i, 1, n - 1}], n]]

输出

Mod[-1 + n!, n]

Problem B

Solved by ultmaster. 01:04 (+)

题意：求 $nm$ 的矩阵上有若干个位置禁手，为不禁手的地方能拉出多少个不同的矩阵。

题解：只要做过此类问题的集大成者：EOJ 3514 五彩地砖，就会发现这题就是个。。。裸题。从大到小枚举矩阵的开始的列，然后考虑可以放的区域，发现是一个 histogram。就是求 histogram 里可以放的不同的矩阵的数量。从大到小枚举矩阵的开始行，然后用一个单调栈维护就好了。

Problem C

Solved by ultmaster. 03:24 (+4)

题意：有一种非常类似斗地主的游戏，然后给出一堆牌（牌的顺序也告诉你了），然后告诉你几个人玩，让你求最后结果。

题解：按题意模拟即可。有一个 else if 漏写了 else 搞自闭了。

Problem D

Solved by ultmaster. 04:17 (+2)

题意：干两件事情：1. 把凸多边形缩小 $r$；2. 求缩小后的凸多边形上的三个点使得组成的三角形面积最大。

题解：1. 这题做过；2. 枚举两个点，三分找第三个点就好了。

Problem E

Solved by ultmaster. 00:35 (+)

题意：给出一系列物品和物品获得之间的依赖关系，物品获得的价值和物品本身的属性和获得的顺序有关。求最大收益。

题解：状压记忆化搜索即可。对于某一个状态，枚举最后一个获得的物品，然后检查是不是其他东西都已经获得，如果是，更新答案。

Problem F

Solved by zerol. 03:48 (+5)

题意：给一棵树，要求支持以下操作：

1. u v 连边

2. 以 u 为根，把 v 和它父亲的边切开

3. 询问以 u 为根，一个生物在 u，以等概率移动到相邻结点，问最后回到 u 的经过边数的期望。

题解：蒙特卡洛可以发现询问就是求 (sz[u]-1)/d[u]*2，其中 sz[u] 是联通块大小，d[u] 是度数。然后就是一个很经典的维护子树大小的 lct 了。

zerol：WA 了那么多次的原因是 lct 在找父亲是没有下传标记，导致看起来是右儿子但其实是左儿子。

Problem G

Solved by kblack. 02:58 (+)

题意：一排房间装着灯，每月买新的节能灯替换，每次找最前面的能完整替换的房间完整替换，求过程。

题解：开个线段树，按灯数量排序，维护最前（原本的）位置，模拟一下就好了。

Problem H

Solved by zerol. 04:47 (+3)

题意：一开始每个集合里有一个数。要求支持操作：

1. 合并两个集合

2. 把一个集合里的数都 +1

3. 询问一个集合里满足 $x \equiv a \pmod {2^k}$ 的 $x$ 的个数。

题解：首先发现询问 3 就是相当于求把所有数字倒过来插入一个 trie 以后某个节点上的和。把一个 trie 上的数字 +1，相当于交换 0/1 然后在左子树(0) 下递归交换。集合合并就是类似于动态开点的线段树的合并。当然这里的数据结构像是介于 trie 和 主席树之间的东西。

zerol：最后只想着 AK 了，就随便交了。因为空间没开够（用的是持久化数据结构）所以 TLE/RE 了两发。不过能写对还是很幸运的。

Problem I

Solved by zerol. 02:26 (+)

题意：求一个数字串中所有本质不同的回文子串之和。

题解：建回文自动机，在转移边上 dfs 统计一下。

Problem J

Solved by zerol. 00:17 (+)

题意：求某个积性函数的前缀和。

题解：上个板子就好了。（这里我用了 min_25 筛，但感觉数据范围有点小。所以其实直接线性筛就好了。）

Problem K

Solved by kblack. 01:53 (+)

题意：给一个函数生成高精量的数，求异或和不为 $0$ 的子集数。

题解：函数循环最大 $2^{12}$，将数列看成 $01$ 向量，组成矩阵 $A$，答案即是 $2^n-2^{(n-r(A))}$，向量长度 12，将循环里（本质不同）的数高斯消元就能方便求到秩了。

Problem L

Solved by ultmaster. 01:26 (+5)

题意：求至多可以让 $k$ 条边免费的最短路径。

题解：建 $n(k+1)$ 个点，然后直接跑最短路。复杂度是 $O(nk \log n)$。是不对的，但是过了。

ultmaster: 听说这题卡了 SPFA，可是 kblack 明明写的是 Dijkstra。kblack 说他军训累了，你就放他过了吧。但是你就是给他 TLE。你考虑过这些吗？没有，你只考虑你自己。

kblack: 叮咚，你的罚了吗外卖，点个好评谢谢。_(xз」∠)_

One,Two,Three,AK

Xiejiadong：整场比赛的锅都是我的。SPFA被卡，SB题卡了3h。自闭。

Problem A

Solved by oxx1108. 0:04:35(+)

题意：签到题，猜结论

题解：看看样例就知道了

Problem B

Solved by dreamcloud. 1:40:13(+) 题意：求 nm 的矩阵上有若干个位置禁手，问总共有多少个不包含禁手的子矩阵。

题解：首先先对每一个格子求出最多向下多少个。然后枚举以每个格子为左上角有多少个矩阵，从左往右看，依次看每列向下能有多少个矩阵，显然是单调递减的，那么前面格子向下的数量会限制后面的。所以我们只需往后找到第一个比当前向下数量小的格子，那么中间一段都更新为当前一段(不需要真的更新，直接算出值即可)，后面则不变。往后找到第一个的方法就是单调队列。

Problem C

Upsolved by oxx1108. 4:59:46(-7)

题意：模拟一个扑克牌游戏

题解：模拟一下即可，$multiset$ 的 $erease$ 用错了导致一直Wa。

Problem D

Solved by oxx1108. 3:23:04(+2)

题意：干两件事情：1. 把凸多边形缩小 $r$；2. 求缩小后的凸多边形上的三个点使得组成的三角形面积最大。

题解：半平面交套个凸包内最大三角形面积(旋转卡壳)模板即可。

Problem E

Solved by Xiejiadong. 3:29:38(+5)

题意：给出解每道题目之前必须要解决的一些题目，求做多可以获得的分数。

题解：一开始觉得是在拓扑图上搞。写了贪心，Wa了；写了dp，Tle了。自闭。

然后发现直接状态压缩一下，跑个dp，用宽搜来实现就可以了。

Problem F

Unsolved.

Problem G

Solved by dreamcloud. 4:08:09(+1)

题意：$n$个房间，每个房间装着$k_i$灯，每月买$m$个新的节能灯替换，每次找最前面的能全部替换的房间替换，求过程。

题解：用线段树，维护最小值，每次找比小于等于当前有的节能灯数量的第一个位置。

Problem H

Unsolved.

Problem I

Solved by Xiejiadong. 2:56:25(+)

题意：求字符串中所有回文字串的和。

题解：回文自动机模板题。加一个处理回文子串大小的东西，最后把本质不同的回文子串全部相加就好了。

Problem J

Solved by dreamcloud. 0:26:57(+)

题意：签到题，积性函数求个前缀和

题解：线性筛搞一下就行

Problem K

Upsolved by dreamcloud

题意：含$n$($n \le 10^{10000000}$)个元素的数组，$a_n = f(a_{n-1})\%k$，($k \le 2^{12}$)，求异或和不为 0 的子集数。

题解：计算出异或和为0的子集数，再通过$2^n$减去即可得到答案。数组中不同元素个数不超过k。将每个数看作二进制，要满足通过取或者不取，使得每一位二进制异或和都是0，这可以通过高斯消元求出自由元个数为r，答案即是 $2^n - 2^{n-r}$。

Problem L

Solved by oxx1108 && Xiejiadong. 1:36:03(+4)

罚时是Xiejiadong贡献的。SPFA被卡了。

题意：可以将$k$条边的权值变为0，求从$1$到$n$的最短路径。

题解：按照$k$，把每一个点都拆成$k$个点来跑最短路。

Xiejiadong写了个SPFA被卡了，不知道为什么。听出题人说并没有可以卡SPFA，验题人还用SPFA拆点最短路跑过去了。可能是写的太丑了。oxx1108重写了一遍dij就过了。