Fork me on GitHub

第五周C++作业题解

希望能帮助那些卡题目的朋友们

by Acmclub:
汤畅绪 吴东小组等人。

申明

本次题解可能出的并不是非常的好,因为这周考试太多。招架不过来,那些题目我自己也有很多是直接暴力解决的。但还是吸取了组员以及acmclub其他成员的代码建议。比较简单的题目我会直接给大家放核心代码,因为这些题目看代码你就会觉得恍然大悟。希望轻喷,求体谅。。。。如果有问题大家在NEUQ OJ交流群上提问就行了,群里的成员都会为你们解决的,大家都很热心的。

分了2个板块,一个是小组讨论觉得比较水的题目,还有一个就是有点难度的题目。

水题

1012: SZ斐波拉契数列

比较水的一个题目。利用函数写一个递归或者循环一个递推都是可以解决的。

核心代码(递推)

1
2
3
4
5
6
7
8
9
int F(int a,int b,int n){
if(n==1) return a;
if(n==2) return b;
if(n>2)
{
if(n%2==0) return F(a,b,n-1)+F(a,b,n-2)+F(a,b,n-3);
else return F(a,b,n-1)+F(a,b,n-2);
}
}

递归的话直接在主函数里面写就行了。

1318: 兔子问题

题目描述:
有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔

子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数

为多少?

输入:
n

输出:
兔子的总队数

样例输入

1
3

样例输出

1
2

同样递归或者递推来解决。
上面那个题目用的递归解决,这个题目上递推吧。

核心代码(递推)

1
2
3
4
for(int i=3;i<=n;i++)
{
s[i]=s[i-1]+s[i-2];
}

n为1,2另外讨论行了,一个循环就可以解决。

1319: 角谷定理

题目描述:
输入一个自然数,若为偶数,则把他除以2,若为奇数,则把它乘以3加1,经过如此有限次运算后,总可以得到自然数值1.求经过多少次可得到自然数1

样例输入

1
22

样例输出

1
16

题(hu)目(luan)分析

一个循环,循环条件不为1,然后对n分奇数偶数的情况进行讨论。然后每循环一次用一个数来进行计数就行了。
题目比较水,不上代码了。

1156: 求具有abcd=(ab+cd)2性质的四位数

描述
题目描述:
3025这个数具有一种独特的性质:将它平分为二段,即30和25,使之相加后求平方,即(30+25)2,恰好等于3025本身。请求出具有这样性质的全部四位数

满足题意的数全部四位数(从小到大输出,且数之间用两个空格分开)

代码讲解&&题目分析

1
2
3
4
5
6
for(int i=1000;i<=9999;i++)
{
int a=i/100,b=i-a*100;//a表示4位数前2位,b表示后2位。
if((a+b)*(a+b)==i)
cout<<i<<" ";
}

题目要求是要找出其中有关的四位数,那我们直接遍历所有的4位数,不用担心会出现超时等问题,因为复杂度是O(n)。找出里面符合题目要求的既可了。

1509: 汉诺塔

描述
题目描述:
汉诺塔是由三根杆子A,B,C组成的。A杆上有N个穿孔圆盘,盘的尺寸由下到上依次变小,编号从1到n。要求按下列规则将所有圆盘移至C杆:每次只能移动一个圆盘;大盘不能叠在小盘上面。提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须尊循上述两条规则。问:如何移?

输入:
一个整数N(N<=10),表示圆盘的个数

输出:
移动盘子的过程,每一步一行,格式为“要移动的盘子所在的柱子编号—要移动到得柱子的编号”

样例输入

1
2

样例输出

1
2
3
A---B
A---C
B---C

题解and代码。

比较经典的递归入门问题。
递归分三步进行:

第一步将A上面除了最大的那个环,其他环借助由A借助于C环全放到B环上。

第二步就是直接将最大的环从A移向C。

第三步是把剩余其他的环从B上移动到C的上面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
using namespace std;
void hhh(int n,char A,char B,char C)
{
if(n==1)
{
cout<<A<<"---"<<C<<endl;
return;
}
hhh(n-1,A,C,B);//第一步
cout<<A<<"---"<<C<<endl;//第二步
hhh(n-1,B,A,C);//第三步
return;
}
int main()
{
int n;
while(cin>>n)
{
hhh(n,'A','B','C');
}
return 0;
}

1185: 【明明的随机数】

描述
题目描述:
明明想在学校中请一些同学一起做一项问卷调查,为了实验的客观性,他先用 计算机生成了N个1到1000之间的随机整数(N≤100),对于其中重复的数字,只保留一个,把其余相同的数去掉,不同的数对应着不同的学生的学号。然 后再把这些数从小到大排序,按照排好的顺序去找同学做调查。请你协助明明完成“去重”与“排序”的工作。

