Difference between revisions of "2019 ICPC Shanghai Onsite"
Jump to navigation
Jump to search
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
Line 43: | Line 43: | ||
== Problem F == | == Problem F == | ||
− | + | Solved by Xiejiadong. 04:34 (+3) | |
+ | |||
+ | 题意:要求支持树上三个操作:链加,链乘,链覆盖,维护链的立方和。 | ||
+ | |||
+ | 题解:树上的问题,通过树链剖分就转换成区间问题了。 | ||
+ | |||
+ | 于是就变成了维护区间立方和,要求支持区间加、乘、覆盖。 | ||
+ | |||
+ | 区间加、乘、覆盖需要三个延迟标记维护。 | ||
+ | |||
+ | 立方和的维护,通过立方和的展开来做,同时维护平方和以及和即可。 | ||
+ | |||
+ | 没什么意思的胖题,挺难写的,线段树部分调了挺久。 | ||
== Problem G == | == Problem G == |
Revision as of 06:08, 3 December 2019
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.