湖南大学计算机与通信学院2007年保研能力测试(机试题目+部分解题报告)

stephenmjm

Problem牋牋AC/Submit牋牋Title
A牋牋牋牋牋牋牋牋 195/203牋牋IP Address
B牋牋牋牋牋牋牋牋牋 10/16牋牋Check a Sudoku
C牋牋牋牋牋牋牋牋牋 5/12牋牋 Don't ask woman about her age
D牋牋牋牋牋牋牋牋牋 2/5牋牋 RSA Attack
E牋牋牋牋牋牋牋牋牋 6/7牋牋 网络传输牋牋（代码见23楼）
F牋牋牋牋牋牋牋牋牋 11/19牋牋合并果子
G牋牋牋牋牋牋牋牋牋 5/6牋牋CRC校验
H牋牋牋牋牋牋牋牋牋 2/6牋牋“快乐男生”演唱会
I牋牋牋牋牋牋牋牋牋 2/3牋牋二叉树遍历
J牋牋牋牋牋牋牋牋牋 2/5牋牋反正切函数的应用

11楼~14楼有部分代码＆解题报告

stephenmjm

IP Address
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 203, Accepted users: 195
Problem 10025 : No special judgement
Problem description
Suppose you are reading byte streams from any device, representing IP addresses. Your task is to convert a 32 characters long sequence of '1s' and '0s' (bits) to a dotted decimal format. A dotted decimal format for an IP address is form by grouping 8 bits at a time and converting the binary representation to decimal representation. Any 8 bits is a valid part of an IP address. To convert binary numbers to decimal numbers remember that both are positional numerical systems, where the first 8 positions of the binary systems are:

27 26 25 24 23 22 21 20 128 64 32 16 8 4 2 1


Input
The input will have a number N (1<=N<=9) in its first line representing the number of streams to convert. N lines will follow.


Output
The output must have N lines with a doted decimal IP address. A dotted decimal IP address is formed by grouping 8 bit at the time and converting the binary representation to decimal representation.


Sample Input
4
00000000000000000000000000000000
00000011100000001111111111111111
11001011100001001110010110000000
01010000000100000000000000000001

Sample Output
0.0.0.0
3.128.255.255
203.132.229.128
80.16.0.1

Problem Source
MCA 2004

stephenmjm

Check a Sudoku
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB
Total submit users: 16, Accepted users: 10
Problem 10140 : No special judgement
Problem description

Sudoku is a puzzle of a 9

stephenmjm

Don&#39;t ask woman about her age
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 12, Accepted users: 5
Problem 10160 : No special judgement
Problem description
Mrs Little likes digits most of all. Every year she tries to make the best number of the year. She tryes to become more and more intelligent and every year studies a new digit. And the number she makes is written in numeric system which base equals to her age. To make her life more beautiful she writes only numbers that are divisible by her age minus one. Mrs Little wants to hold her age in secret.

You are given a number consisting of digits 0, …, 9 and latin letters A, …, Z, where A equals 10, B equals 11 etc. Your task is to find the minimal number k satisfying the following condition: the given number, written in k-based system is divisible by k&#8722;1.


Input
Input consists of one string containing no more than 106 digits or uppercase latin letters.


Output
Output file should contain the only number k, or "No solution." if for all 2 ≤ k ≤ 36 condition written above can&#39;t be satisfyed. By the way, you should write your answer in decimal system.


Sample Input
A1A

Sample Output
22

Problem Source
Tetrahedron Team Contest May 2001

stephenmjm

RSA Attack
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 5, Accepted users: 2
Problem 10161 : No special judgement
Problem description
Thre RSA problem is the following: given a positive integer n that is a product of two distinct odd primes p and q, a positive integer e such that gcd(e, (p-1)*(q-1)) = 1, and an integer c, find an integer m such that me = c (mod n) .



Input
One number K (K ≤ 2000) in the first line is an amount of tests. Each next line represents separate test, which contains three positive integer numbers ?C e, n and c (e, n, c ≤ 32000, n = p * q, which p, q are distinct odd primes, gcd(e, (p-1)*(q-1)) = 1, e < (p - 1) * (q - 1) ).



Output
For each input test the program must find the encrypted integer m.



Sample Input
3
9 187 129
11 221 56
7 391 204



Sample Output
7
23
17



Problem Source
Michael Medvedev

stephenmjm

网络传输
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 7, Accepted users: 6
Problem 10162 : No special judgement
Problem description
为了防止数据包在一个网络里面不停的绕圈传输，每一个数据包都有一个TTL(Time To Live)域。这个域表示可以传输这个数据包的结点数。每个结点收到数据包后，先判断数据包的目标结点是不是自己。如果是的，那么就接受这个数据包，不再转发；否则的话，将TTL的值减少1，如果这时TTL不等于0，那么就转发这个数据包。

在这个问题里，会给你一个网络的描述，再给你数据包的发送结点和初始TTL值，你要输出这个数据包不能到达的结点数。看下面的示例，这个图表示一个网络:



