ACM-ICPC 2018 Nanjing Online Contest
ECNU Foreigners
Problem A
Solved by Mathematica. 00:13 (+)
Problem B
Solved by ultmaster. 01:04 (+)
Problem C
Solved by ultmaster. 03:24 (+4)
Problem D
Solved by ultmaster. 04:17 (+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 了。
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 和 主席树之间的东西。
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(+)
Problem C
Upsolved by oxx1108. 4:59:46(-7)
Problem D
Solved by oxx1108. 3:23:04(+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)
Problem H
Unsolved.
Problem I
Solved by Xiejiadong. 2:56:25(+)
题意：求字符串中所有回文字串的和。
题解：回文自动机模板题。加一个处理回文子串大小的东西，最后把本质不同的回文子串全部相加就好了。
Problem J
Solved by dreamcloud. 0:26:57(+)
Problem K
Unsolved.
Problem L
Solved by oxx1108. 13:36:03(+4)
罚时是Xiejiadong贡献的。SPFA被卡了。