北航算法第一次上机题解 | Eternal_zttz

北航算法第一次上机题解

写在前面

北航新学期开学三个星期,21系也迎来了第一次的上机。上机前自己还是有点忐忑的,不过上机前收到了一个惊喜倒是让自己变得好了很多。至于上机结果,还是有点不尽人意的,不过在可接受范围内。为了给自己留个教训,决定写下题解,以此勉励自己吧

A .水水的斐波那契数列


1. 题目描述

相信大家都学过斐波那契数列,虽然很简单,但是斐波那契数列却是很重要的哦,那么让我们来复习一下斐波那契数列吧!

2. 输入

  1. 多组数据输入
  2. 每行一个整数n (0<n<=30)

    3. 输出

    对于每组数据,输出一行,为斐波那契数列第n项的值

4. 解题思路:

这道题的算法不难,首先要牢记斐波那契数列的转换式:

  1. f[1] = f[2] = 1
  2. f[n] = f[n-1]+f[n-2]

从这个式子我们很容易想出递归的思路,然而事实上递归是不行的,正确性没问题,但是,效率上完全不切实际。递归算法的时间复杂度为 ,题目n的范围为(0,30},完全没想法

递归时间复杂度为什么这么高?我们可以这么理解,递归算法每一次都要从头来过,所谓不撞南墙不回头,一条路走到黑。

事实上,大部分的递归算法都可以使用递推来解决,利用数组来保留之前算过的数,可以迅速的得出结果。

另外,我们可以看到,我们每次只是需要数组中的一个数,而数组是不变的,因此,我们可以在输入循环前对数组进行预处理。

时间复杂度为
空间复杂度为

5. AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
long long a[40];
int main(){
int n;
a[1] = 1;
a[2] = 1;
for (int i =3;i<39;i++)
a[i] = a[i-1]+a[i-2];
while(~scanf("%d",&n))
printf("%lld\n",a[n]);
return 0;
}

B. SkyLee的超位魔法-黑暗丰穰之祭献


1. 题目描述

王国军出动24万军队进攻纳萨利克大坟墓,Overlord SkyLee只是微微一笑,区区几十万人就想与我一教高下?让你们见识一下什么叫真正的恐怖吧,超位魔法-黑暗丰穰之祭献! 刹那间,虚空中出现了一头无比恐怖的怪物,名为黑山羊幼崽。

黑山羊幼崽在出现的第5分钟变为完全体,完全体模式下每分钟可以分裂一次,产生一只新的黑山羊幼崽。(黑山羊幼崽不会被弱小的士兵杀死,也不会消失)

虽然王国军面对黑山羊幼崽只能望风而逃,但SkyLee还是想知道自己的实力有多强大,SkyLee沉浸在自己的强大力量中,无暇思考,你能帮他计算在第n
分钟时一共会有多少只黑山羊幼崽么?

2. 输入

  1. 多组数据输入
  2. 每行一个整数n,为第n分钟黑山羊幼崽的数量(总数不超过int)
  3. 请用递归实现

3. 输出

对于每组数据,输出一行,为第n分钟黑山羊幼崽的数量

4. 解题思路

同样是斐波那契数列,只是变换了时间间隔,可以看到,第5分钟开始分裂,那么需要4分钟的成长时间,所以 f[n] = f[n-1]+f[n-4]

注意,完全体的幼崽仍然是幼崽emmm

这题要用递归实现,时间复杂度为 空间复杂度


5. AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
#include <cstdio>
int recursion(int n){
return n<=4? 1:recursion(n-1)+recursion(n-4);
}
int main(){
int n;
while(~scanf("%d",&n)){
int ans = recursion(n);
printf("%d\n",ans);
}
return 0;
}

C. 芸如的入学测试


1. 题目描述

芸如是一位天才科学家,为中国阵营效力。她有着出众的才智,在几年的军旅生活中,芸如研制了许多高科技武器,使得中国军队的武备可以与厄普西隆阵营狡猾的研究成果相抗衡,甚至还可以和整个盟军部队分庭抗礼。

芸如很小的时候就已经开始展现自己的才华,并作为最优秀的幼儿被送往保密培训学校。在她入校的第一天,校长决定亲自考一考这位被外界奉为”天才”的小姑娘。

校长的问题是这样的:

在一个长度为N的数字序列A,有Q组询问,每组询问给定l和r:l≤r,请求出A[l]+A[l+1]+…+A[r]的值。

由于这个结果可能很大,最终的结果要对10007取模(即取余数)。

2. 输入

  1. 多组数据输入,数据组数不超过10。
  2. 第一行是一个数字N,Q,表示序列A中元素的个数和询问组数。(0<N,Q≤1e6)
  3. 第二行是N个整数,第i个整数A[i]表示序列A中的第i个元素,保证均为非负整数,且在INT范围内。
  4. 接下来Q行,每行是两个用空格分隔的整数l和r(保证l和r不会超出序列A下标的范围,且l≤r)。注意序列A的下标从1开始。

