重庆市第六届程序设计大赛试题

重庆市第六届程序设计大赛试题

1. 睿睿的随机数(Rating:easy)

输入文件名“radom.in” 输出文件名“estdout.pc2”

睿睿想在学校中请一些同学一起做一项问卷调查，为了实验的客观性，他先用计算机生成了N个1到1000之间的随机整数（N≤100），对于其中重复的数字，只保留一个，把其余相同的数去掉，不同的数对应着不同的学生的学号。然后再把这些数从小到大排序，按照排好的顺序去找同学做调查。请你协助睿睿完成“去重”与“排序”的工作。

输入格式

输入文件有2行，第1行为1个正整数，表示所生成的随机数的个数：N 第2行有N个用空格隔开的正整数，为所产生的随机数。

输出格式

输出文件也是2行，第1行为1个正整数M，表示不相同的随机数的个数。第2行为M个用空格隔的正整数，为从小到大排好序的不相同的随机数。

输入样本

10

20 40 32 67 40 20 89 300 400 15

输出样本

8

15 20 32 40 67 89 300 400

2. 国家利益(Rating: medium-easy)

没有永远的朋友，也没有永远的敌人，国家的行为取决于国家利益，国家的地位取决于国家实力。伊拉克战争结束后N个国家正在联合国开会商讨如何分配伊拉克的M块油田。 N个国家按国家实力编号1，2，3...N，1号国家实力最强，第一个发言，N号最后一个发言；依次类推发言国家会提出一个分配方案，所有有表决权的国家进行表决（包括发言国家自己）；如果50%或以上同意此方案，则会议结束，按照此国的方案分配油田，否则该国丧失

表决权，下个国家重复上述过程。那么第一个国家提出怎样的方案才能使本国利益最大化？ 提示：

每个国家分得的油田都是整数，不会出现几个国家共同拥有一块油田

每个国家都不希望别人的方案通过，但是每个国家都按照本国利益投票，比如1号国家提出一个方案， X号国家分Y油田，X号国家会进行比较， 如果该方案被否决，那么下次2号提出的方案X号国家分Z油田，而Z < Y，那么X号国家会赞成1号的方案， 否则反对

输入格式

输入文件有由若干行构成，每行包括一组数据由2个整数N，M构成，（N,M <= 10^8），输入文件的最后一行是‘#’表示文件结束。

输出格式

按照输入文件的顺序对于每组输入数据输出一行，每行包括1个整数，1号国家能获得的最多油田数。

Sample Input 7 100 6 100 #

Sample Output 97 98

3．Base64 编码 (Rating: medium)

Base64编码用来将任意的八位字节序列表示成为区分大小写的让人难以理解的形式。Base64编码用到了US-ASCII中的一个有65个元素的子集，能表示出可打印字符的其中6位。（额外的第65个字符‘=’，用来做特殊处理）。

编码过程中，将一个24位的输入作为一个整体，处理成4个字符输出。编码从左向右进行，一个24位的输入是由三个连续的8位字节组成，这些24位被看成是4个连续的6位的正整数，每一个正整数都被转换成Base64字符表中的一个数字。每个6位的正整数都是64

个字符数组的地址。由此地址确定的字符将会放到输出字符串。 Table 1: Base 64 字符表

值 编码 值 编码 值 编码 值 编码 0 A 17 R 34 i 51 z 1 B 18 S 35 j 52 0 2 C 19 T 36 k 53 1 3 D 20 U 37 l 54 2 4 E 21 V 38 m 55 3 5 F 22 W 39 n 56 4 6 G 23 X 40 o 57 5 7 H 24 Y 41 p 58 6 8 I 25 Z 42 q 59 7 9 J 26 a 43 r 60 8 10 K 27 b 44 s 61 9 11 L 28 c 45 t 62 + 12 M 29 d 46 u 63 / 13 N 30 e 47 v

14 O 31 f 48 w (pad) = 15 P 32 g 49 x 16 Q 33 h 50 y

当输入数据的最后少于24bit的时候就需要特殊处理，最后总是能完全编码。当输入串最后少于24位的时候，不足的部分补0。填充的数据用 ‘=’ 来编码，由于所有的输入都是八位的字符，所以只有下列情况发生：

1、 最后剩余的bit数是24的倍数，输出的字符数目将是4的倍数，不会有 ’=’追加。 2、 最后剩余的 bit 数正好为 8 bits，此时在编码串后追加两个 ‘=’ 字符。 3、 最后剩余的 bit 数正好是 16bits，此时在编码串后追加一个 ‘=’ 字符

输入格式

第一行是一个正整数 T(1 <= T <= 100)，表示数据的组数。接着是 T行，每一行为一个待编码的字符串。

输出格式

对于每一个测试用例，输出相应的编码字符串。

输入样本

4

What is your name i you yes

输出样本

V2hhdCBpcyB5b3VyIG5hbWU= aQ== eW91 eWVz

4．同色游戏 (Rating: medium)

N个学生排成一排，每个学生都穿着某一种颜色的服装。一共有m种颜色，因此每一种颜色都可以用0到m-1之间的一个数字表示。吴老师想让他的学生都只同一种颜色的衣服，

因此他需要一些操作。我们都知道吴老师是一个非常奇怪的人，如果某个学生穿着第i种颜色的衣服而且吴老师想让这个学生换别的颜色，他在一次操作中只让这个学生换成第（i+1）%m种颜色的服装。更加奇怪的是，吴老师总是让连续的t个学生一起改变他们服装的颜色。现在问题来了，我们给你参数n,m和t（n<2000,m<150,t

输入格式

在输入的第一行是k<=30，表示有多少组测试数据。

对于每一种测试数据，有三个输入数据,n,m,t.接着是一行n个数字ai (i=1,2?n), (0<=ai<=m-1).ai 表示第i个学生衣服的颜色。

输出格式

对于每一种测试数据，你需要在一行中输出两个数据，分别是所需要的最少的操作次数和最

后学生衣服的颜色。如果有两种颜色可以通过相同的操作次数得到，你只需要输出较小数字所代表的颜色。题目保证对于所有的测试数据均可以通过某种操作使得所有的学生都穿同一种颜色的服装。

输入样本

1 7 2 3 0 0 1 0 1 0 0

输出样本

3 1

5 Is It A Tree? (Rating: medium)

A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties.

1. There is exactly one node, called the root, to which no directed edges point. 2. Every node except the root has exactly one edge pointing to it.

3. There is a unique sequence of directed edges from the root to each node.

For example, consider the illustrations below, in which nodes are represented by circles and edges are represented by lines with arrowheads. The first two of these are trees, but the last is not.

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库重庆市第六届程序设计大赛试题在线全文阅读。