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)
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$ 个石子。求谁获胜。
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 的所有节点的总权值。
Problem K
Solved by kblack. 01:10 (+4)
一开始就开了，WA 来 WA 去，丢了一血，榜上都过了一片了，才过。