3. 输出

对于每组数据,每个询问输出一行,为和值。

4. 解题思路

给定l,r求a[l]~a[r]之间的和的值%10007,第一感觉我们是依次相加,然而这么写每一次询问的时间复杂度为 ,时间复杂度不低

我们可以看到,每一次的询问都是对于同一组数组,所以,我们可以预处理一下数组,同时,使用前缀和可以省去每次相加所带来的时间消耗

每一次查询的时间复杂度为 总时间复杂度为

注意,由于N<=1e6所以,我们需要用long long 来保存数组


5. AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
const int N = 1000001;
long long a[N];
long long sum[N];
using namespace std;
int main(){
int n,q;
while(~scanf("%d %d",&n,&q)){
sum[0] =0 ;
for (int i =1;i<=n;i++){
scanf("%lld",&a[i]);
sum[i] = sum[i-1]+a[i];
}
for (int i =0;i<q;i++){
int l,r;
scanf("%d %d",&l,&r);
printf("%lld\n",(sum[r] - sum[l-1])%10007);
}
}
return 0;
}

D 芸茹的课堂测试


1. 题目描述

霍纳(Horner)规则是一种将一元n次多项式的求值问题转化为n个一次式的算法。采用最小的乘法运算策略,用于求多项式
在x处的值,转化为
。其伪代码如下:

1
2
3
y = 0
for i = n downto 0
y = ai + x * y

给一个8进制数,这个数很大,他的长度甚至可以达到1e6(即10的6次方)。请输出这个数十进制意义下对1e9+7取模(即取余数)的结果。

2. 输入

  1. 第一个数为数据组数n。n <= 10。
  2. 每组数据包括一行,一个大整数S,表示给定的8进制数x。S在字符串意义下长度不超过1e6。

3. 输出

对于每组数据,输出一行,为其十进制下对1e9+7取模的值。

4. 解题思路

秦九韶算法:对于如下公式:

对于一个普通的8位进制数

所以,我们可以利用上面的算法求解十进制数

注意数很长,因此,我们需要用字符来读入数据,通过 a[i] - 0 来转换 为数值b[i]

另外,注意复合的取模运算方法

总时间复杂度为


5. AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
#include <string.h>
#define N 1000000007
char a[1000001];
int b [1000001];
int main(){
int n;
scanf("%d",&n);
for (int i =0;i<n;i++){
memset(a,'\0',sizeof(a));
memset(b,0,sizeof(b));
scanf("%s",a);
int num = strlen(a);
for (int j = 0;j<num;j++)
b[j] = a[j] - '0';
long long ans = b[0];
for (int j = 1;j<num;j++)
ans = (((ans %N) * 8)%N +b[j]%N)%N;
printf("%lld\n",ans);
}
}

E 比特手链


1. 题目描述

叶姐要想哥赠送一串比特手链,这个手链由0和1组成。想哥买了手链B,无意间得知叶姐想要同样长度的手链A。想哥囊中羞涩,只能手工调整手链。他希望最少通过以下操作进行最少步骤把B变成A。注意:A != B

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
对于一个串S:
操作1——选择下标i,j,i != j:
·result = S[i] & S[j]
·S[i] = result & S[i]
·S[j] = result & S[j]


操作2——选择下标i,j,i != j:
·result = S[i] | S[j]
·S[i] = result | S[i]
·S[j] = result | S[j]


操作3——选择下标i,j,i != j:
·result = S[i] ^ S[j]
·S[i] = result ^ S[i]
·S[j] = result ^ S[j]

问想哥最少多少步能达成心愿。如果想哥无法达成心愿,输出-1

解题思路:

2. 输入

  1. 第一个数为数据组数T
  2. 接下来2T行,第2i - 1行为手链B,第2i行为手链A

3. 输出

对于每组数据,输出一行,最少的步骤数。特别地,如果无法达成,输出-1。

4. 解题思路:

这道题看上去比较的复杂,题目的信息量比较大,并且考点是平时接触得比较少的位运算知识。但是,只要先按照题目给出的意思手写出&、|、^的关系式,会发现,其实这道题的题意还是挺好理解的。让我们来看看这三个操作的意思:

&与操作

s[i] s[j] re re&s[i] re&s[j]
0 0 0 0 0
0 1 0 0 0
1 0 0 0 0
1 1 1 1 1

|或操作
| s[i] | s[j] | re | re\s[i] | re\s[j] |
| —- |—- | —- | —-|—-|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1| 1|
| 1 | 1 | 1 |1|1|
emmm 用斜线代替一下,直接写好像会解释错误


