2022年计算机程序算法试题.docx

《2022年计算机程序算法试题.docx》由会员分享，可在线阅读，更多相关《2022年计算机程序算法试题.docx（35页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆1. 数字分解Time limit: 1 Seconds Memory limit: 32768K 描述 Description 今年是国际数学联盟确定的“2000世界数学年” ,又恰逢我国闻名数学家华罗庚先生诞辰 90 周年；在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好伴侣 XZ 也有幸得以参与；活动中,主持人给全部参与活动的选手出了这样一道题目：设有一个长度 N 的数字串,要求选手使用 K 个乘号将它分成 K+1 个部分,找出一种分法,使得这 K+1 个部分的乘积能够为最大；同时,

2、为了帮忙选手能够正确懂得题意,主持人仍举了如下的一个例子：有一个数字串 : 312,当 N=3,K=1 时会有以下两种分法：1）3*12=36 2）31*2=62 这时,符合题目要求的结果是：31*2=62 现在,请你帮忙你的好伴侣输入格式 Input Format XZ 设计一个程序,求得正确的答案；程序的输入共有两行：第一行共有 2 个自然数 N,K 6=N=40 ,1=K=6 其次行是一个 K 度为 N 的数字串；输出格式 Output Format 屏幕输出 结果显示在屏幕上 ,相对于输入,应输出所求得的最大乘积（一个自然数）；名师归纳总结 - - - - - - -第 1 页,共 1

3、9 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆样例输入 Sample Input 4 2 1231 样例输出 Sample Output 62 时间限制 Time Limitation 1 second 来源 Source NOIP 2000 年名师归纳总结 - - - - - - -第 2 页,共 19 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆2. 回文Time Limit: 1 Second 描述 Description Memory Limit: 32768 KB 回文词是一种对称的字符串也就是说,一个回文词,从左

4、到右读和从右到左读得到的结果是一样的；任意给定一个字符串, 通过插入如干字符, 都可以变成一个回文词； 你的任务是写一个程序, 求出将给定字符串变成回文词所 需插入的最少字符数；比如字符串“ Ab3bd” ,在插入两个字符后可以变成一个回文词（“ dAb3bAd”或“Adb3bdA” ）；然而,插入两个以下的字符无法使它变成一个回文词；输入格式 Input Format 第一行包含一个整数N,表示给定字符串的长度,3=N=5000 其次行是一个长度为N 的字符串,字符串由大小写字母和数字构成；输出格式 Output Format 一个整数,表示需要插入的最少字符数；样例输入 Sample In

5、put 5 Ab3bd 样例输出 Sample Output 2 时间限制 Time Limitation 各个测试点 1s 来源 Source 名师归纳总结 - - - - - - -第 3 页,共 19 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆IOI 2000 by Zossin 名师归纳总结 - - - - - - -第 4 页,共 19 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆3. 看球的巴士描述 Description 两个球队的支持者要一起坐车去看球,他们已经排成了一列；我们要让他们 分乘如干辆巴士, 同一

6、辆巴士上的人必需在队伍中是连续的；为了在车上不起冲突,期望两队的支持者人数尽量相等,差至多是D；有一个例外,就是一辆车上的人全部都是一个球队的支持者；问要将这 巴士；N 个人全部送至球场,至少要几辆输入格式Input Format 第一行是整数 N 和 D,1=N=2500,1=D=N ；接下来的 N 行,按排队的次序,描述每个人支持的球队,用 H 或 J 表示；输出格式 Output Format 至少要几辆巴士；样例输入 Sample Input 14 3 H J H H H J H 名师归纳总结 - - - - - - -第 5 页,共 19 页精选学习资料 - - - - - - -

7、- - 学而不思就惘,思而不学就殆J H H H H H H 样例输出 Sample Output 2 时间限制 Time Limitation 1 second 注释 Hint 名师归纳总结 有多种方案,例如让前9 人做一辆车,差正好是3；后 5 人做一辆车,由于第 6 页,共 19 页只有一对的支持者；- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆4. 伪随机数Time Limit: 1 Second Memory Limit: 32768 KB 运算机通常不能产生真正的随机数,但是常常使用运算机来产生伪随机数；由于实际应用,通过算法

