浙江大学机试真题

1、2011年浙江大学计算机及软件工程研究生机试真题1001: A+B for Matrices 题目描述 This time, you are supposed to find A+B where A and B are two matrices, and then count the number of zero rows and columns.输入 The input consists of several test cases, each starts with a pair of positive integers M and N (10) which are the number o

2、f rows and columns of the matrices, respectively. Then 2*M lines follow, each contains N integers in -100, 100, separated by a space. The first M lines correspond to the elements of A and the second M lines to that of B. The input is terminated by a zero M and that case must NOT be processed.输出 For

3、each test case you should output in one line the total number of zero rows and columns of A+B.样例输入2 21 11 1-1 -110 92 31 2 34 5 6-1 -2 -3-4 -5 -60样例输出152011年浙江大学计算机及软件工程研究生机试真题 1002: Grading题目描述 Grading hundreds of thousands of Graduate Entrance Exams is a hard work. It is even harder to design a pr

4、ocess to make the results as fair as possible. One way is to assign each exam problem to 3 independent experts. If they do not agree to each other, a judge is invited to make the final decision. Now you are asked to write a program to help this process. For each problem, there is a full-mark P and a

5、 tolerance T(P) given. The grading rules are: A problem will first be assigned to 2 experts, to obtain G1 and G2. If the difference is within the tolerance, that is, if |G1 - G2| T, this problems grade will be the average of G1 and G2. If the difference exceeds T, the 3rd expert will give G3. If G3

6、is within the tolerance with either G1 or G2, but NOT both, then this problems grade will be the average of G3 and the closest grade. If G3 is within the tolerance with both G1 and G2, then this problems grade will be the maximum of the three grades. If G3 is within the tolerance with neither G1 nor

7、 G2, a judge will give the final grade GJ.输入 Each input file may contain more thanone test case. Each case occupies a line containing six positive integers: P, T, G1, G2, G3, and GJ, as described in the problem. It is guaranteed that all the grades are valid, that is, in the interval 0, P.输出 For eac

8、h test case you should output the final grade of the problem in a line. The answer must be accurate to 1 decimal place.样例输入20 2 15 13 10 18样例输出14.02010年浙江大学计算机及软件工程研究生机试真题 1003: A+B题目描述给定两个整数A和B，其表示形式是：从个位开始，每三位数用逗号,隔开。现在请计算A+B的结果，并以正常形式输出。输入输入包含多组数据数据，每组数据占一行，由两个整数A和B组成（-109 A,B 109）。输出请计算A+B的结果，并以

9、正常形式输出，每组数据占一行。样例输入-234,567,890 123,456,7891,234 2,345,678样例输出-11111110123469122011年浙江大学计算机及软件工程研究生机试真题 1004: Median题目描述 Given an increasing sequence S of N integers, the median is the number at the middle position. For example, the median of S1=11, 12, 13, 14 is 12, and the median of S2=9, 10, 15,

10、16, 17 is 15. The median of two sequences is defined to be the median of the non-decreasing sequence which contains all the elements of both sequences. For example, the median of S1 and S2 is 13. Given two increasing sequences of integers, you are asked to find their median.输入 Each input file maycon

11、tain more thanone test case. Each case occupies 2 lines, each gives the information of a sequence. For each sequence, the first positive integer N (1000000) is the size of that sequence. Then N integers follow, separated by a space. It is guaranteed that all the integers are in the range of long int

12、.输出 For each test case you should output the median of the two given sequences in a line.样例输入4 11 12 13 145 9 10 15 16 17样例输出132011年浙江大学计算机及软件工程研究生机试真题 1005: Graduate Admission题目描述 It is said that in 2011, there are about 100 graduate schools ready to proceed over 40,000 applications in Zhejiang Pro

13、vince. It would help a lot if you could write a program to automate the admission procedure. Each applicant will have to provide two grades: the national entrance exam grade GE, and the interview grade GI. The final grade of an applicant is (GE + GI) / 2. The admission rules are: The applicants are

14、ranked according to their final grades, and will be admitted one by one from the top of the rank list. If there is a tied final grade, the applicants will be ranked according to their national entrance exam grade GE. If still tied, their ranks must be the same. Each applicant may have K choices and

