2019 ICPC Shanghai Onsite

From EOJ Wiki
Jump to navigation Jump to search

Replay

Xiejiadong:

  • ICPC·Tree Round
  • 怎么感觉这场的题目,按照垃圾分类的传统全是我的题。
  • 被 F 关了两个小时,没有模板纯自己发明,好在发明成功了。
  • 第一次打星参赛。
  • 没想到一场区域赛可以引起一场如此持久的对线。

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

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)

Problem L

Unsolved.

Problem M

Unsolved.