^ 异或操作
| s[i] | s[j] | re | re^s[i] | re^s[j] |
| —- |—- | —- | —-|—-|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0| 1|
| 1 | 1 | 0 |1|1|

对比上面三个操作,我们可以看到,对于s[i] == s[j],三个操作均没有变换。
而对于s[i]!=s[j]:

  1. &操作会让1变成0
  2. |操作会让0变成1
  3. ^操作会交换0和1

所以我们可以考虑以下两种情况:

  1. 若手链B全为0 或全为1 ,那么怎么操作都不会改变手链B的值,那么由于B!=A,所以手链B不可能变成手链A,
  2. 若手链B不全为0或1,那么,我们一次对比手链A和B,看需要改变0的次数和改变1的次数,那么 ans = max(num0,num1),即先用^操作交换两个数,使0,1互换,不够了再一个一个的变换。

时间复杂度为

5.题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <cstring>
using namespace std;
char a[1000001];
char b[1000001];
int main(){
int n;
scanf("%d",&n);
for (int i = 0;i<n;i++){
scanf("%s",a);
scanf("%s",b);
int len = strlen(a);
int num0 =0 ,num1 = 0,num= 0;
for (int i = 0;i<len;i++)
if(a[i] == '0')
num++;
if(num == 0 ||num==len){
printf("-1\n");
}
else{
for (int i = 0;i<len;i++){
if(a[i]!=b[i]&&a[i] == '0')
num0++;
else if(a[i]!=b[i]&&a[i] == '1')
num1++;
}
int max = num0>=num1? num0:num1;
printf("%d\n",max);
}
}
}

F.SkyLee的艾露猫


1. 题目描述

众所周知,怪物猎人中的艾露猫是猎人们狩猎时的好伙伴,不仅可以输出,还可以吸引仇恨,甚至还能帮助采集,实在是居家旅行必备之萌物。

艾露猫很可爱,但是寿命只有短短的20年,艾露猫在出生后2年成年,且成年时每对艾露猫都会在年初产下一对小猫,艾露猫成年10年后进入老年,老年持续8年后遗憾地去世。

现在SkyLee得到了一对可爱的艾露猫,他希望艾露猫越多越好,这样打起龙来就很轻松了。假设艾露猫很传统,都是一夫一妻制,并且生出的小猫也正好为一对,若现在为第1年年初,那么第n年SkyLee一共能有多少只可爱的艾露猫呢?

2. 输入

  1. 第一个数为数据组数T
  2. 接下来T行,每行1个整数n(保证艾露猫数量不超过int)

3. 输出

对于每组数据,输出一行,为第n年艾露猫的数量

4. 解题思路

斐波那契自闭

这一题是斐波那契数列的变形题,我们可以分3步讨论

1: 猫不会死也一直会生育,那么

2: 猫不会死但是十年后不会生育,由于猫还需要2年的时间成长,也就是说,12年前的猫不会再生育了,所以

3:猫会死,那么20年前的猫就不在了,

按照这三步来算,将其分为3个阶段,按照程序来写即可

时间复杂度和一般的递推式斐波那契数列一样,均为

5. 题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <cstdio>
#include <iostream>
#include <algorithm>
long long a[1000001];
long long b[10001];
long long c[10001];
using namespace std;
int main(){
int n;
a[0] =0;a[1] = 2;a[2] = 2;
for (int i = 3;i<=60;i++){
if(i<=12)
a[i] = a[i-1]+a[i-2];
else
a[i] = a[i-1]+a[i-2]-a[i-12];
}
scanf("%d",&n);
for (int i= 0;i<n;i++){
int y;
scanf("%d",&y);
if(y<=20)
printf("%lld\n",a[y]);
else
printf("%lld\n",a[y]-a[y-20]);
}
return 0;
}

G. SkyLee在GameStop


1. 题目描述

SkyLee有一天逛街的时候看到一家新开业的GameStop,里面卖各种各样的游戏。
商店里所有的游戏都按游戏名的字典序从小到大排列好了,小的在里面,大的在外面。
SkyLee想要把所有的游戏都试玩(买不起游戏只能看看),但是有些问题:

  1. 游戏只能从展示架的一侧拿出来
  2. SkyLee只能拿1个游戏试玩
  3. 为了不被商店老板发现蹊跷,SkyLee把游戏光盘放回去的时候总要保证每个展示架的游戏仍然按照字典序从小到大排列(小的在里面,大的在外面)
  4. SkyLee虽然没钱但是不可能偷游戏,离开时不能拿着游戏
  5. SkyLee发现了两个空的展示架可以放游戏

SkyLee给摆放有游戏的那个展示架编号1,空的编号2和3。
假设SkyLee拿游戏、放游戏和试玩游戏都需要时间,现在由你来帮SkyLee提出一个最快的把所有游戏都试玩完的方案吧。