输入:
有2行,第1行为1个正整数,表示所生成的随机数的个数:
N
第2行有N个用空格隔开的正整数,为所产生的随机数。

输出:
也是2行,第1行为1个正整数M,表示不相同的随机数的个数。第2行为M个用空格隔开的正整数,为从小到大排好序的不相同的随机数。

样例输入

1
2
10
20 40 32 67 40 20 89 300 400 15

样例输出

1
2
8
15 20 32 40 67 89 300 400

题目分2个步骤完成。
第一步:排序。
第二步:去重。

1.排序如果用sort完成,去掉重复的元素,可以考虑在输出的时候先输出第一个数组的元素。然后后面循环输出的时候写循环条件和前一个不相同的可以输出。
2.如果用数组进行的是桶排序,对每个元素都进行标记,把那些标记过的元素输出就可以去重了。
可能大家没听过桶排,直接用核心代码解释吧,其实你们可能还用过,只是名称不懂而已。
非常注意的是这个题目的格式,要知道最后一个数字后面是没有空格的。

桶排代码

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
for(int i=1;i<=1000;i++)
{
a[i]=0;
}
for(int i=1;i<=n;i++)
{
cin>>x;
a[x]=1;
}
for(int j=1;j<=1000;j++)
{
if(a[j]==1)
{
m++;
}
}
cout<<m<<endl;
int c=0;
for(int j=1;j<=1000;j++)
{
if(a[j]==1)
{
cout<<j;
c++;
}
if(c!=m)
{
cout<<" ";
}

非水题

1410: 屌丝的逆袭

描述
题目描述:
毕业于普通本科的小Q一直自称是资深屌丝,不仅学校不知名,甚至他自己在这个普通学校也是默默无闻——直到临近毕业的时候,班里5朵金花中的2位甚至从没和他说过话!
  谁又能想到,如此不起眼的小Q在历经重重面试环节后,竟然如愿以偿加入了心仪已久的腾讯公司!消息刚刚传开的那几天,这在他们班甚至整个学院都是讨论的热门话题,如果这时候你还表示不知道小Q是谁,你都会被大家当作怪物的。
  正所谓野百合也有春天,屌丝也有逆袭的那一天!
  
  刚到腾讯大厦上班的那几天,小Q眼中的一切都是那么新鲜,连每天见到的前台MM在他眼中都胖的那么可爱。小Q就这样在紧张与兴奋的情绪中度过了一天又一天,每天即勤奋认真又小心翼翼,很希望能给主管留下个好印象,以免失去这来之不易的工作机会。
  一段时间以后,随着对工作环境以及同事的熟悉,小Q逐渐放松下来,在工作间隙,他细细观察了自己的工作环境,发现整个工作室是一个N行M列的矩形布局,或者是因为屌丝的本性逐步暴露,他还暗自给每个同事在心里进行了魅力值评分(为区别男女,男生一律用负整数表示,女生一律用正整数表示)。
  现在,小Q把所有人的数据记录下来,并且这样定义一个位置的价值:
  1、一个位置的价值只和其上下左右四个邻居的魅力值有关(对于靠边的位置,只考虑其存在的邻居);
  2、如果某位置的邻居和该位置主人性别不同,则总分加上邻居魅力值的绝对值,否则减去;
  3、对周围所有邻居的数据处理后,最终的得分即为这个位置的最终得分,得分越高,则该位置越好;

  现在你能帮助小Q计算一下哪里才是最佳位置吗?

输入:
输入包含多组测试数据;
每组测试数据的第一行包含2个整数N和M,表示工作室的布局是N行M列;
接下来的N行,每行有M个整数,分别表示对应位置员工的魅力值数据Ki,正整数表示女生的魅力值,负整数表示男生的魅力值;
N和M为0的时候表示输入数据结束。

[数据范围]
N<=20
M<=20
-100<=Ki<=100

输出:
请计算并输出最佳位置的行列号以及对应的得分,如果得分最高的位置有多个,则请输出行号最小的那个,行号还相同的话,再比较列号,只输出列号最小的那个即可。

样例输入

1
2
3
4
2 3
5 -4 3
-6 3 7
0 0

样例输出

1
1 2 11

题目分析&&代码实现。

这个题目其实很简单,类似于搜索里面的dfs,但是比搜索要简单,因为不用标记,只需要记录每个点所谓的魅力值就可以了。emmm代码实现里面讲解的比较清晰。

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
51
52
53
#include<iostream>
#include<cmath>
using namespace std;
int emm[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
//用一个二维数组,来规定搜索的方向,当然这里用2个一维数组也可以。搜索周围的4个点就可以了,不用太严格于从哪个方向开始搜索。
int m,n,map[25][25];
int fen(int a,int b)
{
int ans=0,i;
for(i=0;i<4;i++)
{
int tx=a+emm[i][0];
int ty=b+emm[i][1];//相当于找这个点的上下左右的各个人的魅力值。
if(tx<1||ty<1||tx>n||ty>m)
continue;//判断查找的点是否越界,如果越界进行下一次循环,进入下一次查找。
if(map[a][b]*map[tx][ty]<0)
ans+=abs(map[tx][ty]); //2个人魅力值是负的就绝对值相加。
else
ans-=abs(map[tx][ty]); //是正的就相减。
}
return ans;
}
int main()
{
int i,j,max,x,y,score[25][25];
while(cin>>n>>m,n,m)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
cin>>map[i][j];
}
}
max=-9999999;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
score[i][j]=fen(i,j); //从最开始的那个点开始进行搜索。
if(score[i][j]>max)
{
max=score[i][j]; //用max来记录。
x=i,y=j;
}
else if(score[i][j]==max)
{
continue;//如果后面找到的值与之相等,不管,直接跳过。
}
}
cout<<x<<" "<<y<<" "<<max<<endl;
}
return 0;
}

