2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018)

From EOJ Wiki
Jump to navigation Jump to search

One,Two,Three,AK

Xiejiadong签到失败,承担了所有的罚时。

dreamcloud全场最佳。

Problem A

Unsolved.

Problem B

Solved by Xiejiadong.

签到题,题意有毒。

Problem C

Solved by dreamcloud.

Problem D

Solved by dreamcloud.

Problem E

Solved by oxx1108.

Problem F

Unsolved.

Problem G

Unsolved.

Problem H

Solved by dreamcloud.

Problem I

Solved by dreamcloud.

Problem J

Solved by Xiejiadong.

题意:给出00、01、10、11子序列的个数,构造符合题意的01串。

题解:首先根据00和01可以计算出0和1的个数。

假设0的个数为$x$,1的个数为$y$,当且仅当$b+c=xy$的时候有解。当然,不存在这样的$x$、$y$也无解。

然后就是考虑怎么构造$b$的个数,线吧素偶有的1放在0前面,此时$b=0$,然后暴力的把1移到所有的0后面,每次$b+=x$,最后剩下$b%x$,表示最后一个1前面0的个数。

需要注意$a=0$的情况有两种可能,$x=0$或者$x=1$,$d$的情况也是如此。

注意特判$a=0,b=0,c=0,d=0$的情况

Problem K

Solved by dreamcloud.

ECNU Foreigners

Problem A

Solved by zerol. 04:03 (+1)

题意:给一些青蛙,问有多少能跳出去。青蛙有身高体重和跳跃能力,青蛙的承载重量必须小于自重。

题解:状态 $f[w]$ 表示拥有 $w$ 承载力的最大身高和。按体重从大到小排序,设体重为 $w$,身高为 $h$,那么有 $f[x]=\max\{f[min(w-1,x-w)]+h\}$,在 $w$ 和 $2w-1$ 之间的暴力更新,大于 $2w$ 的直接取最大值,由于体重从大到小,所以在移动右边界时更新最大值就好了。最后刷一遍单调性计算答案。

Problem B

Solved by ultmaster. 00:20 (+)

没人想看的签到 1。

Problem C

Solved by ultmaster. 00:29 (+)

没人想看的签到 2。

Problem D

Solved by ultmaster. 03:49 (+)

题意:在一个无向图中,顶点 1 开了家披萨店。于是经常会有顶点上冒出来说,我在 $s_i$ 时刻要了一份披萨,这份披萨要 $t_i$ 时刻才能好。你是这个无向图上唯一的可怜的送货员,你必须先到先服不能擅自更改顺序。要求合理安排送货流程使得等待时间最长的顾客的等待时间最短。

题解:二分答案。考虑验证答案:dp[i] 表示送完 $i$ 份披萨回到披萨店的最早时间。然后转移下去即可。注意转移的时候要维护三个量:能出发的最早时间,路上要花费的时间,以及最迟出发时间。如果出发时间晚于最迟出发时间则跳出不再更新。由于每个顶点所需求的最迟出发时间只与该点会带来的路上时间有关,所以可以方便的累加。

队友都不想写,结果扔给我写了。(怎么回事啊?

Problem E

Solved by zerol. 01:49 (+)

题意:炉石传说。双方至多有 6 个随从,问打一个伤害为 k 的火山喷发,对面随从死光的概率。

题解:概率记忆化搜索,状态不会太多。

Problem F

Unsolved.

自闭了。

Problem G

Unsolved.

Problem H

Solved by kblack. 02:26 (+1)

题意:一堆工作一会儿摸一会儿的除草剂,选能平均一周修一次的最便宜的。

题解:$(t+r)$ 不大,模拟就行了。CF 炸了,修得(又)特别慢。

Problem I

Solved by kblack & ultmaster. 01:16 (+)

模拟题。kblack 声控使用 TNT 编程。

Problem J

Solved by zerol. 00:45 (+)

题意:构造一个 01 串,使得 00, 01, 10, 11 子序列的出现次数分别为 a, b, c, d。

题解:0 的个数和 1 的个数可以由 a, b 得到(注意为 0 时可能有 0/1 个),先检查 $c_0 \times c_1 = b+c$,然后把 1 都塞在 0 前面,一个一个尽可能往后扔。

Problem K

Solved by kblack. 00:24 (+1)

温暖的签到。膜炸了,因为 CF 炸了所以修得很慢。