2018 ACM-ICPC China Xi'an Invitational Programming Contest

From EOJ Wiki
Jump to navigation Jump to search

杂事

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 优化板子结果改错了,难以置信(一口巨锅)!