2019 ICPC Shanghai Onsite

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

Unsolved.

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Unsolved.

Problem L

Unsolved.

Problem M

Unsolved.