这题也就那样吧。逃)。

1018: A+B again

描述
题目描述:
谷学长有一个非常简单的问题给你,给你两个整数A和B,你的任务是计算A+B。

输入:
输入的第一行包含一个整数T(T<=20)表示测试实例的个数,然后2*T行,分别表示A和B两个正整数。注意整数非常大,那意味着你不能用32位整数来处理。你可以确定的是整数的长度不超过1000。

输出:
对于每一个样例,你应该输出两行,第一行是”Case #:”,#表示第几个样例,第二行是一个等式”A+B=Sum”,Sum表示A+B的结果。注意等式中有空格。

样例输入

1
2
3
4
5
2
1
2
112233445566778899
998877665544332211

样例输出

1
2
3
4
Case 1:
1 + 2 = 3
Case 2:
112233445566778899 + 998877665544332211 = 1111111111111111110

高精度模版&&题目分析。

注意事项:高精度加法计算,注意每个加法位置要对整齐。然后同时要注意题目条件把数组开大一点。当然0+0的值也是要有结果的。
这个题目当然要用字符来储存数据,毕竟int,longlong,unsigned longlong太小了。然后转换成每个位置的计算。

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
51
52
53
54
55
56
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int a[1500],b[1500],c[1501],lena,lenb,lenc,i,j,x,k;
void add(char *a1,char *b1)
{
char temp[10000];
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
lena=strlen(a1);
lenb=strlen(b1);
for(i=0;i<lena;i++)
{
a[lena-i]=a1[i]-48;
}
for(i=0;i<lenb;i++)
{
b[lenb-i]=b1[i]-48;
}
lenc=1;
x=0;
while(lenc<=lena||lenc<=lenb)//这里进行各个位置上的计算。
{
c[lenc]=a[lenc]+b[lenc]+x;
x=c[lenc]/10;
c[lenc]%=10;
lenc++;
}
c[lenc]=x;
if(c[lenc]==0)
{
lenc--;
}
for(i=lenc;i>=1;i--)
{
cout<<c[i];
}
cout<<endl;
}
int main()
{
char a1[1500],b1[1500];
int n;cin>>n;
for(int z=1;z<=n;z++)
{
cin>>a1>>b1;
cout<<"Case "<<z<<":"<<endl;
cout<<a1<<" + "<<b1<<" = ";
add(a1,b1);
}
return 0;
}

1321: 苹果的密码

描述
题目描述:
yyf得到了苹果,十分高兴,又怕苹果被偷吃,就果断的给装了一个安全系统,并且要给每一个苹果设立了一个有效的密码,一个有效的密码由L(3<=L<=15)(来自传统的拉丁字母集’a’…’z’)组成,至少有一个元音(‘a’, ‘e’, ‘i’, ‘o’, 或者’u’),至少两个辅音(除去元音以外的音节),并且有按字母表顺序出现的字母(例如,’abc’是有效的,而’bac’不是) .给定一个期望长度L和C个小写字母,写一个程序,打印出所有的长度为L、能由这些字母组成的有效密码。密码必须按字母表顺序打印出来,一行一个。

输入:
第一行:两个由空格分开的整数,L和C
第二行: C个小写字母,密码是由这个字母集中的字母来构建的。

输出:
每一个输出行包括一个长度为L个字符的密码(每个 之后一个空格)。输出行必须按照字母顺序排列。

样例输入

1
2
4 6
atcisw

