北航算法上机题目

更新时间：2023-11-30 00:49:01 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

数据结构与算法上机题推荐度：
相关推荐

算法上机1A

访问统计时间限制：1000 ms | 内存限制：65535 KB 描述

有若干个网站，已知在某一特定星期内每个网站的日访问量情况。现在的问题是，按照网站在这一星期内的总访问量由高到低排序，并输出结果。

输入

只有一组测试数据，第一行：一个正整数N，表示将出现的网址个数。(2<=N<=50) 接下来有N行，每行有一个字符串(中间无空格)，表示网址。保证N个网址互不相同。接下来有一个正整数M，表示M条记录。2<=M<=100 然后有M行，每行的有一个字符串S(长度小于100)，整数T(1<=T<=7)，整数V(0<=V<=100)，表示网站S在星期T里有V的访问量，保证S是前面所述的N个网站中的某一个。注意：保证记录不会重复，同一网站在同一天里的记录也不会出现两次。如果某网站在某天里的记录没有出现，表明该网站在改天里的访问量为0

输出

按照网站在这一星期里的总访问量由高到低排序，访问量相同的按字典序的升序排序. 格式：网址+一个空格+访问量具体参见样例

样例输入 4

http://www.google.com.hk http://www.buaa.edu.cn http://www.qq.com http://www.http://www.wodefanwen.com/ 9

http://www.google.com.hk 1 0 http://www.google.com.hk 2 0 http://www.google.com.hk 7 100 http://www.google.com.hk 6 200 http://www.http://www.wodefanwen.com/ 1 2 http://www.qq.com 1 20 http://www.http://www.wodefanwen.com/ 2 6

http://www.buaa.edu.cn 7 3 http://www.buaa.edu.cn 6 5 样例输出

http://www.google.com.hk 300 http://www.qq.com 20 http://www.http://www.wodefanwen.com/ 8 http://www.buaa.edu.cn 8

计算罚时时间限制：1000 ms | 内存限制：65536 KB 描述

在编程啦比赛的记分板上，有一列叫做“罚时”，这个奇怪的数字究竟是怎么算出来的呢？

留意的同学可能知道，记分板的“查看记分详单”页面，有这么一段注释：

注：(X/Y) —— X表示该题提交次数，Y表示首次通过该题的时间，单位为分钟。对通过的题计算罚时，计算方式为 (X-1)*20 + Y。未通过的题不计算罚时。

具体说来，其中X表示该题首次正确提交之前（包括正确那次）该题的提交次数，比如某次上机中，豆豆同学的提交记录如下（比赛开始时间为14：30）：

· B Accepted (AC) 14:52

· A Wrong Answer (WA) 14:58

· A Wrong Answer (WA) 14:59

· A Wrong Answer (WA) 15:00

· A Accepted (AC) 15:05

· C Wrong Answer (WA) 15:12

· C Wrong Answer (WA) 15:14

· C Accepted (AC) 15:15

· D Accepted (AC) 15:21

· A Presentation Error (PE) 15:32

· A Accepted (AC) 15:33

· E Time Limit Exceeded (TLE) 15:55

则对于A题，X=4（计算该题的X时无视该题AC后的提交记录以及其他题的记录），Y=35（分钟），由于通过该题带来的罚时为：（4-1）*20+35=95；

对于E题，罚时为零，因为这题始终没有通过（Accepted）。

现在，告诉你某次上机中，豆豆的所有提交记录，你能帮助豆豆计算出罚时吗？输入

第一行为一个整数M，表示有M组数据（M<10）。

对于每组数据，第一行为一个整数N，表示共有N条提交记录（N<20）。

以下N行，每行有两个整数P、T和一个字符串S，表示第P题在比赛开始后第T分钟有一次提交（1<=P<=5，0<=T<=150），结果为S，S为以下7种情况之一（缩写）：

· Accepted (AC)

· Presentation Error (PE)

· Compilation Error (CE)

· Wrong Answer (WA)

· Runtime Error (RE)

· Time Limit Exceeded (TLE)

· Memory Limit Exceeded (MLE)

详见样例，其中N条记录已按照时间顺序排列。

输出

对于每组数据输出一行，即总罚时（各题的罚时之和）。样例输入 2 2

