ACM/ICPC2016沈阳网络赛(不完全)解题报告

比赛地址:


1003.hannnnah_j’s Biological Test

题目大意:

圆周上有N个不同的椅子,要让M个相同的人坐在上面,使得两人之间至少隔K把空椅子,求方案数(模1e9+7)。

0

题解:

考虑每两个人之间隔了几把椅子。可以发现,一共有M个数,和为N-M,且每个数都>=K.将每个数都减去K-1,即得到:M个正数之和为N-K*M,方案数为C(N-K*M-1,M-1).需要乘以圆排列的N,同时每个方案被算了M次,再除以M。
答案为:C(N-K*M-1,M-1)*N/M。需要用预处理阶乘的方法计算组合数。注意特判M=1的情况。

代码:

1007.odd-even number

题目大意:

对于一个十进制整数,如果它的数位表示中,连续的奇数总有偶数个,连续的偶数总有奇数个,就称它是“好”的。给定1 <= L,R <= 9e18,求[L,R]内“好数”的数量。

题解:

首先容斥一下,只需要求“<=x的好数”这样一个问题。


数位DP,枚举“从哪一位开始和x不同”。例如,x为47397456,我们就需要求一些例如“有多少个形如47395???的好数”这样的问题。特别注意位数比x少的那些数,即类似于“有多少个形如????????的好数”这种问题。对此,我们可以先DP出来一个数组F:F[i][j][n],其中i=0/1/2代表开头一段是偶数/奇数/未开始,j=0/1代表开头一段有偶数/奇数个(如果i=2就规定j=0),n代表后面有n个未定位,F[i][j][n]就是这种情况下的“好数”个数。例如,形如“47395???”的好数就有F[1][0][3]个,形如“????”的好数就有F[2][0][4]个。

代码:

1008.oasis in desert

题目大意:

给定一张N<=500的边带权无向图和一个整数K。定义:

1. “最大危险集”:是顶点集的一个子集,该集合中任意两顶点的最短路大于K。最大危险集是所有这种集合中最大的。

2. “最小安全集”:是顶点集的一个子集,如果全部顶点中,任意二者的最短路小于等于K,该集合中必须至少包含其中的一个。最小安全集是所有这种集合中最小的。

要求找出一个集合,它既是最大危险集,又是最小安全集。若有多组解,输出字典序最小者。无解输出“Impossible”。

题解:

2016/11/23更新:

感谢@cmershen 的评论,他指出了这个做法的错误:

“楼主你好,你这个1008题的题解是错的,而且代码交上去也是wa。
我认为错在这里:“注意,这张图有可能不连通,但这并不影响结论,因为每一个连通块都应符合上述条件。”

如果两个子图不连通,其中每个子图都有符合题意的集合,那么按LZ代码的思路,答案应为两个子图的并集。如果我从这两个子图里分别拿出一个点,他俩根本就是不可达的,题中的“minimum distance longer than K”就没有意义。


还有,二分图就算是一边有N/2个点,也不一定存在完美匹配的。。。。。。我在LZ的代码上补充了这两种情况,提交到hdu 5899上,确实AC了。

详见评论区。就是说,下面的题解和代码都少考虑了这些情况,请大家不要被误导(我也懒得改代码了(逃)。

首先建一张新图,其中两点之间连一条单位边当且仅当它们在原图中的最短路<=K。

我们不妨假设一个点在集合中,看看会发生什么:

1. 它本身在集合中。
2. 和它相邻的点不在集合中。
3. 和2中点相邻的点在集合中(这是最小安全集的规定)。
4. 和3中点相邻的点不在集合中。
5. 和4中点相邻的点在集合中。
……

可以发现,这实质上是对图进行二分染色。换言之,这张图必须是二分图。

在此基础上,显然“最大危险集”就是二分图的最大独立集,“最小安全集”就是二分图的最小支配集。这二者应当相等。我们注意到,最小支配集的大小等于匹配数,而最大独立集的大小等于N-匹配数,换言之,应当有匹配数=N/2。也就是说,图的左右两边应当一样大,并且有完备匹配。

因此我们总结出三条(其实是两条)判据:

1. 图是二分图。
2. 二分图的两边均有N/2个点。
3. 二分图的匹配数为N/2.

注意,这张图有可能不连通,但这并不影响结论,因为每一个连通块都应符合上述条件。

如果判断图是合法的,那么取字典序较小的那一边输出即可。注意输出格式:行末无空格,而且如果输出0个点,就不应换行。我们队当时PE了三次。

代码:


1009.QSC and Master

题目大意:

在黑板上写一排N<=300个数,每个数都有一个价值val。若相邻两个数不互质,就可以把它们擦去,并获得它们的价值之和(注意,操作后原先不相邻的数可能变得相邻)。问最多能获得多少价值。

题解:

DP:F[i][j][0]代表把区间i~j全部消掉,在这一区间能获得的最大价值。F[i][j][1]代表不把区间i~j全部消掉,在这一区间能获得的最大价值。

转移:

1. F[i][j][0] <- F[i+1][j-1][0]+val[i]+val[j],代表中间全部消掉以后i和j“碰头”,然后再把它们消掉。要求第i个数和第j个数不互质。
2. F[i][j][0] <- F[i][k][0]+F[k+1][j][0],代表分别把前半截和后半截消掉。
3. F[i][j][1] <- F[i][k][0]+F[k+1][j][1],代表前半截消掉,后半截不消掉。
4. F[i][j][1] <- F[i][k][1]+F[k+1][j][0],前半截不消掉,后半截消掉。
5. F[i][j][1] <- F[i][k][1]+F[k+1][j][1],前后都不消掉。

最后答案就是max(F[1][N][0], F[1][N][1]).

代码:

1010. Count Primes 

题目大意:

计算[1..n]内的素数个数,n<=1e11.

题解:

一开始没敢写……其实就是打表。首先观察到一个事实:只需要先筛出1e6以内的素数,就可以判断一个1e11以内的数是不是素数。

每隔1.2e7打表,这样表大概有60KB,正好不超过限制。注意,表里存“这一段有多少个素数”,而不是“1..i内有多少个素数”,因为后者数比较大,占空间多。然后求个前缀和。查询时,先查表,然后暴力筛剩下的部分(至多1.2e7)即可。筛法的的效率大概是每秒筛1e8个数,因此不会超时。我筛法的数组只开了1e6,但是用记录“时间戳”的方法,每次不用memset整个数组,因此筛的速度和数组大小无关。

发表评论

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