在同样快的试玩方案中,SkyLee会第一时间试玩他拿到的新游戏,然后尽量把字典序更小的游戏放在编号大的展示架上。

2. 输入

  1. 多组数据
  2. 每组数据1个数n,表示游戏的数量。1≤n≤10

3. 输出

对于每组数据,输出把所有游戏都试玩完的最快方案,按以下要求: 拿出游戏输出一行get game from board i,其中i是展示架的编号。 放回游戏输出一行put game to board i,其中i是展示架的编号。 试玩游戏输出一行playing。 离开商场输出一行leave。

4. 解题思路

虽然题目比较怪异,但是本质上还是一个Hanoi问题,只不过有一点点的变形。

对于Hanoi 问题,很显然需要用递归来写,首先我们来考虑一下基本情况:

  1. 如果只有一个游戏,那么显然 1-> 3
  2. 如果有两个游戏,那么根据题目意思,字典序小的要放到标号大的上面,所以在外面的要先放到2号位置,即1->2,1->3;
  3. 如果超过两个,要在最快的情况下要完成试玩,先将n-2个移到2号位置,第n-1个移到3号,第n个放回本身位置

这题要注意一下,并不需要所以的游戏放到一个位置,所以

  1. 放回本身的位置是合法的
  2. 两个的时候也是特殊情况,因为可以分开放

时间复杂度为

5. 题解代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<iostream>
using namespace std;
void move(char from, char to){
printf("get game from board %c\n", from);
printf("playing\n");
printf("put game to board %c\n", to);
}
void moves(char from, char to){
printf("get game from board %c\n", from);
printf("put game to board %c\n", to);
}
void hanoi2(int n, char from, char depend, char to){
if (n == 1)
moves(from, to);
else{
hanoi2(n - 1, from, to, depend);
moves(from, to);
hanoi2(n - 1, depend, from, to);
}
}
void hanoi(int n, char from, char depend, char to){
if (n == 1)
move(from, to);
else{
hanoi(n - 1, from, to, depend);
move(from, to);
hanoi2(n - 1, depend, from, to);
}
}
int main(){
char a = '1', b = '2', c = '3';
int n;
while (cin >> n){
if (n > 2){
hanoi(n - 2, a, c, b);
move(a, c);
move(a, a);
printf("leave\n");
}
else if (n == 2){
move(a, b);
move(a, c);
printf("leave\n");
}
else{
move(a, c);
printf("leave\n");
}
}
}

H .序列优美差值


1. 题目描述

给定一个序列a,询问满足i<j且 L≤a[j]−a[i]≤R的点对(i,j)数量

2. 输入

  1. 第一个数为数据组数T,每组数据两行。
  2. 第一行为整数n, L, R,表示序列长度,L,R;
  3. 接下来一行为空格分隔的n个整数。
  4. T≤10 . n≤1e6

3. 输出

对于每组数据,输出一行,点对的数量

4. 解题思路

对于求数组中前后元素关系的题,通常而言我们有两种方法:

  1. 暴力求解。既然是比大小,那我们只要一个二重循环,将整个数组遍历一遍,记录满足条件的值即可。时间复杂度为

  2. 分治法。利用归并排序,在排序的时候利用数组间已经有的大小关系,来算出我们需要的解。时间复杂度为

通常第一种情况比较好写算法,然而时间复杂度过高,所以我们不考虑。

我们来看看第二种算法:
考虑两个有序数组L,R,对于它们之间的答案,可分为三部分:

  1. L数组中满足条件的对数
  2. R数组中满足条件的对数
  3. L和R数组之间满足条件的对数

可以想到,对于1和2这两部分的答案,在归并的上一次二分时便可得出答案,那么,我们每一次便只需要考虑数组间的对数即可.

5.题解代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
typedef long long ll;
int n,l,r;
const int N= 1000010;
ll a[N],k[N],ans;
void Merge(int left,int right){
if(left >= right)
return ;
int mid = (left+right)/2;
Merge( left, mid);
Merge( mid+1, right);


int s = left,e = left;
for (int i = mid+1;i<=right;i++){
while(a[i] - a[e]>=l&&e<=mid)
++e;
while(a[i] - a[s]>r&&s<=mid)
++s;
ans += e - s;
}
int i = left,j = mid+1,p = left;
while(i<=mid&&j<=right)
k[p++] = a[i]<a[j]? a[i++]:a[j++];
while(i<=mid) k[p++] = a[i++];
while(j<=right) k[p++] = a[j++];
for (int i = left;i<=right;i++)
a[i] = k[i];
}
int main(){
int T;
scanf("%d",&T);
for (int i = 0;i<T;i++){
ans = 0;
scanf("%d %d %d",&n,&l,&r);
for (int j = 0;j<n;j++){
scanf("%lld",&a[j]);
}
Merge(0, n-1);
printf("%lld\n",ans);
}
return 0;
}
-------------The End-------------