网上找的一些试题省选problemset

1、PAGE PAGE 8组队选拔赛共有五道题，完成时间共3小时。每题有十组测试数据，每组10分，每题100分，共500分。= 运 动 会 题目描述：运动会.doc 输入数据：sports1.in sports10.in 输出数据：sports1.out- sports10.out 数字游戏 题目描述：数字游戏.doc 输入数据：Game1.in Game10.in 输出数据：Game1.out Game10.out 双调路径 题目描述：双调路径.doc 输入数据：bic1.in - bic10.in输出数据：bic1.out- bic10.out 数 列 题目描述：数列.doc 输入数据：seq

2、1.in - seq10.in 输出数据：seq1.out - seq10.out 群的计数 题目描述：群的计数.doc 输入数据：group1.in - group10.in 输出数据：group1.out - group10.out 运动会sports.pas/c/cpp 时间限制：1S 100分 【问题描述 】 某届运动会共有n个项目，编号为1，2，.，n（1=n=100）。项目无先后顺序关系，共有k个人参赛，（1=k=参加人数，即跑一次，就可决出名次。问题要求给出一种安排，用最少时间（天数）完成比赛，并保证所有人都能完成参赛项目。n =4，k=4参赛情况 第1人 参加 1，2项目 第2

3、人 参加 1，3项目 第3人 参加 2项目 第4人 参加 4项目安排 第一天 1，4 项目（不唯一） 第二天 2，3 项目共2天，完成比赛n =4，k=2参赛情况 第1人 参加 1，2项目 第2人 参加 3，4项目安排 第一天 1，3 项目（不唯一） 第二天 2，4 项目【输入文件 】 第一行2个整数n ，k（数字间一个空格）以下共有k行，每行表示每人的参赛项目，项目号用一个整数表示，两数之间用一个空格隔开，每行均以0结束【输出文件 】一个整数，即天数【样 例 】 sports.in4 2 1 2 0 3 4 0sports.out2 数字游戏Game.pas/c/cpp 时间限制：1S 10

4、0分【问题描述 】考虑下面一个两个人玩的游戏：在一个游戏板上有N个正整数（2 = N = 100）排成一列。玩家1先玩。两个玩家交替从这列数的两端取数。取得的数值加入玩家的总分中，取完数后，如果玩家的分数大于他的对手的分数，他就赢了。问题写一个程序执行最优策略。最优策略是指的是与“最好的情况”对抗，你的程序认为对手也是用最优策略的。【输入文件 】：第一行是一个正整数N，是游戏板上正整数的数量；第二行到第N+1行，依次是游戏板上从左到右的N个数。【输出文件 】：输出文件只有一行，两个数，分别是玩家1和玩家2的分数，用一个空格隔开。【样 例 】game.in6472952game.out11 双调

5、路径 bic.pas/c/cpp时间限制： 3S 100分 【问题描述 】如今的道路收费发展很快。道路的密度越来越大，因此选择最佳路径是很现实的问题。城市的道路是双向的。每条道路有固定的旅行时间以及需要支付的费用。路径是连续经过的道路组成的。总时间是各条道路旅行时间的和，总费用是各条道路所支付费用的总和。一条路径越快，或者费用越低，该路径就越好。严格地说，如果一条路径比别的路径更快，而且不需要支付更多费用，它就比较好。反过来也如此理解。如果没有一条路径比某路径更好，则该路径被称为最小路径。这样的最小的路径有可能不止一条，或者根本不存在路径。例子下图给出了一个网络，每条路有两个参数：费用和时间。

6、从1到4有4条路径。124(fee4, time5), 134(fee4, time5), 1234(fee6, time4)，1324(fee4, time10)。134和 124比 1324更好。有两种最佳路径：fee4, time5 (roots 124 and 134) 和 fee6, time4 (root 1234)。问题：从文件bic.in中读入网络，计算最小路径的总数。费用时间都相同的两条最小路径只算作一条。你只要输出不同种类的最小路径数即可。【输入文件 】：文件的第一行有4个整数，城市总数n, 1n100, 道路总数 m, 0m300, 起点和终点城市s，e, 1s,en,

