2018-2019 ICPC, NEERC, Southern Subregional Contest

From EOJ Wiki
Jump to navigation Jump to search

Problem A

Solved by ultmaster. 00:20 (+)

题意:求一个最小的数使得各位数字之和为 $s$,且能被 $d$ 整除。

题解:BFS、最短路、DP。爱叫什么叫什么。

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)

题意:给一个无向图的所有边染色。颜色种类没有限制,每种颜色最多用两次,同时要保证跟一个点相连的边的颜色种类不超过 $k$。

题解:首先如果有个点度数大于 $2k$ 就凉透了。

考虑某一个点度数是 $d$,如果 $d$ 小的话肯定是可以乱染的。$d$ 大的时候,一定有 $d-k$ 种颜色是要用两遍的。也就意味着一个点要「占有」$2(d-k)$ 条边,不顾旁人地给它们两两配对,染成相同的颜色。之所以可以「不顾旁人」,是因为一旦两条边染成了相同的颜色,就不能有第三条边跟它们颜色一样了。所以一条边只能被至多一个点「占有」。建立一个左边是点,右边是所有边的图模型,跑最大流即可。有解条件是最大流是 $\sum 2(d-k)$。

DIRT1: WA 了。

DIRT2: 打印下来查。查了很久都觉得挺对的。有点自闭。发现当前弧优化的初始化可能是错的(事后证明没有问题),改了交,没有改善。

DIRT3: 怀疑人生了,加了两个自我 check(想看看是第一类错误还是第二类错误),结果成功 RE 了。对了个拍,发现是 n m 傻傻分不清。。。

Problem J

Solved by kblack. 02:06 (+3)

题意:给若干字母,要求分成 $n$ 个和 $m$ 个两组,使得两组间同种字母数量乘积和最少。

题解:只有一种字母会同时出现在两组中,枚举这个字母,背包确定在左边的其他字母的数量,然后更新答案。

Problem K

Solved by zerol. 00:07 (+)

温暖的签到。

Problem L

Upsolved by ultmaster.

题意:将一个无向图分成 $r$ 块,使得每一块内部的点的度数都是偶数。求最小的 $r$。

题解:可以猜想 $r$ 最多是 2。可以对每个点设一个变量 $x_i$ 表示属于 0 还是属于 1。然后可以列入 $\mathbb{Z}_2$ 意义下的 $n$ 个方程。用 bitset 压位高斯消元即可。

证明:方程无解当且仅当一个子集方程组消出了 $0=1$。右边意味着这奇数个点的度数总数是奇数;同时这些方程的诱导子图的点数总数是奇数。同时,一开始偶数度数的点最后度数还是偶数;一开始奇数度数的点最后度数还是奇数。子图总度数是奇数,矛盾。