数字表示结点的编号，直线表示两个结点之间直接相连。如果初始TTL是2，发送数据包的结点是35，那么这个数据包可以到达15，10，20，40，55，50，60号结点，不能到达的结点数是5个。如果初始TTL改为3，那么只有45号结点不能到达。


Input
第一行是一个整数NC，表示网络的连接数。接下来有NC对正整数，表示这两个编号的结点之间直接相连。网络的结点总数不超过30。整个网络是连通的，两个结点之间至多只有一条直接联结的线路。

接下来是若干个问题，每个问题用2个数表示，第一个表示发送数据包的节点编号，第二个数表示初始TTL值。问题以两个0结束。



Output
对每个问题输出一行，每行一个数字，表示不能到达的节点数。


Sample Input
16
10 15
15 20
20 25
10 30
30 47
47 50
25 45
45 65
15 35
35 55
20 40
50 55
35 40
55 60
40 60
60 65
35 2
35 3
0 0

Sample Output
5
1


Problem Source
HNU Contest

stephenmjm

合并果子
Time Limit: 2000ms, Special Time Limit:5000ms, Memory Limit:32768KB
Total submit users: 19, Accepted users: 11
Problem 10163 : No special judgement
Problem description
在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过n-1次合并之后，就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有3种果子，数目依次为1，2，9。可以先将 1、2堆合并，新堆数目为3，耗费体力为3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为12，耗费体力为 12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。


Input
输入包括两行，第一行是一个整数n（1 <= n <= 10000），表示果子的种类数。第二行包含n个整数，用空格分隔，第i个整数ai（1 <= ai <= 20000）是第i种果子的数目。


Output
输出包括一行，这一行只包含一个整数，也就是最小的体力耗费值。输入数据保证这个值小于2的31次方。


Sample Input
3
1 2 9

Sample Output
15

Problem Source
NOI

stephenmjm

CRC校验
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 6, Accepted users: 5
Problem 10164 : No special judgement
Problem description
当我们给大洋彼岸的朋友发出一封email或给家乡的亲人发送一条手机短信时，我们一般不会担心对方收到错误的信息。然而，无论email还是手机短信在抵达目的地前都必需化为电信号穿越无数的电缆和设备，甚至化作无形的电磁波在天空中传播，衰减和噪音时刻都威胁着你发出的信息。为了保证通信的正确性，必需及时发现传输错误并予以纠正，这是现代通信技术中的重要研究内容。一般的解决思路是在原始信息的后面附加一些校验信息，通过这些校验信息来判断传输的正确性。循环冗余码CRC就是这样一种信息校验方法。它的思路是：
待传输的信息是由字节序列组成的，可以看作是一个很长的正二进制数B。当传输B时，在其后附上两个字节的CRC校验值组成B’。CRC校验值不是任意取的，它要使B’能被一个16位的预定义值g整除。信息的接收方也知道g，因此对方只需把接收值除以g看余数是否为零就能判断传输的正确性。在本题中我们设定g = 34943（十进制）。你的任务是编写程序计算任意输入信息对应的CRC校验值。




Input
输入文件中每一行的内容（不包括换行符）就代表一条待传输的信息。每一条待传输信息包含不多于1024个ASCII字符。首字符为“#”的行代表输入的结束。




Output
输出文件的每一行包含两个16进制数（以空格分隔）代表输入文件中对应行中待传输信息的两字节CRC校验值。每个校验值应该在十进制数的0 到34942 之间。




Sample Input
this is a test

A
#


Sample Output
77 FD
00 00
0C 86


Problem Source
湖南省第二届程序设计大赛

stephenmjm

“快乐男生”演唱会
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 6, Accepted users: 2
Problem 10165 : No special judgement
Problem description
“快乐男生”要开演唱会了！听到这个消息，有2n个歌迷排成一行进入影视中心。
演唱会的门票是50元1张。2n个人中n个人带着50元钞票，另外n个人只带着100元钞票。而售票处最初没有任何钞票。
为了加快售票速度，需要先排好队，使得每个用100元买票的人，售票处都有50元钞票找零。
如果我们把所有的人看成两种：带100元的和带50元的，那么有多少种不同的排队的方法呢？


Input
每个测试数据占据一行，只有一个正整数n。(0 < n ≤ 100)
n=-1表示测试数据的结束，并且无需处理。


Output
对于每个测试数据，输出一行，包含一个整数，表示对应的排队方式的数目。


Sample Input
2
3
-1


Sample Output
2
5

Judge Tips
假设带50元的用A表示，带100元的用B表示。
则对于第一个测试数据，满足要求的队列有AABB ,ABAB;
对于第二个测试数据，满足要求的队列有AAABBB ,AABABB,AABBAB,ABAABB,ABABAB;


Problem Source
HNU Contest

stephenmjm