8、使得伪随机数成为真随机数；随机数应用广泛,包括在仿真领域；伪随机数生成时用的最普遍的是线性同余法；假如上一次生成的伪随机数是 L,那么接下来的伪随机数通过（z*L+ I ）mod M 产生,这里的 Z 是一个常数乘法器,I 是常数增量,M 是常量模数；例如,假设 Z=7 ,I=5 ,M = 12 ,第一个随机数（通常叫做种子）是 4,那么我们可以得到后续的伪随机数,如下表所示：通过上表我们可以看出,通过这个方法产生的随机数序列在6 个数字以后会重复；明显,由于模数 M ,用这个方法能产生的最长序列是有限的；通过给出的 Z, I, M, 和种子 L ,Z,I,M,L 10000 ,我们确定产生的

9、伪随机数序列的重复周期；留意重复周期不肯定从种子 L 开头；Input 每行有四个数字, 依次是 Z, I, M, 和 L ,其中 L M. 最终一行是 束；Output 对于输入的每行,输出伪随机数序列的重复周期Sample Input 7 5 12 4 5173 3849 3279 1511 9111 5309 6000 1234 1079 2136 9999 1237 0 0 0 0 Sample Output Case 1: 6 Case 2: 546 Case 3: 500 4 个 0,表示输入数据的结名师归纳总结 - - - - - - -第 7 页,共 19 页精选学习资料 -

10、- - - - - - - - 学而不思就惘,思而不学就殆Case 4: 220 名师归纳总结 - - - - - - -第 8 页,共 19 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆5. 机器人规划Time limit: 5 Seconds Memory limit: 32768K 在一个方格地图上放机器人；有三种方格：墙、草地、空地；机器人只能放在空地上,不断 向四个方向发射激光；激光可以穿过草地,但不能穿墙；机器人不能移动；问在使机器人不能相互攻击的情形下,最多可以放多少个机器人；输入：第一行 T=11 代表有 T 组测试数据 ; 每组测试数据第一行

11、为m,n1=m,n=50 代表地图的大小; 下面有 m 行,每行 n 个字符 #,或 o,分别代表墙 ,草地 ,空地 . 输出：对于第 T 组数据 ,第一输出 Case :T; 提行输出最多可以放置的机器人数 . Sample Input 2 4 4 o* *# oo#o *o 4 4 #ooo o#oo oo#o *# Sample Output Case :1 3 Case :2 5 名师归纳总结 - - - - - - -第 9 页,共 19 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆6. 嬉戏Time limit: 10 Seconds Memory

12、 limit: 32768K 最近 Hart 迷上了一种嬉戏： Gnome Tetravex；嬉戏开头给出玩家 n*n 个正方形,每个正方形分成四个三角形,并且分别标号（0 到 9）；在每个正方形里,三角形分成左三角形,上三角形,右三角形和下三角形；例如,图 1 显示了嬉戏的初始状态： 2*2 个正方形图. 1 初始状态： 2*2 个正方形玩家需要移动这些正方形到最终状态；所谓的最终状态就是： 任意两个相邻正方形的相邻三角形的编号要是同一个数字；图 2 就是上面例子的一种最终状态；图. 2 最终状态看起来这个嬉戏不难,实际上,Hart 对这个嬉戏并不熟,他只能完成最简洁的；假如嬉戏复杂一点,他

13、就完成不了；请编程判定嬉戏是否能够完成；Input名师归纳总结 - - - - - - -第 10 页,共 19 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆输入文件包含了几个嬉戏用例；每个嬉戏用例的第一行包含一个整数（0=n=5）,表示嬉戏的正方形个数 n*n；随后的 n*n 行表示每一个正方形内的三角形编号；每一行有四个整数,编号次序按从上,右,下,左；以 0 表示输入文件终止；Output判定每一个嬉戏用例是否能够完成,打印 开每个嬉戏用例的判定结果；Sample Input 2 5 9 1 4 4 4 5 66 8 5 4 0 4 4 3 2 1 1

14、1 12 2 2 2 3 3 3 3 4 4 4 4 0Output for the Sample Input Game 1: Possible Game 2: ImpossiblePossible或者Impossible；以空行隔名师归纳总结 - - - - - - -第 11 页,共 19 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆7. 欧几里得嬉戏Time Limit: 1 Second Memory Limit: 32768 KB Stan 和 Ollie 两个人用两个自然数做嬉戏；第一 Stan 用大数减去小数的正倍数,假设所 得的差是非负的；然后