15、the admission will be done according to his/her choices: if according to the rank list, it is ones turn to be admitted; and if the quota of ones most preferred shcool is not exceeded, then one will be admitted to this school, or ones other choices will be considered one by one in order. If one gets

16、rejected by all of preferred schools, then this unfortunate applicant will be rejected. If there is a tied rank, and if the corresponding applicants are applying to the same school, then that school must admit all the applicants with the same rank, even if its quota will be exceeded.输入 Each input fi

17、le may contain more than one test case. Each case starts with a line containing three positive integers: N (40,000), the total number of applicants; M (100), the total number of graduate schools; and K (5), the number of choices an applicant may have. In the next line, separated by a space, there ar

18、e M positive integers. The i-th integer is the quota of the i-th graduate school respectively. Then N lines follow, each contains 2+K integers separated by a space. The first 2 integers are the applicants GE and GI, respectively. The next K integers represent the preferred schools. For the sake of s

19、implicity, we assume that the schools are numbered from 0 to M-1, and the applicants are numbered from 0 to N-1.输出 For each test case you should output the admission results for all the graduate schools. The results of each school must occupy a line, which contains the applicants numbers that school

20、 admits. The numbers must be in increasing order and be separated by a space. There must be no extra space at the end of each line. If no applicant is admitted by a school, you must output an empty line correspondingly.样例输入11 6 32 1 2 2 2 3100 100 0 1 260 60 2 3 5100 90 0 3 490 100 1 2 090 90 5 1 38

21、0 90 1 0 280 80 0 1 280 80 0 1 280 70 1 3 270 80 1 2 3100 100 0 2 4样例输出0 1035 6 72 81 42010年浙江大学计算机及软件工程研究生机试真题 1006: ZOJ问题题目描述对给定的字符串(只包含z,o,j三种字符),判断他是否能AC。是否AC的规则如下：1. zoj能AC；2. 若字符串形式为xzojx，则也能AC，其中x可以是N个o 或者为空；3. 若azbjc 能AC，则azbojac也能AC，其中a,b,c为N个o或者为空；输入输入包含多组测试用例，每行有一个只包含z,o,j三种字符的字符串，字符串长度小于

22、等于1000。输出对于给定的字符串，如果能AC则请输出字符串“Accepted”，否则请输出“Wrong Answer”。样例输入zojozojoozoojoooozoojoooozoojozojooooozojozojoooo样例输出AcceptedAcceptedAcceptedAcceptedAcceptedAcceptedWrong AnswerWrong Answer2010年浙江大学计算机及软件工程研究生机试真题1007: 奥运排序问题题目描述按要求，给国家进行排名。输入有多组数据。第一行给出国家数N，要求排名的国家数M，国家号从0到N-1。第二行开始的N行给定国家或地区的奥运金牌

23、数，奖牌数，人口数（百万）。接下来一行给出M个国家号。输出排序有4种方式: 金牌总数 奖牌总数 金牌人口比例 奖牌人口比例 对每个国家给出最佳排名排名方式 和 最终排名格式为: 排名:排名方式如果有相同的最终排名，则输出排名方式最小的那种排名，对于排名方式，金牌总数 奖牌总数 金牌人口比例 奖牌人口比例 如果有并列排名的情况，即如果出现金牌总数为 100,90,90,80.则排名为1,2,2,4.每组数据后加一个空行。样例输入4 44 8 16 6 24 8 22 12 40 1 2 34 28 10 18 11 28 12 38 13 40 3样例输出1:31:12:11:21:11:120

24、10年浙江大学计算机及软件工程研究生机试真题1008: 最短路径问题题目描述给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。输入输入n,m，点的编号是1n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点t。n和m为0时输入结束。(1n=1000, 0m100000, s != t)输出输出 一行有两个数， 最短距离及其花费。样例输入3 21 2 5 62 3 4 51 30 0样例输出9 112010年浙江大学计算机

25、及软件工程研究生机试真题1009: 二叉搜索树题目描述 判断两序列是否为同一二叉搜索树序列输入开始一个数n，(1=n=20) 表示有n个需要判断，n= 0 的时候输入结束。接下去一行是一个序列，序列长度小于10，包含(09)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。输出 如果序列相同则输出YES，否则输出NO样例输入25674325432675763420样例输出YESNO提示来源2005年浙江大学计算机及软件工程研究生机试真题1010: A + B题目描述读入两个小于100的正

