2018 ACM-ICPC China Xi'an Invitational Programming Contest
杂事
ultmaster
- $pc^2$ 差评。
- 一直 Compilation Error。然后重测了一下 CE 变 WA 了。
- 做得非常不顺,前期一直在铁牌区。
- 开 J 可能是正确的。然而开完 J 就挂机了。(我太菜了,并没有做出另一道题。)
- 想来想去都是 飞机 / 公交车 / GCJ 的错啊!
- 这比赛没人打的,甚至都没人带榜。有可能放在区域赛,打成这样,就 Ag 了吧。
- SJTU 还是强啊。
- 除了差点没上机零贡献以外,
我没背锅,罚时都是队友贡献的。
zerol
- 槽都被吐完了。。。
- 垃圾热身赛,数据范围都没有。
- 打印代码送的速度很慢,甚至有的代码甚至都不送来。
- 榜很垃圾,甚至封榜后连 ?都没有了。还有榜上垃圾的 1 tries 和 2 try,洋文水平不行。CE 算罚时,真的垃圾。
- 空调太冷,凉凉。
- CE 太坑了,都问了还回答有 C++14,明明连 C++11 都不支持。编译选项都能出问题,垃圾。后来重测了,CE 变 WA,美滋滋。
- $pc^2$ 选语言甚至有两个 Python,2 和 3 都不标。
- A 题假得不行,后面还有题意不清的题。
- 背锅,背锅,大概一半的锅。
kblack
- 正赛的槽还真的吐得差不多。。。
- 自带广告的打印代码甚至可以向 ICPC 举报?(大雾)
- 当收到发吃的的中断的时候,志愿者会挂起其他所有任务,优先发吃的。
- 甚至坐下来,喝了拿铁还在打哈欠,都是 GCJ 的错!
- 以为 B 题简单是,是因为上厕所时,经过了气球室看到了大量某色气球(相对其他颜色),感觉可能原本是简单题。
- 现在看可能是志愿者不清楚题目难度,初期按 ABCD 的顺序打了气球了吧。。。
- 可能热身赛,正赛各丢了两个一血。。。
- 主动抢锅!其实至少 $\frac{3643015}{5464523}$ 的锅都是我的!谁都别和我抢!
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)
题意:求多条线段总共有多少个不同的交点。
题解:n²肯定可解,考虑解决去重的精度问题,没敢直接上double,于是在写了在膜意义下的版本,用 set T 了一发,改成 sort 以后 wa 了,盯着看了很久才意识到自带剩余系的 point 类用于计算差积的时候符号会爆炸(虽然叉积写了单独的版本,但是 point 没有),随后 ac。
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 去,丢了一血,榜上都过了一片了,才过。
题意:区间改 y'(t) 区间询问 y(t)。 题解:bit / 线段树维护当前增量和前面要减去的部分即可。
zerol:
- 调到板子里的时候,就已经预示着要凉了。
- 没想到 kblack 优化板子结果改错了,难以置信(一口巨锅)!