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$ 是否联通即可。