7月5日测试题

Posted by Ytoworld's Blog on July 5, 2017

测试

试题名称 Barricade City Treesum
源文件 barricade.cpp/.pas/.c city.cpp/.pas/.c treesum.cpp/.pas/.c
输入文件 barricade.in city.in treesum.in
输出文件 barricade.out city.out treesum.out
时间限制 1s 1s 1s
空间限制 256MB 256MB 256MB
测评机器配置:
CPU Intel Core i7, 2.7 GHz 
内存16g

Barricade

问题描述:

帝国受到攻击并计划捍卫自己的城堡。整个国家可以看成N个城镇和M条公路,每条道路具有相同的长度,并连接两个城镇。编号为 1 的城镇就是将军所在地,编号 N 的城镇是敌人驻扎地。将军知道敌人会选择最短路径,而且收到消息说他的军队还没有准备好战斗,他需要更多的时间。因此他决定摆一些路障使他的敌人减速。现在,他问你要找到一种方法来设置这些路障,以确保敌人将遇到至少一个路障。此外,第 i 条道路上的路障需要 wi 的木材。由于缺乏资源,你需要尽可能少的使用木材。

输入格式:

在第一行中有两个整数N和M。

接下来的M行的第i行描述了用三个整数 u,v 和 w 其中 0 ≤ w ≤ 1000 表示 u 和 v 之间存在一条公路,这条路上的路障成本为w。

输出格式:

输出最少需要多少木材。

样例输入:

4 4
1 2 1
2 4 2
3 1 3
4 3 4

样例输出:

4

数据规模:

对于 30% 的数据,N≤10,M≤20
对于另外 20% 的数据,除点 1 和点 N 外,其余点的度数都为 2
对于所有数据,N≤1000,M≤10000

City

问题描述:

H省有 N 个地级市,政府为了城市开发建设,决定先修路,后造房子,以吸引外来人员。一开始每个城市中有 b[i]个住户,而在两个城市 u,v 之间建路需要的代价就是 R 乘 u,v 两个城市的住户数目之和。建路的目标是使得所有城市相互之间都可达。 建完路之后,就要造房子了,由于 H 省的房产商仅有一家,所以只能一户一户的造房子。不过政府有权利任意安排建造的顺序,在城市 i 建造一个房子的代价是,h[i]乘以城市 i 当前住户数目同城市 i 周边城市(即通过道路直接相连的)的当前住户数目之和。由于现在房子炙手可热,所以每造好一户,就立刻有用户入住。政府决定最后的目标是每个城市 a[i]个住户。作为政府部门的财务主管,请你计算出最少需要花费多少钱,才可以完成上述要求。

输入格式:

第一行一个整数 N,表示有 N 个城市;

接下来一行有 N 个整数,描述 b 数组,也就是每个城市一开始的住户数; 接下来一行有 N个整数,描述 a 数组,也就是每个城市最终的住户数;

接下来一行有 N 个整数,描述 h 数组,表示建房费用;

接下来有一个 N*N 的矩阵,第 i 行第 j 个元素表示原来 i 城市和 j 城市是否有路相连。 最后一行一个整数 R,表示建路的费用。

输出格式:

一个整数,表示最小费用。

样例输入:

4
1 1 1 1
1 3 1 2
8 5 3 2
NYNN
YNYN
NYNY
NNYN
100000

样例输出:

39

数据规模:

对于 100% 的数据,1≤N≤50,b[i]≤a[i]≤100000,h[i],R≤100000,矩阵是对称的。
数据保证有一定的梯度。

Rectangle

问题描述:

把包含 N 个元素的集合{1,2,3…N}划分成若干个非空子集的方案数被称为贝尔数,记为 Bell(N)。例如,当 N=3 时:

{1, 2, 3}
{1} {2 3}
{1, 2} {3}
{1, 3} {2}
{1} {2} {3}

有以上五种划分方案,因此 Bell(3)=5。现在有一位长者想知道如何快速地计算贝尔数。如果长者给你一个正整数 N,你能告诉其 Bell(N) mod 95041567 的值吗?

输入格式:

第一行一个正整数 T,表示数据组数。接下来 T 行,每行一个正整数 N,表示要计算 Bell(N)。

输出格式:

一共 T 行,每行一个整数,表示 Bell(N) mod 95041567 的值。

样例输入:

6
1
2
3
4
5
6

样例输出:

1
2
5
15
52 
203

数据规模:

对于 50%的数据,1<=N<=1000。
对于 100%的数据,1<=N<=2147483647,1<=T<=10。 	

你需要的公式:

贝尔数递推公式

image

Touchard 同余公式:

若 p 是任意质数,则: image