二叉树遍历
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 3, Accepted users: 2
Problem 10166 : No special judgement
Problem description
遍历一棵二叉树就是按某种次序系统地“访问”二叉树上的所有结点，并使每一个结点恰好被访问一次。所谓“访问”一个结点，是指对该结点的数据域进行某种处理，处理的内容依具体问题而定，通常比较简单。我们知道，遍历一个线性结构很容易，只须从开始结点出发顺序扫描每个结点即可。但是二叉树是一个非线性结构，每个结点可以有两个后继结点，因此需要寻找一种规律来系统地访问树中各结点。遍历运算的关键在于访问结点的“次序”，这种次序应保证二叉树上的每个结点均被访问一次且仅一次。
　　 由定义可知，一棵二叉树由三部分组成：根、左子树和右子树。因此对于二叉树的遍历也可相应地分解成三项“子任务”：
　　 ①访问根结点;
　　 ②遍历左子树(即依次访问左子树上的全部结点);
　　 ③遍历右子树(即依次访问右子树上的全部结点)。
　　 因为左、右子树都是二叉树（可以是空二叉树），对它们的遍历可以按上述方法继续分解，直到每棵子树均为空二叉树为止。由此可见，上述三项子任务的次序决定了遍历的次序。若以D、L、R分别表示这三项子任务，则共有6种可能的次序：DLR、LDR、LRD、DRL、RDL和RLD。通常限定“先左后右”，即子任务②在子任务③之前完成,这样就只剩下前三种次序,按这三种进行的遍历分别称为先根遍历(或前序遍历)、中根（或中序）遍历、后根（或后序）遍历。三种遍历方法的定义如下。
　　 先根遍历 若需遍历的二叉树为空，执行空操作；否则，依次执行下列操作：
　　 ①访问根结点;
　　 ②先根遍历左子树;
　　 ③先根遍历右子树。
　　 中根遍历 若需遍历的二叉树为空,执行空操作；否则，依次执行下列操作：
　　 ①中根遍历左子树；
　　 ②访问根结点；
　　 ③中根遍历右子树。
　　 后根遍历 若需遍历的二叉树为空，执行空操作；否则，依次执行下列操作：
　　 ①后根遍历左子树；
　　 ②后根遍历右子树;
　　 ③访问根结点。
　　 显然，上述三种遍历方法的区别在于执行子任务“访问根结点”的“时机”不同；若最先（最后、在中间）执行此子任务，则为先根（后根、中根）遍历。
　　 按某种遍历方法遍历一棵二叉树，将得到该二叉树上所有结点的访问序列。


Input
输入的第一行包含单独的一个数字T，表示测试序列的数目；
　　以下T个部分，每个部分一个测试序列；
　　每个测试序列的第一行包含一个整数N（0 < N ≤ 1000），表示二叉树的节点数；
　　接下来N行，每行按照这样如下的格式依次描述每个节点：
　　字符数据 左孩子序号 右孩子序号
　　其中节点的字符数据是一个单字符,如果左/右孩子不存在，用0表示其序号。


Output
对应每个测试序列，输出以下四行：
　　Case #:  &#39;#&#39;是从一开始的测试序列号；
　　先序遍历的结果
　　中序遍历的结果
　　后序遍历的结果


Sample Input
2
8
* 2 3
+ 4 5
- 0 6
x 0 0
y 0 0
/ 7 8
a 0 0
2 0 0
3
+ 2 3
2 0 0
3 0 0

Sample Output
Case 1:
*+xy-/a2
x+y*-a/2
xy+a2/-*
Case 2:
+23
2+3
23+

Judge Tips

　　测试序列1对应的二叉树如图：




Problem Source
HNU Contest

stephenmjm

反正切函数的应用
Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:32768KB
Total submit users: 5, Accepted users: 2
Problem 10167 : No special judgement
Problem description

(其中0 ≤ x ≤ 1) 公式(1)

使用反正切函数计算PI是一种常用的方法。例如，最简单的计算PI的方法：

PI=4arctan(1)=4(1-1/3+1/5-1/7+1/9-1/11+...) 公式(2)

然而，这种方法的效率很低，但我们可以根据角度和的正切函数公式：

tan(a+b)=[tan(a)+tan(b)]/[1-tan(a)*tan(b)] 公式(3)

通过简单的变换得到：

arctan(p)+arctan(q)=arctan[(p+q)/(1-pq)] 公式(4)

利用这个公式，令p=1/2,q=1/3，则(p+q)/(1-pq)=1，有

arctan(1/2)+arctan(1/3)=arctan[(1/2+1/3)/(1-1/2*1/3)]=arctan(1)

使用1/2和1/3的反正切来计算arctan(1)，速度就快多了。
我们将公式(4)写成如下形式

arctan(1/a)=arctan(1/b)+arctan(1/c)

其中a,b和c均为正整数。

我们的问题是：对于每一个给定的a（1 ≤ a ≤ 60000），求b＋c的值。我们保证对于任意的a都存在整数解。如果有多个解，要求你给出b+c最小的解。



Input
输入文件中只有一个正整数a，其中 1 ≤ a ≤ 60000。


Output
输出文件中只有一个整数，为 b+c 的值。


Sample Input
1

Sample Output
5

Problem Source
NOI 2001

stephenmjm

论坛的建设需要大家的共同努力
有料的多发主帖
暂时学习中的多回帖支持发帖人
谢谢合作！ [s:241]