2019 ICPC China Xi'an Invitational Programming Contest

Replay

Xiejiadong:

• 主办方为了增加收入(?)，现场座位挤在一起。

• 四点求面积这种题目都能锅，提前预感到了正赛锅会比较大。

• 果然正赛连样例都能锅。

• 题面表述乱七八糟，全靠连蒙带猜得知题意。

• H 题题面表述不清，大概程序有一个坑点，正准备再交的时候，上一发显示 correct 。

• 听说 E 题连 $O(nq)$ 的暴力都能过，出题人造树的数据连个链都没有，怕是用脚造的数据。

• 评测队列积压严重。甚至 $5$ min 才能出结果。

• 打印效率奇低，甚至送过来的还是一部分代码。

• $0$ min 过签到都没抢到一血，看来都提早开题了。

• 比赛打到 12 点的时候就开始犯困了，想来想去都是 GCJ 的锅。

Kilo_5723:

• 空调坏了，赛场热的一（——）

Weaver_zhu:

Problem A

Solved by Xiejiadong. 00:00 (+)

贪心。签到。

Problem B

Unsolved.

Problem C

Solved by Kilo_5723. 01:33 (+)

Problem D

Solved by Weaver_zhu. 01:30 (+)

Problem E

Solved by Xiejiadong. 04:29 (+1)

题意：支持树上某一点到根路径上所有点 and 一个值， or 一个值，链上做 nim 游戏。

题解：显然 nim 游戏就是求个异或。

常规操作，拆位。

and 一个值和 or 一个值，转换一下就是链上所有的数置 $0/1$ ，线段树维护就好了。

树上的链处理，树链剖分一下。

（模版没有，自己发明，初始化锅了，好久才发现。

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Unsolved.

Problem I

Unsolved. (-4)

Problem J

Solved by Kilo_5723. 02:28 (+)

Problem K

Unsolved.

Problem L

Solved by Kilo_5723. 00:36 (+)

Problem M

Solved by Xiejiadong. 00:50 (+)

题意：可以给一个飞船升级，每次升级花费 $c$ ，可以通过的路径长度 $+d$ ，可以通过的边总数 $+e$ 。求最小的花费，能从 $1$ 到 $n$ 。

题解：二分最小的升级次数。

验证的时候从 $1$ 开始 BFS ，所有能够拓展的边全部拓展，显然 BFS 先到的满足了通过边数最小的要求，可以拓展的边满足了可以通过的路径长度要求。

判断此时 $1$ 到 $n$ 是否联通即可。