2018 ACM-ICPC China Xi'an Invitational Programming Contest
杂事
ultmaster
- $pc^2$ 差评。
- 一直 Compilation Error。然后重测了一下 CE 变 WA 了。
- 做得非常不顺，前期一直在铁牌区。
- 开 J 可能是正确的。然而开完 J 就挂机了。（我太菜了，并没有做出另一道题。）
- 想来想去都是 飞机 / 公交车 / GCJ 的错啊！
- 这比赛没人打的，甚至都没人带榜。有可能放在区域赛，打成这样，就 Ag 了吧。
- SJTU 还是强啊。
- 除了差点没上机零贡献以外，
我没背锅，罚时都是队友贡献的。
Problem A
Solved by zerol. 00:43 (+2)
题意：给两个数 a 和 b，问对 a 或 b 移位后相加点后得到 a b 之积的使用加减的最少次数。
题解：题意不明，但却是理解了出题人的意图，结果搞了一通假算法。后来出题人发现自己是假的，于是在 clarification 中直接发了个题解（可能的意思：标程是这么做的，你们也这么写，就能过），然后就过了。
Problem B
Unsolved.
ultmaster: 听 kblack 说这题是傻逼题。做了两个小时。于是就挂机了。（甩锅啊！）
Problem C
Solved by ultmaster. 02:36 (+)
题意：（简化后）你手上有些钱，现在有 $n$ 块宝石。对于每块宝石，你可以直接以 $p_i$ 卖掉，或者用 $b$ 元（前提是你得有钱）切开，然后以 $q_i$ 卖掉。求最大收益。
题解：01 背包。先把切开会亏的直接卖掉。如果你手上已经 $b$ 元了，那么怎么都可以卖了。关键是手上如果没有 $b$ 元，你得先筹到 $b$ 元。方法是假设可以赚的我们全部赚到。接下来计算我们最少得亏多少钱。$dp(i,j)$ 表示考虑前 $i$ 个宝石，筹到 $j$ 元最少要花多少钱。然后乱搞一下就好了。注意 bound 上界。
ultmaster:
- 被 \r\n 坑的选手，显然没怎么做过题。
- 已经准备好打印代码了，没想到居然直接返回了 Yes。
Problem D
Solved by zerol. 00:58 (+3)
题意：Nim 游戏，每次对于一个有 $n$ 个石子的石子堆，可以拿走 $\lceil n/2 \rceil$, $\lceil 2n/3 \rceil$, $\lceil 3n/4 \rceil$ 个石子。求谁获胜。
题解：能打表的无脑打表，发现 SG(x) = (64 - __builtin_clzll(x)) % 3，直接异或就好了。
zerol:
- 这题我要背大锅。
- 一开始 mex 写错 WA 一发。（由于 CE 的缘故，WA 买一送一）
- 后来改的时候只改了一半，又 WA 一发。
Problem E
Solved by zerol. 00:17 (+)
题意：问若干条棍子能不能组成一个简单多边形。
题解：签到。
Problem F
Unsolved.
基于 F 的魔咒，一开始就读了。然而没人过，所以到最后都没怎么想。
题意：最短路，经过每个点时总花费一定要大于某个值。
Problem G
Solved by kblack. 01:55 (+2)
题意：求多条线段总共有多少个不同的交点。
Problem H
Unsolved.
做完 J 之后就玩这题了。当然大家的智商都早已经不在线了。
题意：$T(1)$ 是一条长度为 $p$ 的链，$T(2)$ 是一条长度为 $q$ 的链，$T(k)$ 是一个左子树是 $T(k-1)$，右子树是 $T(k-2)$ 的二叉树。玩一个游戏，每步操作是删掉一个子树。谁不得不删根谁就输。求先手要获胜，第一步有多少种不同的操作。
Problem I
Unsolved.
题意：有 $n$ 个数，初始值都是 $n$。先给出 $n$ 个询问，每次询问查询 $[i+1,\min(n, a_i)]$ 中有多少个数大于等于 $i$。每次询问完之后对 $[l_i,r_i]$ 这段区间减去 $x_i$。
似乎是简单题？然而题意上存在巨大的障碍？而且榜上也没有信息。
Problem J
Solved by zerol. 04:19 (+11)
题意：一棵树，每个节点上的权值都是 0 或 1。每次操作可以 flip 一条链，或者查询跟某个点距离不超过 1 的所有节点的总权值。
题解：考虑所有点距离不超过 1 的点的个数之和是 2n。如果个数少的，暴力查，个数多的，在修改时维护好。修改时用树链剖分+树状数组维护每个节点上的权值。对于修改的路径，可能有至多 3 个点在某个邻居多的点周围，然后找出这些点，根据它们当前的值修改那个邻居多的点的答案。
zerol:
- 这题我一开始维护答案错了，被 kblack 指出。
- 后来就出来一个问题，怎么找一条路径上到一个点距离不超过 1 的所有点。然后 kblack 给我秀了一手如何用树链剖分从一个点向上爬对应深度。然后开始 T，然后开始优化常数，然后又 T，然后心态开始爆炸，后来 ultmaster 指出那个 gogogo 函数不大对，结果果然假得很，随便测试一下这个函数就死循环了（但是光是编数据可能检测不出这个函数的问题），然后修复了一通还是过了，此时丢掉了一血。
Problem K
Solved by kblack. 01:10 (+4)
一开始就开了，WA 来 WA 去，丢了一血，榜上都过了一片了，才过。
zerol:
- 调到板子里的时候，就已经预示着要凉了。
- 没想到 kblack 优化板子结果改错了，难以置信（一口巨锅）！