26、整数A和B,计算A+B.需要注意的是:A和B的每一位数字由对应的英文单词给出.输入测试输入包含若干测试用例,每个测试用例占一行,格式为A + B =,相邻两字符串有一个空格间隔.当A和B同时为0时输入结束,相应的结果不要输出.输出 对每个测试用例输出1行,即A+B的值.样例输入one + two =three four + five six =zero seven + eight nine =zero + zero =样例输出390962005年浙江大学计算机及软件工程研究生机试真题1011: 最大连续子序列题目描述 给定K个整数的序列 N1, N2, ., NK ，其任意连续子序列可表示为

27、Ni, Ni+1, ., Nj ，其中 1 = i = j = K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列 -2, 11, -4, 13, -5, -2 ，其最大连续子序列为 11, -4, 13 ，最大和为20。现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。输入 测试输入包含若干测试用例，每个测试用例占2行，第1行给出正整数K( K 10000 )，第2行给出K个整数，中间用空格分隔。当K为0时，输入结束，该用例不被处理。输出 对每个测试用例，在1行里输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号

28、i和j最小的那个（如输入样例的第2、3组）。若所有K个元素都是负数，则定义其最大和为0，输出整个序列的首尾元素。样例输入6-2 11 -4 13 -5 -210-10 1 2 3 4 -5 -23 3 7 -2165 -8 3 2 5 01103-1 -5 -23-1 0 -20样例输出20 11 1310 1 410 3 510 10 100 -1 -20 0 02005年浙江大学计算机及软件工程研究生机试真题1012: 畅通工程题目描述 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直

29、接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？输入 测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( 0 )，下面列出了N天的记录。 每天的记录在第一行给出记录的条目数M (M 0 )，下面是M行，每行的格式为 证件号码 签到时间 签离时间 其中时间按“小时:分钟:秒钟”（各占2位）给出，证件号码是长度不超过15的字符串。输出 对每一天的记录输出1行，即当天开门和关门人的证件号码，中间用1空格分隔。 注意：在裁判的标准测试输入中，所有记录保证完整，每个人的签到时间在签离时间之前，且没有多人同时签到或者签离的情况。样例输入31ME30

30、21112225321 00:00:00 23:59:592EE301218 08:05:35 20:56:35MA301134 12:35:45 21:40:423CS301111 15:30:28 17:00:10SC3021234 08:00:00 11:25:25CS301133 21:45:00 21:58:40样例输出ME3021112225321 ME3021112225321EE301218 MA301134SC3021234 CS3011332005年浙江大学计算机及软件工程研究生机试真题1014: 排名题目描述 今天的上机考试虽然有实时的Ranklist，但上面的排名只是根

31、据完成的题数排序，没有考虑每题的分值，所以并不是最后的排名。给定录取分数线，请你写程序找出最后通过分数线的考生，并将他们的成绩按降序打印。输入测试输入包含若干场考试的信息。每场考试信息的第1行给出考生人数N ( 0 N 1000 )、考题数M ( 0 M = 10 )、分数线（正整数）G；第2行排序给出第1题至第M题的正整数分值；以下N行，每行给出一名考生的准考证号（长度不超过20的字符串）、该生解决的题目总数m、以及这m道题的题号（题目号由1到M）。 当读入的考生人数为0时，输入结束，该场考试不予处理。输出 对每场考试，首先在第1行输出不低于分数线的考生人数n，随后n行按分数从高到低输出上线

32、考生的考号与分数，其间用1空格分隔。若有多名考生分数相同，则按他们考号的升序输出。样例输入4 5 2510 10 12 13 15CS004 3 5 1 3CS003 5 2 4 1 3 5CS002 2 1 2CS001 3 2 3 51 2 4010 30CS001 1 22 3 2010 10 10CS000000000000000001 0CS000000000000000002 2 1 20样例输出3CS003 60CS001 37CS004 3701CS000000000000000002 20提示来源2006年浙江大学计算机及软件工程研究生机试真题1015: 还是A+B题目描述读

