（前四届）湖南省大学生程序设计大赛题

1

湖南省首届“湘邮科技杯”大学生程序设计大赛试题

试题 1 n 个人围成一圈, 并依次编号 1～n，。从编号为 1 的人开始，按顺时针方向每隔一人选出一个，

剩下的人重新围成一圈，如此循环直到剩下两人，这剩下的两人就是幸运儿。如果你想成为最后两个

幸运儿，请问开始时应该站在什么位置？（设 3<=n<=50）

输入：开始时的人数 n

输入：

12

应该的输出：

2 4 6 8 10 12 3 7 11 5

1 9

寻找的字符串，每个字符串不会超过 20 个字符。

输出：n 行，每行保存 1 个字符串的位置。位置的格式形如(1,2)->(2,6)，意为该字符串首字母在字符矩

阵中的位置是第 1 列 2 行，尾字母在字符矩阵中的位置是第 2 列 6 行。

备注：如果某个字符串在字符阵列中出现多次，则只记录任意一个出现位置即可。字符串出现的形式

可能是水平、竖直、向前、向后和斜向。输出的位置顺序应该与输入中的字符串出现顺序一致。

区分字符的大小写。

2

示例

试题 3 给出一个正方形图案和它的变换图案，称为图案变换对。编写程序，求图案变换对之间的最小

变换。图案是由黑白两种小方块构成的。可能的变换包括：

输入：输入文件中包含多组图案变换对。每一对图案数据的起始行都是一个整数，表示正方形图案的

边长 a（以一个小方块为单位，1<=a<=100），后续的 a 行，每一行包含了原图案的一行和变换图案的

对应行，两者之间用一个空格分开。黑色小方块用 b 表示，白色小方块用 o 表示。

输出：输出文件的每一行对应输入文件的每一个图案变换对。其中每行开始的整数表示对应图案对在

输入文件中出现的序号，紧跟一个空格，然后就是该图案对的最小变换，采用上述记号表示。

备注：为了比较不同变换的大小，定义：旋转变换的代价小于映像变换，小角度旋转变换的代价小于

大角度旋转变换，保持变换的代价最小。注意：对本题而言，只有上面列出的变换是合法的，如果某

个图案对可以由多个变换得到，则应选择代价最小的变换。

3

示例

输入：

oooob bboob

6

oooobb boooob

oooboo bobooo

bboobo oboobo

2

5

boooo obooo

obooo ooboo

obooo ooboo

ooobo oooob

oooob boooo

4

oboo oobo

4

试题 4 在计算机辅助设计(CAD)中，有一个经典问题：消除隐藏线（被其它图形遮住的线段）。你需要

设计一个软件，帮助建筑师绘制城市的侧视轮廓图。为了方便处理，限定所有的建筑物都是矩形的，

下面左图中的建筑物分别用如下三元组表示：

(1,11,5),(2,6,7),(3,13,9),(12,7,16),(14,3,25),(19,18,22),(23,13,29),(24,4,28)

输入：输入文件中包含一系列的建筑物三元组。建筑物的坐标都是正整数且不大于 1000。建筑物的数

目不会超过 50。每行只有一个三元组。三元组的每个元素之间用一个空格分开。三元组按照 Li 排序，

即左边缘坐标最小的建筑物三元组会出现在输入文件的第一行。

输出：输出文件中包含一行描述轮廓线的数值序列，其中偶元素代表轮廓线的延伸高度，奇元素代表

轮廓线顶点的水平坐标，如上面的图例所示。

示例

输入：

23 13 29

24 4 28

输出：

1 11 3 13 9 0 12 7 16 3 19 18 22 3 23 13 29 0

5

试题 5 也许是因为有 10 个手指的原因，所以我们把 0～9 十个数字组合起来表达任意的数值，但这

并不是唯一可能的记数法。在某个外星球居住着一种智慧生物，他们的手跟我们的手构造不同，他们

他们的数值系统中，每个数位是右边相邻数位的 3 倍。因此数’10-’表示数值 8（因为 8＝1×9＋0×3

＋－1×1），数’-1’表示数值-2（因为-2= -1×3＋1×1）。