15、,Ollie 对差和小数进行同样的操作,然后是 Stan,依次交替；直到 有人得到差的结果是 0,就是这个人赢了；例如,他们从（25,7）开头：25 7 11 7 4 7 4 3 1 3 1 0 这个例子是 Stan 赢了 . Input 每行包含嬉戏开头的两个正整数,测试用例以“Output 0 0” 终止； Stan总是先开头嬉戏；对每个测试用例,输出哪个赢的判定结果；输入的最终一行“0 0” 不需要处理；Sample Input 34 12 15 24 0 0 Sample Output Stan wins Ollie wins 名师归纳总结 - - - - - - -第 12 页,共

16、19 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆8. Prime Ring Problem 1 Time Limit: 10 Seconds Memory Limit: 32768 KB A ring is compose of n circles as shown in diagram. Put natural number 1, 2, ., n into each circle separately, and the sum of numbers in two adjacent circles should be a prime. Note: the n

17、umber of first circle should always be 1. Input n 0 n 20 Output The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexico

18、graphical order. You are to write a program that completes above process. Print a blank line after each case. Sample Input 6 8 Sample Output Case 1: 1 4 3 2 5 6 1 6 5 2 3 4 Case 2: 1 2 3 8 5 6 7 4 1 2 5 8 3 4 7 6 名师归纳总结 - - - - - - -第 13 页,共 19 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆1 4 7 6 5 8 3 2

19、1 6 7 4 3 8 5 2 名师归纳总结 - - - - - - -第 14 页,共 19 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆9. 迷宫Time Limit: 10 Seconds Memory Limit: 32768 KB 这些四方块中有的是岩石,有金字塔的北边有个很大的迷宫；迷宫由许多四方块组成,的是空的； 在每个空的四方块中心的地上有些小钩子；分析发觉每两个钩子可以通过一根绳子连接起来,而这根绳子穿过路径（由相互连起来的四方块组成）上的全部方块； 当绳子拉紧的时候, 一个隐匿的门就会打开；问题是我们并不知道要连接哪个钩子,因此所需要绳子的

20、最大长度也是未知的；任务：给出一个迷宫,请确定绳子的最大长度；Input 输入有几个测试用例；第一行的数字T 表示测试用例的数目；每个测试用例的第一行是两个整数 C,R（2=C,R=1000 ） ,分别表示行列数；接下来有 R 行,每行有 C 个字符；字符是“#” 或者“.” ,表示迷宫的内部分布；“ #” 代表岩石四方块, “.” 代表空的四方块；当相邻块紧挨在一起,只能在相邻四方块间行走,不能按对角线行走也不能走出迷宫；迷宫的设计方法是：任意两个空四方块之间只有一条路径；因此, 假如我们可以找到合适的钩子来连接,也就找到了相应的路径；Sample Output 对于每个测试用例,请输出任意

21、两个空四方块间的路径中的最大长度（长度单位是块） ；Sample Input 2 3 3 # #.# # 7 6 # #.#.# #.#.# #.#.#.# #.# # Sample Output Maximum rope length is 0. Maximum rope length is 8. 名师归纳总结 - - - - - - -第 15 页,共 19 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆10. 抄书Time Limit: 1 Second Memory Limit: 32768 KB m 本书分给 k 个抄书员,书的页数为分别为p1,p2.

22、pm,每个抄书员速度相同,而且只能分得连续的如干本书；求一种安排方案使得抄书的所用总时间最少；每个抄书员安排至少一本书；Input 输入的第一行只包含一个整数N,表示有N 个测试用例；接下来是测试用例；每个测试用例包含两行；每个测试用例的第一行有两个整数：m 和 k ,1 = k = m Item names will have length at most 20 and will contain only lowercase letters. 名师归纳总结 - - - - - - -第 17 页,共 19 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆Only

23、 the singular form of an item name will be used no plurals. There will be at most 60 distinct items. There will be at most one assertion for any pair of distinct items. There will be no contradictory assertions. For example, 2 pig = 1 cow, 2 cow = 1 horse, and 2 horse = 3 pig are contradictory. Asse

24、rtions are not necessarily in lowest terms, but output must be. Although assertions use numbers less than 100, queries may result in larger numbers that will not exceed 10000 when reduced to lowest terms. Sample Input . 6 shirt = 15 sock . 47 underwear = 9 pant . sock = shirt . shirt = pant . 2 sock = 1 underwear . pant = shirt . Sample Output 5 sock = 2 shirt . shirt = . pant 45 pant = 188 shirt 名师归纳总结 - - - - - - -第 18 页,共 19 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆名师归纳总结 - - - - - - -第 19 页,共 19 页