33、入两个小于10000的正整数A和B，计算A+B。需要注意的是：如果A和B的末尾K（不超过8）位数字相同，请直接输出-1。输入测试输入包含若干测试用例，每个测试用例占一行，格式为A B K，相邻两数字有一个空格间隔。当A和B同时为0时输入结束，相应的结果不要输出。输出对每个测试用例输出1行，即A+B的值或者是-1。样例输入1 2 111 21 1108 8 236 64 30 0 1样例输出3-1-11002006年浙江大学计算机及软件工程研究生机试真题1016: 火星A+B题目描述 读入两个不超过25位的火星正整数A和B，计算A+B。需要注意的是：在火星上，整数不是单一进制的，第n位的进制就是

34、第n个素数。例如：地球上的10进制数2，在火星上记为“1,0”，因为火星个位数是2进制的；地球上的10进制数38，在火星上记为“1,1,1,0”，因为火星个位数是2进制的，十位数是3进制的，百位数是5进制的，千位数是7进制的输入 测试输入包含若干测试用例，每个测试用例占一行，包含两个火星正整数A和B，火星整数的相邻两位数用逗号分隔，A和B之间有一个空格间隔。当A或B为0时输入结束，相应的结果不要输出。输出 对每个测试用例输出1行，即火星表示法的A+B的值。样例输入1,0 2,14,2,0 1,2,01 10,6,4,2,10 0样例输出1,0,11,1,1,01,0,0,0,0,02006年浙

35、江大学计算机及软件工程研究生机试真题1017: 还是畅通工程题目描述 某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。输入 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。 当N为0时，输入结束，该用例不被处理。输出 对每个测试用例，在1行里输

36、出最小的公路总长度。样例输入31 2 11 3 22 3 441 2 11 3 41 4 12 3 32 4 23 4 50样例输出352006年浙江大学计算机及软件工程研究生机试真题1018: 统计同成绩学生人数题目描述读入N名学生的成绩，将获得某一给定分数的学生人数输出。输入测试输入包含若干测试用例，每个测试用例的格式为第1行：N第2行：N名学生的成绩，相邻两数字用一个空格间隔。第3行：给定分数当读到N=0时输入结束。其中N不超过1000，成绩分数为（包含）0到100之间的一个整数。输出对每个测试用例，将获得给定分数的学生人数输出。样例输入380 60 9060285 660560 75

37、90 55 75750样例输出1022006年浙江大学计算机及软件工程研究生机试真题1019: 简单计算器题目描述 读入一个只包含 +, -, *, / 的非负整数计算表达式，计算该表达式的值。输入 测试输入包含若干测试用例，每个测试用例占一行，每行不超过200个字符，整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束，相应的结果不要输出。输出 对每个测试用例输出1行，即该表达式的值，精确到小数点后2位。样例输入1 + 24 + 2 * 5 - 7 / 110样例输出3.0013.362007年浙江大学计算机及软件工程研究生机试真题1020: 最小长方形题目描述 给定一系

38、列2维平面点的坐标(x, y)，其中x和y均为整数，要求用一个最小的长方形框将所有点框在内。长方形框的边分别平行于x和y坐标轴，点落在边上也算是被框在内。输入 测试输入包含若干测试用例，每个测试用例由一系列坐标组成，每对坐标占一行，其中|x|和|y|小于 231；一对0 坐标标志着一个测试用例的结束。注意(0, 0)不作为任何一个测试用例里面的点。一个没有点的测试用例标志着整个输入的结束。输出 对每个测试用例，在1行内输出2对整数，其间用一个空格隔开。第1对整数是长方形框左下角的坐标，第2对整数是长方形框右上角的坐标。样例输入12 5623 5613 100 012 340 00 0样例输出1

39、2 10 23 5612 34 12 342007年浙江大学计算机及软件工程研究生机试真题1021: 统计字符题目描述 统计一个给定字符串中指定的字符出现的次数。输入 测试输入包含若干测试用例，每个测试用例包含2行，第1行为一个长度不超过5的字符串，第2行为一个长度不超过80的字符串。注意这里的字符串包含空格，即空格也可能是要求被统计的字符之一。当读到#时输入结束，相应的结果不要输出。输出 对每个测试用例，统计第1行中字符串的每个字符在第2行字符串中出现的次数，按如下格式输出： c0 n0 c1 n1 c2 n2 . 其中ci是第1行中第i个字符，ni是ci出现的次数。样例输入ITHIS IS

