山东信息奥赛培训(7.17)

《山东信息奥赛培训(7.17)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、NOIP模拟试题题目名称城市街区因子的排列序列排序可执行文件名cityfactorssort输入文件city.infactors.insort.in输出文件city.outfactors.outsort.out每个测试点时限1s1s1s内存限制128M128M128M测试点数目101010每个测试点分值101010结果比较方式忽略多余的空格和文件尾的空行题目类型传统传统传统注意：最终测试时，所有编译命令均不打开任何优化开关。一、城市街区(city.pas/c/cpp)问题描述：小A有一个游戏，这个游戏中的某个城市的地图是一个

2、大型方格网，左下角为(-109,-109)，右上角为(109,109)。在方格网内部（包括边界）每个整点都是一个路口，每条直线x=x0或y=y0（x0,y0为整数）在方格网内部（包括边界）的部分都是该城市的一条街道。此外，该城市还存在一条斜向的街道，其直线方程为Ax+By+C=0（A,B均不等于0），这条斜向的街道与方格网的交叉点也是路口。现在有N个人，所有人都只能沿着城市的街道行走，其中第i个人要从该城市的路口(ai,bi)走到路口(ci,di)。小A希望计算每个人需要走的最短路径的长度。由于N太大了，小A不想自己算，因此

3、他向你求助。输入：第一行，四个整数N,A,B,C。接下来的N行，每行四个整数ai,bi,ci,di。输出：N行，每行一个实数（保留3位小数），其中第i行的整数表示第i个人需要走的最短路径的长度。输入输出样例：city.incity.out322-1-6224-62-3-2-62-81010.0007.0008.828数据范围：对于30%的数据，

4、A

5、,

6、B

7、,

8、C

9、,

10、ai

11、,

12、bi

13、,

14、ci

15、,

16、di

17、<=10；对于全部的数据，

18、A

19、,

20、B

21、,

22、C

23、,

24、ai

25、,

26、bi

27、,

28、ci

29、,

30、di

31、<=109，1<=N<=2000。

32、二、因子的排列(factors.pas/c/cpp)问题描述：一天，小B学习了分解质因数的相关内容。他发现，一个数的质因子可以有许多不同的排列方式，例如20=2*2*5=2*5*2=5*2*2，那么小B认为20的质因子有3种不同的排列方式。小B的同学现在有一个问题：如果一个整数的质因子的不同的排列方式的种类数为k，那么这个整数n（n>1）最小是多少？小B的同学一共有T个不同的k值，希望小B帮助这个同学解决问题。但是小B发现T太大了，并且给出的k值也相当大，因此小B向你求助。输入：第一行，一个整数T。接下来的T行，每行一个整数

33、k。输出：T行，每行一个整数，其中第i行的整数表示第i个k值对应的n的值。输入输出样例：factors.infactors.out41231052612720数据范围：对于30%的数据，1

34、行，N个整数，表示小C的序列。输出：一行，一个整数，表示小C需要的最小代价。输入输出样例：sort.insort.out684532734数据范围：对于30%的数据，1<=N<=10；对于全部的数据，1<=N<=100000，输入数据中的其他整数均为正整数且不超过109。