1 10 WA 1 15 AC 4

1 10 WA 2 15 AC 2 17 PE 2 17 AC 样例输出 35 15

基础分治法时间限制：1000 ms | 内存限制：65535 KB 描述

这是一很经典的问题，要你计算 X=Y^Z mod D，其中Y,Z的范围是： [0,2147483647], D的范围是：[1,46340] 输入

多组测试数据，每组测试数据占一行，有三个整数Y,Z,D 输出

输出X，每组输出占一行

样例输入 3 18132 17 17 1765 3

2374859 3029382 36123 样例输出 13 2

13195

提示分治法：

X=Y^Z mod D , Z为偶数,等价于(Y*Y)^(Z/2) mod D; Z为奇数时，等价于 (Y*Y)^(Z/2) * Y mod D ; 火星

时间限制：2000 ms | 内存限制：65535 KB 描述

DJY是一个火星数学家。一天，DJY拜访地球，和地球人XiaoM在讨论数学问题。DJY写出很多的等式(火星数学家也使用阿拉伯数字），但是XiaoM却很迷惑，因为很多等式在地球都是不成立的，比如：1+1=110， 110+111=101 原来，在DJY所在的火星上，人们使用的进制不是10进制，也不是2进制，而是-2进制. “-2进制?!\感到很奇怪。原来，-2进制是这样定义的：一个整数N（注意：可以是负整数）的-2进制表示形式是一串数字Bi（从右到左写），Bi只能为0或1，并且必须满足以下等式（地球上的等式）

N=B0+B1*(-2)+B2*(-2)^2+B3*(-2)^3+..... .

明显，对于任何一个确定的整数N，N的-2进制表示形式都是唯一的（注意：除了0以外，首位数字（即最左边的数字）不能为0，这和地球上是一样的）。现在你的任务是，给你一个正整数N，请你输出N的-2进制表示形式. N的范围是 -1,000,000,000 到 1,000,000,000. 输入

第一个整数是测试数据组数T(T<=100) 接下来有T行，每行一个整数N 输出

输出N的-2进制表示，具体格式见样例

样例输入 4 1 7 -2 0

样例输出 Case #1: 1

Case #2: 11011 Case #3: 10 Case #4: 0

提示

这里，(-2)^2 表示 (-2)的2次方

跳棋小游戏时间限制：1000 ms | 内存限制：65536 KB 描述

在一条直线棋盘上，有N个小洞，每个小洞可以放置一个跳棋。

初始状态，我们放置一些跳棋，作为初始状态。有跳棋的小洞我们用小写字母“欧”表示,即\没有放跳棋的小洞用\表示，即减号

在棋盘上，如果出现(...)-oo(...)的情况，（注意，括号表示省略，我们只关注中间部分），那么我们可以把右边的跳棋往左跳；如果出现(...)oo-(...)的情况，那么我们可以把左边的跳棋往右跳，

但是，只要跳棋A越过跳棋B，那么B就要从棋盘上拿掉，因此这两种情况在跳过之后会变成(...)o--(...)和(...)--o(...)

现在问题是，如果在一个有12个小洞的棋盘上，能得到到的最小跳棋数是多少

输入

一个整数N

代表N组数据

每组数据为12个字符，拼成一个棋盘

输出

对应每组数据最少可以得到的跳棋数

样例输入 5

---oo------- -o--o-oo---- -o----ooo--- oooooooooooo oooooooooo-o 样例输出 1 2 3 12 1

成绩计算时间限制：1000 ms | 内存限制：65536 KB 描述

大家都知道，今年的算法课程的期末成绩是由以下几部分组成的：

平时上机（30'）

期末上机考试（30'）

期末笔试（40'）

加分项（大作业，算法讨论）（20'）

如果这几项的和超过了100分，就按100分计算。

现在，已知某位同学这几项的成绩，你能帮他计算出总分吗？

输入

第一行一个整数t，表示有t组数据以下每行有4个整数，分别对应以上各项成绩。

输出

每组数据输出一行，即问题的答案。

样例输入 2

28 27 30 10 30 30 39 15

样例输出 95 100 提示

由于上周五上机的结果不够理想，考虑大家的整体编程能力，从这次上机开始，简单题的难度会进一步降低。对于第一次上机A、B两次题目难度不同的情况，我们在分数上会区别对待。大家加油！

电灯泡时间限制：1000 ms | 内存限制：65535 KB 描述

电灯泡。额。

走廊里有N个灯泡，编号为1到N，每个灯泡都由一个相应的开关控制着，每按一次该开关就会改变这个灯泡的亮灭状态，这和我们日常生活的常识是一致的。

某年某月的某一天，XiaoM和MM玩了这样一个游戏：首先，XiaoM把这N个电灯泡的亮灭状态设置为L1,L2,L3,...,LN，其中Li(1<=i<=N) 为1或0，表示灯泡为亮或灭。然后，MM进行N次操作，对于第i次操作，编号为i的倍数的灯泡的开关都会被各按一次。 MM希望进行了N次操作后，灯泡的

亮灭状态为 Lg1,Lg2,....,LgN (Lgi为1或0，表示灯泡的亮或灭)。为了满足MM的要求，XiaoM一开始应该如何设置L1，L2，L3，..., LN 呢？

输入

多组测试数据

每组测试数据有两行，第一行是一个正整数N (1<=N<=10000),第二行是N个只能取0或1的整数Lg1,Lg2,...,LgN

输出

对于每组测试数据，输出L1，L2，..., LN,占一行，Li和L(i+1)之间有一个空格，行末无多余的空格样例输入 3 1 1 1 样例输出 0 1 1

提示

scanf and printf is recommended.

the bee 时间限制：1000 ms | 内存限制：65536 KB 描述

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。如图。

试求蜜蜂从蜂房a爬到蜂房b的可能路线数。输入

第一行一个整数表示数据组数（多组数据），对于每组数据只一行有两个整数a,b (1≤a < b≤40) 输出

对于每组输入，输出一行，即从蜂房a爬到蜂房b的可能路线数。

样例输入 1 1 5

样例输出 5

矩形图像覆盖时间限制：2000 ms | 内存限制：65535 KB 描述

由一种大写字母围成了一个封闭的矩形，矩形的长、宽至少为3，矩形的边的厚度严格为1，如下图所示：

这是一个8x6的矩形。每条边的厚度都严格是1。对于每个矩形，围成边的大写字母只有一种。不同矩形，大写字母不同。 XiaoM有一部特殊的摄像机，他把一个RxC的矩形完整拍摄在一个NxM的底片上(R<=N,C<=M)。很明显，拍摄的位置不同，我们可以得到不同的照片，（注意：不能旋转矩形，也不能旋转底片，也即：在最后的照片里，底片还必须是N行M列，矩形还必须是R行C列，矩形还必须是完整的）例如，把上面8x6的矩形拍摄在9x7的底片上时，可以得到的全部照片如下：

图中的'.'表示透明部分，大写字母表示矩形部分、不透明的。设想将以下两张9x7的照片叠放在一起：

其中第一幅在底部，第二幅在上面，那么将会得到如下结果：

该结果中，非透明部分的面积是：32（即有32个字母）显然，如果改变这两个矩形框的在底片中的拍摄位置，那么覆盖后得到的非透明部分的面积就会不同。你的任务是，给出底片大小RxC,在底部的矩形大小N1xM1,在顶部的矩形大小N2xM2，给出覆盖后非透明部分的最大面积。输入

多组测试数据（不超过20组）每组测试数据占一行，给出四个正整数：R C N1 M1 N2 M2 其中： 3<=R,C<10, 3<=N1,N2<=R, 3<=M1,M2<=C

输出

一个整数，覆盖后的非透明部分的最大面积，每组测试数据占一行

样例输入 9 7 3 3 3 3 样例输出 16

改进版N皇后时间限制：5000 ms | 内存限制：65535 KB 描述

某年月日，N个皇后又聚到了一起，她们不想再玩老掉牙的N皇后游戏了，于是乎，她们学会了“马”的步法??

在NXN格的国际象棋棋盘上摆放N个“加强版”皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，而且，通过国际象棋中“马”的步法也不能互相攻击

“马”的攻击范围如图所示：

问在新规则下，共有多少种摆法。输入

第一行为一个整数T，表示有T组数据。以下T行，每行有一个整数n（0

对于每组数据输出一行，即问题的答案。

样例输入 2 1

10 样例输出 1 4

算法上机2a

Eason的时光倒流时间限制：1000 ms | 内存限制：65535 KB 描述

童年你与谁渡过、圣诗班中唱的歌,再哼一哼可以么,当时谁与你排着坐、白色恤衫灰裤子、再穿一穿可以么、遗憾我当时年纪不可亲手拥抱你欣赏、童年便相识、余下日子多闪几倍光、谁让我倒流时光一起亲身跟你去分享、能留下印象、阅览你家中每道墙、拿着你歌书、与你合唱??

Eason是一名出色的歌手，同时是一位深情的诗人、哲学家、爱情家。“时光倒流二十年”打动了无数的痴男痴女，终于，上帝也被深深感动了?于是，上帝给了Eason回到过去的机会?Wonderful and Romantic? Right？ Of Course。

上帝给Eason开了n扇门，编号1到n，门的种类有两种：A类、B类。A类门能让Eason穿越时空，回到那个她的童年，而如果Eason很不幸进了B类门，那么Eason将还是停留在现在。Eason选择第i扇门的概率是Pi。这里保证P1+P2+?+Pn=1,并且0<=Pi<=1.上帝会给Eason最多m次的机会，每次Eason以上述的概率分布选择一扇门，如果Eason选中了A类门，那么能够实现时光倒流，Eason将直接回到过去。否则，Eason将还是绕回到原地，然后Eason将再以同样的概率分布选择其中一扇门（即：如果上一次Eason选择了B类的门j，那么下次选择门j的概率还是原来的Pj）。当然，如果Eason选择的次数达到了m次还没有回到过去，那么Eason就不能再选择了，他只能留在现在。Eason将一直随机选择某个门进入直到时光倒流或者用尽所有机会。

现在，请你帮Eason计算他回到过去的概率是多少。

输入

多组测试数据，每组测试数据占两行，第一行有两个正整数n,m （1<=n<=10,0<=m<=10），表示n扇门，Eason有m次机会。第二行有n个浮点数Qi(1<=i<=n), 如果Qi>=0,那么表示这扇门是A类的（能回到过去），Eason选中它的概率是Pi=Qi。如果Qi<0，那么表示这扇门是B类的（还是回到现在），并且，Eason选中它的概率是Pi=-Qi。 Eason每次选择门的事件都是独立的。保证|Q1|+|Q2|+?+|Qn|=1.

输出

对于每组测试数据，输出一行，如果Eason回到过去的概率，保留到3位小数。样例输入 2 1 0.5 0.5 2 1 0.5 -0.5 2 1 0 -1 样例输出 1.000 0.500 0.000

扫雷英雄榜时间限制：1000 ms | 内存限制：65536 KB 描述

说起豆豆同学在扫雷方面的造诣，那可是在整个宿舍都数一数二的~从小学开始，豆豆就对扫雷产生了浓厚的兴趣??（以下省略数万字）可是最近他遇到点小麻烦：当他把“扫雷英雄榜”刷到5', 34', 133'之后，就没再刷新过，一段时间下来，豆豆觉得很没成就感，但他又不想清除原来的记录，于是，他就把目光瞄准了室友的电脑??

这天，豆豆以自己的电脑在实验室为由，借来了室友的电脑。由于室友电脑上的扫雷还没玩过，所以记录都是默认的999（单位：秒）。于是，豆豆选定高级开始扫雷。只听鼠标噼里啪啦一阵乱响，豆豆已经获胜了N局了。现在，分别给你这N局的用时，问：豆豆一共刷新了多少次记录呢？

（注：只有本局游戏获胜且用时小于当前记录时，才算刷新一次记录）输入

第一行为一个整数T，表示有T组数据。每组数据中，第一行一个整数N（0

第二行有N个小于999的整数，表示获胜的每局游戏的用时。输出

对于每组数据输出一行，即问题的答案。

样例输入 3 3

200 190 180 3

140 140 140 2

150 160 样例输出 3 1 1

合并排序时间限制：1000 ms | 内存限制：65536 KB 描述

给出一组数，要求用合并排序的方法，求出从小到大排序后的序列。

如果只是这些，一个sort（a，a+N）就搞定了??所以，本题要求输出排序的中间结果。

给出合并排序的伪代码：（分治的思想）

merge_sort(int a[], int s, int f){

如果s和f相等，则直接返回

否则{

M=(s+f)/2;

merge_sort(a, s, m);

merge_sort(a, m+1, f);

// 为保证输出的唯一性，这里规定，排序a[s~f]时，将s ~ (s+f)/2分为一段，(s+f)/2+1 ~ f分为一段

把已经排好序的a[s~m], a[m+1~f]两段合并成一段有序序列，存放在a[s~f]里（可以暂存到另一数组中，再copy过去）

///// 在这里输出排好序的a[s~f]序列，每两个数之间一个空格，末尾换行 } }

例如：5 4 3 2 1，输出结果为：

4 5 //merge_sort(a,0,1)（注：这里是按下标从0开始写的，从1开始不会影响输出结果）

3 4 5 //merge_sort(a,0,2)

1 2 //merge_sort(a,3,4)

1 2 3 4 5 //merge_sort(a,0,4) 输入

第一行为一个整数T，表示有T组数据。每组数据中，第一行一个整数N（2<=N<100）

第二行有N个整数，表示待排序的数组。输出

见伪代码中的描述及样例，每组数据末尾输出一个空行

样例输入 2 5

5 4 3 2 1 9

8 6 4 2 9 7 5 3 1

样例输出 4 5 3 4 5 1 2

1 2 3 4 5 6 8 4 6 8 2 9

2 4 6 8 9 5 7 1 3 1 3 5 7

1 2 3 4 5 6 7 8 9 提示

注意每组数据后输出空行(样例中未显示出最后一组的空行)

我要偷菜时间限制：1000 ms | 内存限制：65536 KB 描述

豆豆虽然没开农场，但还是看别人玩过的。在农场里，为了得到最大的收益，除了自己辛苦种菜之外，去别人农场偷菜就成了赚钱的另一种方式。

话说某天，豆豆在周围某些同学的威逼利诱下，也开通了农场。他想迅速赚钱升级，但又不想花太多时间整天看着，于是，他开始观察大家的种菜习惯，发现每个人种菜的时间是有规律的??

设豆豆共有N个玩农场的好友，他们每人每天种菜一次，为简化问题，假设他们种的都是同一种作物，且每人每天的作物的成熟时间是固定的。由于成熟之后，其他好友也可以去偷，而且主人发现了也会一下收光，所以去晚了就偷不到了。假设对于所有好友种的菜，成熟之后T分钟之内（含第T分钟）是可以偷的，且每个好友那里只能偷1棵。给出N个好友的菜的成熟时间，你能计算出，豆豆每天至少要偷几次才能偷遍所有好友的菜吗？(\偷菜一次\是指在某个时间点, 把当前所有可以偷菜的好友偷一遍, 用时忽略不计)

输入

第一行为一个整数Q，表示有Q组数据。每组数据中，第一行两个整数N，T（0

以下N行每行一个时间字符串，格式“hh:ss”，表示每个好友的菜的成熟时间（08：00~22：00之间）。输出

每组数据输出一行，最少偷菜的次数。

样例输入 2 3 60 11:30 11:50 12:10 3 60 12:30 12:31 11:30 样例输出 1 2

Eason演唱会时间限制：2000 ms | 内存限制：65535 KB 描述

Eason要开演唱会了，这次他的演唱会在一

个特殊的音乐厅中举行。音乐厅是一个三角形的建筑物，里面的房子也是三角形的，它具体按照下面的方式构成：

音乐厅由两个正整数N(N>=1),M(M>=2)表示，N表示音乐厅的层数，M表示每个房子的大小。音乐厅由N层组成，每层含有的房子数从上到下是1到N。建造一个大小为M的房子具体步骤如下：

首先是房顶（即第一行）：

/\\ (斜杠和反斜杠)

然后从i=2行到i=M-1行，它由一个’/’（斜杠）、2*(i-1)个空格、一个‘\\’（反斜杠）组成。