40、 A TESTi ngthis is a long test string#样例输出I 2i 3 5n 2g 22007年浙江大学计算机及软件工程研究生机试真题1022: 游船出租题目描述 现有公园游船租赁处请你编写一个租船管理系统。当游客租船时，管理员输入船号并按下S键，系统开始计时；当游客还船时，管理员输入船号并按下E键，系统结束计时。船号为不超过100的正整数。当管理员将0作为船号输入时，表示一天租船工作结束，系统应输出当天的游客租船次数和平均租船时间。 注意：由于线路偶尔会有故障，可能出现不完整的纪录，即只有租船没有还船，或者只有还船没有租船的纪录，系统应能自动忽略这种无效纪录。输入

41、测试输入包含若干测试用例，每个测试用例为一整天的租船纪录，格式为： 船号（1100） 键值（S或E） 发生时间（小时:分钟） 每一天的纪录保证按时间递增的顺序给出。当读到船号为-1时，全部输入结束，相应的结果不要输出。输出 对每个测试用例输出1行，即当天的游客租船次数和平均租船时间（以分钟为单位的精确到个位的整数时间）。样例输入1 S 08:102 S 08:351 E 10:002 E 13:160 S 17:000 S 17:003 E 08:101 S 08:202 S 09:001 E 09:200 E 17:00-1样例输出2 1960 01 602007年浙江大学计算机及软件工程研

42、究生机试真题1023: EXCEL排序题目描述 Excel可以对一组纪录按任意指定列排序。现请你编写程序实现类似功能。 对每个测试用例，首先输出1行“Case i:”，其中 i 是测试用例的编号（从1开始）。随后在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当 C=2时，按姓名的非递减字典序排序；当 C=3 时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。输入 测试输入包含若干测试用例。每个测试用例的第1行包含两个整数 N (N=100000) 和 C，其中 N 是纪录的条数，C 是指定排序的列号。以下有N行，每行包含一条学生纪录

43、。每条学生纪录由学号（6位数字，同组测试中没有重复的学号）、姓名（不超过8位且不包含空格的字符串）、成绩（闭区间0, 100内的整数）组成，每个项目间用1个空格隔开。当读到 N=0 时，全部输入结束，相应的结果不要输出。输出 对每个测试用例，首先输出1行“Case i:”，其中 i 是测试用例的编号（从1开始）。随后在 N 行中输出按要求排序后的结果，即：当 C=1 时，按学号递增排序；当 C=2时，按姓名的非递减字典序排序；当 C=3 时，按成绩的非递减排序。当若干学生具有相同姓名或者相同成绩时，则按他们的学号递增排序。样例输入3 1000007 James 85000010 Amy 900

44、00001 Zoe 604 2000007 James 85000010 Amy 90000001 Zoe 60000002 James 984 3000007 James 85000010 Amy 90000001 Zoe 60000002 James 900 0样例输出Case 1:000001 Zoe 60000007 James 85000010 Amy 90Case 2:000010 Amy 90000002 James 98000007 James 85000001 Zoe 60Case 3:000001 Zoe 60000007 James 85000002 James 9000

45、0010 Amy 902007年浙江大学计算机及软件工程研究生机试真题1024: 畅通工程题目描述 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。经过调查评估，得到的统计表中列出了有可能建设公路的若干条道路的成本。现请你编写程序，计算出全省畅通需要的最低成本。输入 测试输入包含若干测试用例。每个测试用例的第1行给出评估的道路条数 N、村庄数目M (N, M =100 )；随后的 N 行对应村庄间道路的成本，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间道路的成本（也是正整数）。为简单起见，村庄从1到M编号。当

46、N为0时，全部输入结束，相应的结果不要输出。输出 对每个测试用例，在1行里输出全省畅通需要的最低成本。若统计数据不足以保证畅通，则输出“?”。样例输入3 31 2 11 3 22 3 41 32 3 20 100样例输出3?2007年浙江大学计算机及软件工程研究生机试真题1025: 最大报销额题目描述 现有一笔经费可以报销一定额度的发票。允许报销的发票类型包括买图书（A类）、文具（B类）、差旅（C类），要求每张发票的总额不得超过1000元，每张发票上，单项物品的价值不得超过600元。现请你编写程序，在给出的一堆发票中找出可以报销的、不超过给定额度的最大报销额。输入 测试输入包含若干测试用例。每

