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

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

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 现在，请你帮助你的好朋友XZ 设计一个程序，求得正确的答案。输入格式Input Format 程序的输入共有两行：第一行共有 2 个自然数 N，K (6=N=40，1=K=6) 第二行是一个 K 度为 N 的数字串。输出格式Output Format 屏幕输出 (结果显示在屏幕上 )，相对于输入，应输出所求得的最大乘积（一个自然数）。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页，共 19 页学而

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

4、入若干字符， 都可以变成一个回文词。 你的任务是写一个程序， 求出将给定字符串变成回文词所需插入的最少字符数。比如字符串“Ab3bd” ， 在插入两个字符后可以变成一个回文词（ “dAb3bAd”或“Adb3bdA”）。然而，插入两个以下的字符无法使它变成一个回文词。输入格式Input Format 第一行包含一个整数N，表示给定字符串的长度，3=N=5000 第二行是一个长度为N 的字符串，字符串由大小写字母和数字构成。输出格式Output Format 一个整数，表示需要插入的最少字符数。样例输入Sample Input 5 Ab3bd 样例输出Sample Output 2 时间限制Ti

5、me 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 页学而不思则惘，思而不学则殆J H H H H H H 样例输出Sample Outp

7、ut 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) ，我们确定产生的伪随机数序列的重复周期。注意重复周期不一定从种子L 开始。Input 每行有四个数字，依次是 Z, I, M, 和

9、 L，其中 L M. 最后一行是4 个 0，表示输入数据的结束。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 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页，共 19 页学而不思则惘，思而不学则殆Case 4: 220 精选学习资料 - - - - - - -

10、 - - 名师归纳总结 - - - - - - -第 8 页，共 19 页学而不思则惘，思而不学则殆5. 机器人规划Time limit: 5 Seconds Memory limit: 32768K 在一个方格地图上放机器人。有三种方格：墙、草地、空地。机器人只能放在空地上，不断向四个方向发射激光。激光可以穿过草地，但不能穿墙。机器人不能移动。问在使机器人不能互相攻击的情况下，最多可以放多少个机器人。输入：第一行 T(=11) 代表有 T 组测试数据 ; 每组测试数据第一行为m,n(1=m,n=50) 代表地图的大小; 下面有 m 行,每行 n 个字符 #,或 o,分别代表墙 ,草地 ,空地

11、 . 输出：对于第 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 limit: 32768K 最近 Hart 迷上了一种游戏： Gnome Tetravex 。游戏开始给出玩家n*n

12、 个正方形，每个正方形分成四个三角形，并且分别标号（0 到 9）。在每个正方形里，三角形分成左三角形，上三角形，右三角形和下三角形。例如，图1 显示了游戏的初始状态： 2*2 个正方形图. 1 初始状态： 2*2 个正方形玩家需要移动这些正方形到最终状态。所谓的最终状态就是： 任意两个相邻正方形的相邻三角形的编号要是同一个数字。图2 就是上面例子的一种最终状态。图. 2 最终状态看起来这个游戏不难，实际上，Hart 对这个游戏并不熟，他只能完成最简单的。如果游戏复杂一点，他就完成不了。请编程判断游戏是否能够完成。Input精选学习资料 - - - - - - - - - 名师归纳总结 - -

13、- - - - -第 10 页，共 19 页学而不思则惘，思而不学则殆输入文件包含了几个游戏用例。每个游戏用例的第一行包含一个整数（0=n=5），表示游戏的正方形个数n*n。随后的 n*n 行表示每一个正方形内的三角形编号。每一行有四个整数，编号顺序按从上，右，下，左。以 0 表示输入文件结束。Output判断每一个游戏用例是否能够完成，打印Possible或者Impossible。以空行隔开每个游戏用例的判断结果。Sample Input 25 9 1 44 4 5 66 8 5 40 4 4 321 1 1 12 2 2 23 3 3 34 4 4 40Output for the Sam

14、ple Input Game 1: PossibleGame 2: Impossible精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 19 页学而不思则惘，思而不学则殆7. 欧几里得游戏Time Limit: 1 Second Memory Limit: 32768 KB Stan 和 Ollie 两个人用两个自然数做游戏。首先 Stan 用大数减去小数的正倍数，假设所得的差是非负的。然后，Ollie 对差和小数进行同样的操作，然后是Stan，依次交替。直到有人得到差的结果是0，就是这个人赢了。例如，他们从（25,7）开始：25 7

15、 11 7 4 7 4 3 1 3 1 0 这个例子是Stan 赢了 . Input 每行包含游戏开始的两个正整数，测试用例以“0 0”结束。 Stan总是先开始游戏。Output 对每个测试用例，输出哪个赢的判断结果。输入的最后一行“0 0”不需要处理。Sample Input 34 12 15 24 0 0 Sample Output Stan wins Ollie wins 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 19 页学而不思则惘，思而不学则殆8. Prime Ring Problem 1 Time Limit: 1

16、0 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 number of first circle should always be 1. Input n (0 n 20) Output The output fo

17、rmat 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 lexicographical order. You are to write a program that completes above process. Pri

18、nt 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 1 6 7 4 3 8 5 2 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 19 页学而不

19、思则惘，思而不学则殆9. 迷宫Time Limit: 10 Seconds Memory Limit: 32768 KB 金字塔的北边有个很大的迷宫。迷宫由很多四方块组成，这些四方块中有的是岩石，有的是空的。 在每个空的四方块中央的地上有些小钩子。分析发现每两个钩子可以通过一根绳子连接起来，而这根绳子穿过路径（由互相连起来的四方块组成）上的所有方块。当绳子拉紧的时候， 一个隐藏的门就会打开。问题是我们并不知道要连接哪个钩子，因此所需要绳子的最大长度也是未知的。任务：给出一个迷宫，请确定绳子的最大长度。Input 输入有几个测试用例。第一行的数字T 表示测试用例的数目。每个测试用例的第一行是两个

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

21、 # 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.pm，每个抄书员速度相同，而且只能分得连续的若干本书。求一种分配方案使得抄书的所用总时间最少。每个抄书员分配至少一本书。Input 输入的第一行只包含一个整数N，表示

22、有N 个测试用例。接下来是测试用例。每个测试用例包含两行。每个测试用例的第一行有两个整数：m 和 k ，1 = k = m Item names will have length at most 20 and will contain only lowercase letters. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 19 页学而不思则惘，思而不学则殆Only the singular form of an item name will be used (no plurals). There will be at most

23、 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. Assertions are not necessarily in lowest terms, but output must be. Although assertio

24、ns 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 页