Difference between revisions of "2018-2019 ACM-ICPC Nordic Collegiate Programming Contest (NCPC 2018)"
Line 117: | Line 117: | ||
Solved by kblack & ultmaster. 01:16 (+) | Solved by kblack & ultmaster. 01:16 (+) | ||
− | 模拟题。kblack <del>声控</del> | + | 模拟题。kblack <del>声控</del>'''使用 TNT''' 编程。 |
== Problem J == | == Problem J == |
Revision as of 11:18, 10 November 2018
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 . 04:03 (+1)
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 . 01:49 (+)
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 . 00:45 (+)
Problem K
Solved by kblack. 00:24 (+1)
温暖的签到。膜炸了,因为 CF 炸了所以修得很慢。