2019 ICPC China Xi'an Invitational Programming Contest

Replay

Xiejiadong:

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

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

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

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

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

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

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

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

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

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

Kilo_5723:

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

• 两道出锅的题目都是我写的，差点心态崩 twice 。

• C 题 出 题 人 签 到 大 失 败（大嘘）。

• C 题样例锅了导致榜上一直没人交，也就产生了很多“本来能一血”的假象。实际上在队友告诉我 C 过了一片（看错题号）之后写完没过样例，手算了一遍感觉肯定是题目锅了之后，差点直接交一发等 rejudge（抢一血），后来冷静一下求稳放弃了。不过这时候榜上已经有一发 WA 的了，可能人家不仅开得准、写得快，而且自信又果断，比不了。

• L 题为了求稳暴力反复检查了好多次，浪费了一些时间（明明平时我最莽）。深刻意识到了现场交题时不可能像平时一样放松。

• 最后一道空间树 + 三维并查集，空间树用了很愚蠢的写法导致三维并查集没调完。感觉这场的锅全都是我背，瑟瑟发抖。

Weaver_zhu:

• 热身赛终于给 python 的 eval() 一个大秀的机会

• 上完厕所回来会感觉机房的门相当于一个巨型暖气

• 出题人计算几何有问题

• 有一题看了下队友刚交上去的代码，发现有个细节假了。结果还没出来就建议直接改了再交，结果竟然过了。

• 上来直接推了 B 的式子，结果到结束也没能开始写代码

• I 题一直以为自己的方法很完美，也不难写，也测了很多数据。结束前还没出来时背后出了好多汗，锅坐实了。

• 以后前一天晚上得多睡一会，以及最后一小时大概率是要有取舍的。

Problem A

Solved by Xiejiadong. 00:00 (+)

贪心。签到。

Problem B

Unsolved.

Problem C

Solved by Kilo_5723. 01:33 (+)

题意：给定一个圆，圆之外中心高度以下的部分不能被经过，圆内部也不能被经过，求圆上最低点到圆外中心高度之上任意一点的最短路。

题解：先把原点放到圆心，再把终点 $x$ 坐标变成绝对值。$\frac {1}{4} \pi r$ 的路径是必走的，然后如果 $x>r$，从 $(r,0)$ 直线走过去就可以了，如果 $x<r$，算一下要走过的弧度，再求之后的直线距离即可。

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 (+)

题意：给定一棵有 $n$ 个节点的树，求这棵树上每条路径上，边权异或和为 $0$ 的子路径的数量和。

题解：定义 $dep(u)$ 是 $u$ 的深度 (根节点深度为 $0$)，$son(u)$ 是以 $u$ 为根的子树中的节点数，$E(u,v)$ 为 $u$ 到 $v$ 的路径，$F(u,v)$ 是 $u$ 到 $v$ 的路径的边权异或和。

深度为对边权异或和的路径 $E(u,v)(u \neq v,dep(u)<=dep(v))$ 分类讨论。

如果 $u$ 不是 $v$ 的祖先，这条路径对答案的贡献是 $son(u) \times son(v)$。否则，这条路径对答案的贡献是 $son(u) \times (n-son(v))$。

把第一类路径拆成 $E(u,lca(u,v))$ 和 $E(v,lca(u,v))$ 两条链，那么要处理第一类路径，我们只要对每个点所有在其子树中的 $v$ 和每一个 C，维护 $F(u,v)=C$ 的 $son(v)$ 之和即可。

Problem K

Unsolved.

Problem L

Solved by Kilo_5723. 00:36 (+)

题意：给定一个长度为 $n$，每个元素均不同的序列，可以将偶数位和前面的奇数位互换，可以将前一半和后一半互换（如果有中间元素，中间元素不变），问可以从初始序列达到多少个不同的序列。

题解：找规律。对 $n=1,3$ 的情况特判，剩下的情况里 $n \%4=0$ 时答案是 $4$，$1$ 时是 $2n$，$2$ 时是 $n$，$3$ 时是 $12$。

Problem M

Solved by Xiejiadong. 00:50 (+)

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

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

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

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