2019 ICPC Shanghai Onsite
Replay
Xiejiadong:
- ICPC·Tree Round
- 怎么感觉这场的题目，按照垃圾分类的传统全是我的题。
- 被 F 关了两个小时，没有模板纯自己发明，好在发明成功了。
- 一进场就发现 K 气球颜色不是 black 了，就知道这个 K 一定有问题，于是开场就看了 K ，可以上来忘记考虑数据组数 TLE 了一发。
- 第一次打星参赛。
- 没想到一场区域赛可以引起一场如此持久的对线。
Kilo_5723:
Weaver_zhu:
Problem A
Unsolved.
Problem B
Solved by Xiejiadong. 00:32 (+)
题意：判断给出的所有字符串是否存在其中一个是另一个的前缀。
题解：直接把每一个字符串插入字典树，插入一个单词的时候，以下两种情况就是产生前缀关系了：
- 单词的结尾是已经存在的（为已经插入字符串的前缀）；
- 插入的过程中遇到了单词结尾的标记（已经插入的字符串存在当前串的前缀）。
Problem C
Unsolved.
Problem D
Solved by Kilo_5723. 00:44 (+)
题意：给出一张 $n$ 个点的完全图，要求移除尽可能多的 $n$ 个点的生成树。
题解：$n=2k$ 时，可以从 $n-2$ 的情况推到 $n$：$n-2$ 的情况下有 $\frac{n-2}{2}$ 棵生成树，对第 $i$ 棵生成树连接 $2i-1$ 到 $n-1$，$2i$ 到 $n$ 的边，再新建一颗生成树，有所有 $2k$ 到 $n-1$，$2k-1$ 到 $n$ 的边，再加上一条 $n-1$ 到 $n$ 的边。
对于 $n=2k+1$ 的情况，从 $n-1$ 的第 $i$ 棵成树连接一条 $i$ 到 $n$ 的边。
Problem E
Solved by Kilo_5723. 02:15 (+2)
Problem F
Solved by Xiejiadong. 04:34 (+3)
题意：要求支持树上三个操作：链加，链乘，链覆盖，维护链的立方和。
题解：树上的问题，通过树链剖分就转换成区间问题了。
于是就变成了维护区间立方和，要求支持区间加、乘、覆盖。
区间加、乘、覆盖需要三个延迟标记维护。
立方和的维护，通过立方和的展开来做，同时维护平方和以及和即可。
没什么意思的胖题，挺难写的，线段树部分调了挺久。
Problem G
Unsolved.
Problem H
Solved by Xiejiadong. 03:16 (+1)
题意：要求将树切割成 $k$ 部分，使得每一部分点权和的最大值最小。
题解：显然二分答案，考虑如何验证答案。
$f[i]$ 表示当前结点 $i$ 所在的联通块的点权和。
显然对于每一个节点，将其所有孩子的 $f[x]$ 排序以后，从小到大依次往父亲里塞。
塞不下的，就只能切断了，也就是形成单独的联通块，塞进父亲里的，更新到父亲的 $f[fa]$ 中，可以继续和上面的节点合并。
如此可以判断出在有限的点权和情况下，做多可以切割的块数。
Problem I
Unsolved.
Problem J
Unsolved. (-6)
Problem K
Solved by Xiejiadong. 00:15 (+1)
题意：保留最多的边，使得图中没有奇环。
题解：看到奇环，马上就能联想到二分图。
因为只有 $16$ 个点，于是可以枚举每一个点属于哪一边，然后只保留两边之间的边，枚举所有的情况，求保留做多的边数即可。
Problem L
Unsolved.
Problem M
Unsolved.