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)

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_clz(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 的所有节点的总权值。

Problem K

Solved by kblack. 01:10 (+4)

一开始就开了,WA 来 WA 去,丢了一血,榜上都过了一片了,才过。