2018-2019 ICPC, NEERC, Southern Subregional Contest

Problem A

Solved by ultmaster. 00:20 (+)

Problem B

Solved by kblack & zerol. 03:48 (+1)

题意：有一些子网的黑白名单，要求用数量最少的黑名单覆盖所有黑名单且不误伤白名单。

题解：看成二进制数的问题，子网就是 32 位二进制数的一个前缀，全部插进 trie，然后 dfs 一遍。如果当前子树中全是黑名单就采用该结点对应的子网且不进入递归，否则左右子树递归。

Problem C

Solved by kblack. 00:55 (+)

题意：若干天时间有物品和价格，每天都需要若干个，问最少花多少钱。

题解：以价格为下标扔进树状数组里二分。

Problem D

Solved by kblack. 00:12 (+)

温暖的签到。

Problem E

Solved by zerol. 01:59 (+)

题意：选取一个最优的 d 使得在 t 时间内完成最多的任务。策略如下，只会做耗时不超过 d 的任务，每做 m 个任务都会休息之前 m 个任务的耗时和等长的时间。

题解：将所有任务按耗时排序，从小到大一批批加进去，然后用二分时间判断能完成的最多任务数，可以树状数组上二分计算前若干个任务的耗时和。

Problem F

Solved by zerol. 00:45 (+)

题意：有一些带权的东西标号是 11, 01, 10, 00 之一，要求选择它的一个子集，使得第一/二位是 1 的不少于子集大小的一半，求最大的权重和。

题解：可以把 0 看成 -1，那么条件转化成了第一位以及第二位的和非负。11 先全吃了。01 和 10 分别排序后按从大到小的顺序一对一对吃，随后剩下的 01/10 和 00 再一起从大到小排序，能吃几个就吃几个。

Problem G

Solved by zerol. 04:44 (+2)

题意：有一排格子，格子上有数字，英雄路过的时候血量就会加上那个值，如果为负就挂了，而且这个数字是一次性的。你有若干个带有血量的英雄，要让他们在某个点集合。你可以安排他们的集合地点，以及出发的顺序。一旦出发，只能朝集合点前进。求一个不会挂的方案或者输出无解。

题解：预处理每个英雄向左向右能到达的最远位置。枚举集合地点。考虑左侧过来的，按离集合地点从近到远排序，如果能直接到终点就出发，否则就最后再走。如果最远的那个不能到就 GG 了。右侧同理。

Problem H

Solved by kblack. 00:28 (+)

Problem I

Solved by ultmaster. 03:54 (+3)

Problem J

Solved by kblack. 02:06 (+3)

Problem K

Solved by zerol. 00:07 (+)

温暖的签到。