2019 CCPC Final

Replay

Xiejiadong:

Kilo_5723:

Weaver_zhu:

Problem A

Solved by Kilo_5723. 00:55 (+2)

Problem B

Unsolved.

Problem C

Solved by Weaver_zhu. 00:46 (+)

Problem D

Unsolved.

Problem E

Solved by Weaver_zhu. 02:30 (+)

Problem F

Solved by Xiejiadong. 01:26 (+)

题意：给出 $x$ 求任意一组解满足 $a^3+b^3+c^3=x$ 且 $|a|,|b|,|c|\le 5\cdot 10^3,0\le x\le 200$ 。

题解：考虑预处理出所有 $|a|,|b|\le 5\cdot 10^3$ 的情况，枚举所有的 $x$ ，再枚举 $c$ ，判断是否存在这样的 $a,b$ 。

直接用 map 是不大行的，无论是时间复杂度还是内存上本地都跑不出来，差点电脑死机了。

考虑用数组存下所有的情况，排序以后，再在其中二分。

打表直接输出即可。

Problem G

Unsolved.

Problem H

Solved by Kilo_5723. 03:57 (+1)

Problem I

Unsolved.

Problem J

Unsolved. (-5)

Problem K

Unsolved.

Problem L

Solved by Xiejiadong. 03:24 (+)

题意：给出一棵树，树上每个节点都有一个字母，每次可以选择一个节点，从它开始向他的父节点走，沿路记下字母。

每次询问给出一个节点以及走的步数，求整棵树上可以走出多少这样的字符串。

题解：考虑如果对于每一个节点变成向他的孩子走，题目就转换成了后缀的问题。

如果能够处理出来所有节点往下走的字符串，建立 SAM ，在其中做子串定位以及统计当前子串状态出现的次数就好了。

考虑到这是一个树，每次记录当前节点对应在广义 SAM 的节点编号，回溯的时候，暴力的跳父亲的 SAM 节点，在 insert 即可。