SRM584

又是一个悲情的夜晚,常时间不做题果然很挫,言归正传

250pt:

描述:给定一个N个节点的连通的无向图,每个节点有一个值val,两个节点之间有边当且仅当,两个节点的val的差的绝对值不大于d

求:这张图的任意两个节点的val的差值最大是多少?

思路:画几张示例图后发现,两个节点最大的差值与两点之间的经过的边数有关,仔细再一想,这个边数就是最短路。直接对图的边赋值为d,floyd求任意两个节点的最短路,最短路中最大值即为结果

注意:由于节点和自己是不能连通的,所以要么建图的时候赋值为0,要么在判断结果的时候不能算节点对自己的边(我就是大意了这里,最后1分钟的时候,想到了,懒得改。。。。。)

500pt:

描述:古文明有N个建筑,没落之后被埋地下,不同建筑埋的深度不一样,不同建筑的种类不同。现在考古学家知道建筑的位置,使用某种设备挖掘了K个建筑点,深度为D,现在知道挖出来的建筑(深度大于D的挖不出来)的种类(重复不计)。

求:给定N个建筑的深度depth和种类kind,以及挖掘的建筑点数K和挖掘出的种类found,求K个建筑的组合情况。

示例:

建筑点 种类 深度
1 1 10
2 1 15
3 2 10
4 2 20

K为2,挖掘出的建筑种类为{1}

答案为3  即

{1 ,2} 挖掘深度D [10, ∞)

{1 ,4} 挖掘深度D [10, 20)

{2 ,4} 挖掘深度D [15, 20)

共三种情况

分析:N最大为50,直接C(N,K)显然是不可能的。因为一定要挖出found集合中所有的种类(即挖出该种类的建筑数至少一个),如果深度<=D的建筑中已经包含了found的所有种类,那么这样的D是可能的。于是考虑把建筑按照深度从小到大排序,从深度<=D中每个found的种类至少选一个,共选出x个,从深度>D中,选出K-x个,这样算出的就是结果

难点:考虑示例当D为[10,15)时,合法的组合为{1,2},{1,4}

当D为[15,20)时,合法的组合为{2,1},{2,4}

我们发现了{1,2}这个组合的重复,如何去重才是这个题目最难的部分。

当D=10,我们首先选择1,我们只需要从{2,3,4}中任意选择1个,使之满足给定条件的就是{2,4}

当D=15,我们这个时候要选出之前没有出现过的组合,那什么样的才是没有重复的呢?我们发现之前选出的组合,任意一个包含在found种类的点中,肯定会存在depth[i]<D 且Kind[i]属于found的建筑点,所以我们只要对(至少)一个包含在found的种类,不选depth[i]<D的点即可。

那怎么实现呢?研究了NaHs的代码,看了好久才明白了= =

对于指定的D,定义数组dp[N][K][2],

dp[i][j][0]表示前i种建筑选出j个建筑点,且前i种建筑中肯定都包含<D的建筑的方法数。

dp[i][j][1]表示前i种建筑选出j个建筑点,且前i种建筑中至少有一个不包含<D的建筑的方法数。

很显然,对于指定的D,第i种建筑<D的有x个,=D的有y个

那么dp[i][j][0]= ∑dp[i-1][k][0]*(C(x+y,j-k)-C(y,j-k))   k∈[i-1,j-1]

dp[i][j][1]= ∑dp[i-1][k][0]*C(y,j-k)+ ∑dp[i-1][k][1]*C(x+y,j-k)   k∈[i-1,j-1]

具体代码实现参见:http://community.topcoder.com/stat?c=problem_solution&rm=317926&rd=15696&pm=12641&cr=22658074

1000pt:54了

后记:第一次负分,分数狂降190+,1198,下次就div2了。也算是一个新的开始,加油。

文章分类 SRM

发表评论

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

*

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>