47、个测试用例的第1行包含两个正数 Q 和 N，其中 Q 是给定的报销额度，N（N=30）是发票张数。随后是 N 行输入，每行的格式为： m Type_1:price_1 Type_2:price_2 . Type_m:price_m 其中正整数 m 是这张发票上所开物品的件数，Type_i 和 price_i 是第 i 项物品的种类和价值。物品种类用一个大写英文字母表示。当N为0时，全部输入结束，相应的结果不要输出。输出 对每个测试用例输出1行，即可以报销的最大数额，精确到小数点后2位。样例输入200.00 32 A:23.50 B:100.001 C:650.003 A:59.99 A:120

48、.00 X:10.001200.00 22 B:600.00 A:400.001 C:200.501200.50 32 B:600.00 A:400.001 C:200.501 A:100.00100.00 0样例输出123.501000.001200.502008年浙江大学计算机及软件工程研究生机试真题1026: 又一版 A+B题目描述输入两个不超过整型定义的非负10进制整数A和B(=231-1)，输出A+B的m (1 m 10)进制数。输入输入格式：测试输入包含若干测试用例。每个测试用例占一行，给出m和A，B的值。当m为0时输入结束。输出输出格式：每个测试用例的输出占一行，输出A+B的m进

49、制数。样例输入8 1300 482 1 70样例输出250410002008年浙江大学计算机及软件工程研究生机试真题1027: 欧拉回路题目描述 欧拉回路是指不令笔离开纸面，可画过图中每条边仅一次，且可以回到起点的一条回路。现给定一个图，问是否存在欧拉回路？输入 测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是节点数N ( 1 N 1000 )和边数M；随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号（节点从1到N编号）。当N为0时输入结束。输出 每个测试用例的输出占一行，若欧拉回路存在则输出1，否则输出0。样例输入3 31 21 32 33

50、21 22 30样例输出102008年浙江大学计算机及软件工程研究生机试真题1028: 继续畅通工程题目描述 省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可）。现得到城镇道路统计表，表中列出了任意两城镇间修建道路的费用，以及该道路是否已经修通的状态。现请你编写程序，计算出全省畅通需要的最低成本。输入 测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 1 N 100 )；随后的 N(N-1)/2 行对应村庄间道路的成本及修建状态，每行给4个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本，以

51、及修建状态：1表示已建，0表示未建。 当N为0时输入结束。输出 每个测试用例的输出占一行，输出全省畅通需要的最低成本。样例输入31 2 1 01 3 2 02 3 4 031 2 1 01 3 2 02 3 4 131 2 1 01 3 2 12 3 4 10样例输出3102008年浙江大学计算机及软件工程研究生机试真题1029: 魔咒词典题目描述 哈利波特在魔法学校的必修课之一就是学习魔咒。据说魔法世界有100000种不同的魔咒，哈利很难全部记住，但是为了对抗强敌，他必须在危急时刻能够调用任何一个需要的魔咒，所以他需要你的帮助。 给你一部魔咒词典。当哈利听到一个魔咒时，你的程序必须告诉他那个

52、魔咒的功能；当哈利需要某个功能但不知道该用什么魔咒时，你的程序要替他找到相应的魔咒。如果他要的魔咒不在词典中，就输出“what?”输入 首先列出词典中不超过100000条不同的魔咒词条，每条格式为： 魔咒 对应功能 其中“魔咒”和“对应功能”分别为长度不超过20和80的字符串，字符串中保证不包含字符“”和“”，且“”和后面的字符串之间有且仅有一个空格。词典最后一行以“END”结束，这一行不属于词典中的词条。 词典之后的一行包含正整数N（=1000），随后是N个测试用例。每个测试用例占一行，或者给出“魔咒”，或者给出“对应功能”。输出 每个测试用例的输出占一行，输出魔咒对应的功能，或者功能对应的魔咒。如果魔咒不在词典中，就输出“what?”样例输入expelliarmus the disarming charmrictusempra send a jet of silver light to hit the enemytarantallegra