7、se。接下来的m行每行描述了一条道路的信息，包括4个整数，两个端点p，r，费用c，以及时间t，1p,rn, pr, 0c100, 0t100。两个城市之间可能有多条路径连接。【输出文件 】：仅一个数，表示最小路径的总数。【样 例 】Bic.inbic.outComments4 5 1 42 1 2 13 4 3 12 3 1 23 1 1 42 4 2 42该例对应前面的图。数 列 seq.pas/c/cpp 时间限制：10 S 100分 【问题描述 】 有这样一种数列A1、A2、A3、An，其中A1=0，且对任意一项Ai满足|Ai-Ai+1|=1（1=in）。设S=A1+A2+A3+An，表

8、示前n项之和。问题：现在给出数列长度n与数列前n项之和S，要求：输出满足条件的数列的总数。输出满足条件的100个数列（如果不满100个就全部输出）。【输入文件 】： 一行，包含两个整数n和S（1=n=100），用1个空格隔开。【输出文件 】 第1行一个整数t（0=t=263-1），表示满足条件的数列总数。接下来每行输出一个数列，数列各项之间用一个空格隔开。若满足条件的数列数目不满100个，全部输出即可。【样 例 】seq.in4 0seq.out20 -1 0 10 1 0 -1群的计数 group.pas/c/cpp 时间限制： 2S 100分【问题描述 】代数学研究的基本对象之一群是一些元

9、素的集合。这些元素之间有一种代数运算，称之为乘法。两个群元素的乘积是一个群元素。一个大家习以为常的群是有理数乘法群，例如，等等，都是这个群中乘法的例子。需要注意的是，如果了此们仅仅考虑有理数的乘法群，另外的一些运算比如加法是不被讨论的。数学家们把乘法抽象出来，就成为了群。群需要满足以下三条性质：结合律：对群中的任意元素a,b,c 有 a(bc)=(ab)c单位元：在群中存在唯一的元素e，它对群中任意的元素a有ea=a，ae=a有理数乘法群的单位元是1逆 元： 对群中任意元素a,都存在群中唯一的元素b,使得ab=ba=e比如有理数乘法群中，23的逆元就为。从这里可以看出，整数乘法不能构成一个群。

10、需要注意的是，群的定义中并没有交换律，就是说ab不一定等于ba，有理数乘法群作为一个特例，其交换性是没有普遍的意义的。问题：现在的问题是，给定群的元素的个数（群的阶数），需要知道这样的群有多少种。只要满足上述三条性质，就是群，应该算上。 下面用四阶群的例子来说明这个问题。抽象地记群元素为e,a,b,c 只要列出一个乘法表，就可以代表一个群。下面给出推导乘法表的步骤：群1EABcEe (1)a (1)b (1)c (1)Aa (1)e (2)c (3)b (3)Bb (1)c (3)e (4)A (5)Cc (1)b (3)a (5)e (5)有单位元素的性质，可以填上：a*a可能为e,b,c，

11、但不可能为a,否则a*a=a两边乘以a的逆元，得到a=e；a*a=b和a*a=c的情况是一样的，只是乘法表中元素的位置进行了一个变换，本质没有改变，称为一个群同构；此时可以把a*a得到的元素称为b；所以只要讨论a*a=e和a*a=b的情况；下面先讨论a*a=e的情况a*b不能为a或e，a*b为b的话，a=e，也矛盾，所以a*b=c；同理可填上所有的(3)b*b=e时，b*c=c*b=a，c*c=e，得到群1b*b=a时，b*c=c*b=e，c*c=a，得到群2群2EAbcEe (1)a (1)b (1)c (1)Aa (1)e (2)c (3)b (3)Bb (1)c (3)a (4)e (5)Cc (1)b (3)e (5)a (5)当a*a=b时，按照标号顺序可填出下列的群：群 2EAbcEe (1)a (1)b (1)c (1)Aa (1)b (2)c (4)e (3)Bb (1)c (4)e (6)a (5)Cc (