Nordic Collegiate Programming Contest 2018 [NCPC2018] 题解

A. Altruistic Amphibians

unsolved

B. Baby Bites

solved (0:08, +1)

逐个检查即可。

C. Code Cleanups

solved (0:17)

逐日模拟即可。

D. Delivery Delays

solved (4:55)

首先跑最短路获取APSP。

二分答案,然后dp出送完前i单最早时间,或者不可行

E. Explosion Exploit

solved (3:23)

可以用dp的思想转移。由于随从的顺序无关,可以将他们的血量排序,总状态数会大大减少。

F. Firing the Phaser

unsolved

G. Game Scheduling

unsolved

H. House Lawn

solved (0:34)

如果\(\frac{10080rc}{t+r} \geq l\),则说明可行。记录可行的机器中,最便宜的那些机器的名称即可。

I. House Lawn

solved (1:00 +1)

由于相邻两数相差至少为一倍,只需要从大到小排序,然后能减就减。最后结果为0,则选中的那些就是答案。

J. Jumbled String

solved (1:57 +2)

可以根据00和11子序列的数量算出0和1的数量,然后根据01和10子序列的数量调整0和1的位置。注意若干边界情况。

K. King’s Colors

solved (3:07)

用最多k种颜色染色有\((k-1)^{n-1}k\)种方案。用恰好$k$种颜色的方案数可以用容斥算出。

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注