OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【HAOI2010】软件安装

【题目描述】

现在我们的手头有N个软件,对于一个软件i,它要占用Wi的磁盘空间,它的价值为Vi。我们希望从中选择一些软件安装到一台磁盘容量为M计算机上,使得这些软件的价值尽可能大(即Vi的和最大)。

但是现在有个问题:软件之间存在依赖关系,即软件i只有在安装了软件j(包括软件j的直接或间接依赖)的情况下才能正确工作(软件i依赖软件j)。幸运的是,一个软件最多依赖另外一个软件。如果一个软件不能正常工作,那么它能够发挥的作用为0。

我们现在知道了软件之间的依赖关系:软件i依赖软件Di。现在请你设计出一种方案,安装价值尽量大的软件。一个软件只能被安装一次,如果一个软件没有依赖则Di=0,这时只...

【JSOI2007】合金

【题目描述】

某公司加工一种由铁、铝、锡组成的合金。他们的工作很简单。首先进口一些铁铝锡合金原材料,不同种类的原材料中铁铝锡的比重不同。然后,将每种原材料取出一定量,经过融解、混合,得到新的合金。新的合金的铁铝锡比重为用户所需要的比重。

现在,用户给出了n种他们需要的合金,以及每种合金中铁铝锡的比重。公司希望能够订购最少种类的原材料,并且使用这些原材料可以加工出用户需要的所有种类的合金。

【输入】

第一行两个整数m和n(m,n≤500),分别表示原材料种数和用户需要的合金种数。

第2到m+1行,每行三个实数a,b,c(a,b,c≥0且a+b+c=1),分别表示铁铝锡在一种原材料中所占...

【HAOI2005】希望小学

【题目描述】

地处偏僻山区的X乡有N个自然村,目前还没有一所小学,孩子们要么不上学,要么需要翻过一座大山到别处上学。如今好啦,有一位热心人士准备捐款在某个自然村建立一所希望小学。

通过调查发现,X乡各个村庄之间的道路较为复杂,有平路、上坡和下坡。考虑到每个村孩子们的人数不同,走上坡、下坡和平路的速度也不同,男孩和女孩走路速度也不同,请你为X乡选择一个最合适建立希望小学的村庄,使得所有的孩子花在路上的总时间最少。

【输入】

第1行: N B1 B2 B3 G1 G2 G3 (村庄数、男孩分别走平路、上坡、下坡每千米花费的时间以及女孩分别走平路、上坡、下坡每千米花费的时间)

第2行: Xl...

【LNOI2013】最小距离之和

【题目描述】

DQ星球的世界末日就要到了,可是诺亚方舟还没有制造完成。为了制造诺亚方舟这个星球上的所有国家都站在统一战线。现在一共有n个国家,一个国家到另一个国家都有一条且仅有一条通信渠道,且这个渠道有一个距离,这样就形成了一个有向完全图。 世界末日的预兆已经来了,世界上很多东西都在遭到不明原因的破坏,包括这些通信渠道。现在为了联合制造出诺亚方舟,需要统计所有国家对(a到b和b到a是不同的)之间通信最短距离之和。即需要求出表示i国家与j国家之间的最小距离。可是每隔一段时间就有一些渠道会被破坏,现在DQ星球的首领急需要你来解决这个问题。

【输入】

对于每组数据,第一行是一个n,表...

【NOI2007】社交网络

【题目描述】

在社交网络(social network)的研究中,我们常常使用图论概念去解释一些 社会现象。 不妨看这样的一个问题。在一个社交圈子里有 n 个人,人与人之间有不同程 度的关系。我们将这个关系网络对应到一个 n 个结点的无向图上,两个不同的人 若互相认识,则在他们对应的结点之间连接一条无向边,并附上一个正数权值 c, c 越小,表示两个人之间的关系越密切。 我们可以用对应结点之间的最短路长度来衡量两个人 s 和 t 之间的关系密切 程度,注意到最短路径上的其他结点为 s 和 t 的联系提供了某种便利,即这些结 ...

© OI技术宅 | Powered by LOFTER