样例输出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
acis
acit
aciw
acst
acsw
actw
aist
aisw
aitw
astw
cist
cisw
citw
istw

说实话,这个题目我a的比较血腥,300多行代码直接把L从3-15的所有情况讨论了一波(
毕竟这个题目数据比较弱)。然而仔细研究一波,发现这就是个简单的深度搜索题目。。。

题目分析

题目分析写在代码注释上面希望大家不要介意,写的很详细了。

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 <cstdio>
int l,c;
bool b[26];//标记数组
char m[15];//密码
void dfs(int n,int j)
{
int i,sum;
int K[26]={0};
if(n==l)//密码是否达到题目要求长度
{
for(i=0;i<l;i++)
{
K[m[i]]++;//统计密码里面每个出现的小写字母的个数
}
sum=K[0]+K[4]+K[8]+K[14]+K[20];//统计小写元音字母个数
if(sum>=1&&l-sum>=2)//判断条件 元音字母个数大于等于1 且 辅音字母大于等于2
{
for(i=0;i<l;i++)
{
printf("%c",m[i]+'a');//输出字母使加97
}
printf(" \n");//每次输出一个有效密码,根据题意应该还要输出一个空格!并且换行。
}
return;
}
for(i=j;i<26;i++)//保证字母顺序
{
if(b[i]!=0)
{
m[n]=i;
b[i]=false;
dfs(n+1,i);
b[i]=true;//搜完后还原标记,以便后面的字母使用现在这个字母
}
}
return;
}
int main()
{
char a;
scanf("%d%d",&l,&c);//输入两个数字
getchar();//此处注意换行符'\n'也是一个字符,会影响到下面输入的字母,因此用getchar()消化掉
for(int i=0;i<c;i++)
{
scanf("%c",&a);
b[a-'a']=true;//标记出现过的字母,也可以写成b[a-97]=1;ASCLL上的小写字母是从97开始的,为了使b[0]对应a,此处应该减去一个'a'的值97;
}
dfs(0,0);//从零开始,保证密码字母顺序
return 0;
}

1415: F4ck Me

描述
题目描述:
好无聊啊~

谁来 AC 我啊~

输入:
每行输入一个句子,你只需要统计每个小写字母出现的次数,每个字符串至多长100000 . 输入结束为文件结尾(EOF)

注意,直接使用cin可能会超时哦!

输出:
对于每行数据,输出每个字母出现次数,格式为: X:N

每组数据后输出一个空行。

样例输入

1
2
hello, this is my first acm contest!
work hard for neuq acm.

样例输出

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
51
52
53
a:1
b:0
c:2
d:0
e:2
f:1
g:0
h:2
i:3
j:0
k:0
l:2
m:2
n:1
o:2
p:0
q:0
r:1
s:4
t:4
u:0
v:0
w:0
x:0
y:1
z:0
a:2
b:0
c:1
d:1
e:1
f:1
g:0
h:1
i:0
j:0
k:1
l:0
m:1
n:1
o:2
p:0
q:1
r:3
s:0
t:0
u:1
v:0
w:1
x:0
y:0
z:0

一个额外的知识点

这个题目题目提示我们组并没有用,但还是给大家介绍一波。
在C++里面cin和cout是速度在计算那些大数据的时候比较容易卡时间然后tle的,而C语言的scanf和printf则不会出现这种情况,那这种情况怎么办呢?
不用担心,这里介绍2个猛男函数,可以使cin和cout的速度加快。

1
2
3
4
ios::syne_with_stdio(false);
//放在cin后面,关闭和stdio同步,使速度和scanf一样快
cin.tie(0);
//放在cout后面,输出速度一样加快。

回归题目。

题目就比较简单了,单纯的统计小写字母而已,利用ascll值进行循环统计即可。输入字符用gets函数就可以了
代码如下:

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<cstring>
int main()
{
char s[100000];
while(gets(s)!=NULL)//读入一串字符,注意此处不能用scanf("%s",s)因为sanf遇到空格停止输入,应该注意
{
int num[26]={0};
for(int i=0;i<strlen(s);i++)
{
//统计字母个数
for(int j=0;j<26;j++)
{
if(s[i] ==(j+97))
{
num[j] ++;
break;
}
}
}
for(int i=0;i<26;i++)
printf("%c:%d\n",i+97,num[i]);
printf("\n");
}
return 0;
}

总结

好了,到这里题解已经结束了,讲的并不是很详细。但无奈时间和精力都不是很充足,如果还有疑问建议在OJ群里面进行交流即可。
非常感谢观看。明天还要考CAD实际操作。逃)
By Acmclub 吴东

-------------本文结束感谢您的阅读-------------