Scott's world.

蓝桥杯 基础练习(下)

Word count: 6.3kReading time: 28 min
2020/03/21 Share

蓝桥杯 基础练习(下)

BASIC-20 数的读法

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  Tom教授正在给研究生讲授一门关于基因的课程,有一件事情让他颇为头疼:一条染色体上有成千上万个碱基对,它们从0开始编号,到几百万,几千万,甚至上亿。
  比如说,在对学生讲解第1234567009号位置上的碱基时,光看着数字是很难准确的念出来的。
  所以,他迫切地需要一个系统,然后当他输入12 3456 7009时,会给出相应的念法:
  十二亿三千四百五十六万七千零九
  用汉语拼音表示为
  shi er yi san qian si bai wu shi liu wan qi qian ling jiu
  这样他只需要照着念就可以了。
  你的任务是帮他设计这样一个系统:给定一个阿拉伯数字串,你帮他按照中文读写的规范转为汉语拼音字串,相邻的两个音节用一个空格符格开。
  注意必须严格按照规范,比如说“10010”读作“yi wan ling yi shi”而不是“yi wan ling shi”,“100000”读作“shi wan”而不是“yi shi wan”,“2000”读作“er qian”而不是“liang qian”。

  • 输入格式

  有一个数字串,数值大小不超过2,000,000,000。

  • 输出格式

  是一个由小写英文字母,逗号和空格组成的字符串,表示该数的英文读法。

  • 样例输入

1234567009

  • 样例输出

shi er yi san qian si bai wu shi liu wan qi qian ling jiu

分析

这道题无关于算法,根据题意描述出题目

代码

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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
string num[10] = {"ling ", "yi ", "er ", "san ", "si ", "wu ", "liu ","qi ", "ba ", "jiu "};
string numWei(string x)
{
string result="";
int len=x.size();
if(len>=4){
result+=num[x[0]-'0'];
result+="qian ";
}
if(len>=3){
if(x[len-3]!='0'){
result+=num[x[len-3]-'0'];
result+="bai ";
}
}
if(len>=2){
if(x[len-2]=='1'){
if(len!=2){
result+="yi shi ";
}else{
result+="shi ";
}
}
if(x[len-2]!='1'&&x[len-2]!='0'){
result+=num[x[len-2]-'0'];
result+="shi ";
}
}
if(len>=1){
if(x[len-1]!='0'){
result+=num[x[len-1]-'0'];
}
}
return result;
}

int main()
{
int Size;
int flag;
string input;
string temp;
cin>>input;
Size=input.size();
if(Size>=9){
temp=input.substr(0,Size-8);
cout<<numWei(temp)<<"yi ";
}
temp="";
flag=0;
if(Size>=5){
for(int i=Size-8;i<Size-4;i++){
if(i<0 ||(flag==0 && input[i]=='0'))continue;
temp+=input[i];
flag=1;
}
if(flag){
cout<<numWei(temp)<<"wan ";
}
temp="";
flag=0;
for(int i=Size-4;i<Size;i++){
if(flag==0&&input[i]=='0')continue;
if(input[i-1]=='0'){
cout<<"ling ";
}

temp+=input[i];
flag=1;
}
cout<<numWei(temp);
}
if(Size<=4){
cout<<numWei(input);
}
return 0;
}

BASIC-21 Sine之舞

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  最近FJ为他的奶牛们开设了数学分析课,FJ知道若要学好这门课,必须有一个好的三角函数基本功。所以他准备和奶牛们做一个“Sine之舞”的游戏,寓教于乐,提高奶牛们的计算能力。
  不妨设
  An=sin(1–sin(2+sin(3–sin(4+…sin(n))…)
  Sn=(…(A1+n)A2+n-1)A3+…+2)An+1
  FJ想让奶牛们计算Sn的值,请你帮助FJ打印出Sn的完整表达式,以方便奶牛们做题。

  • 输入格式

  仅有一个数:N<201。

  • 输出格式

  请输出相应的表达式Sn,以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

  • 样例输入

3

  • 样例输出

((sin(1)+3)sin(1–sin(2))+2)sin(1–sin(2+sin(3)))+1

分析

根据题意可以很清晰地看出,这道题是考察递推方面

我们先求An,递推出An的每一种情况,然后再通过Sn的递推规律求出Sn

代码

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
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;

string AN[201];

void An(int n){
AN[0]="sin(1";
for(int i=1;i<n;i++){
AN[i]=AN[i-1];
if(i%2==0){
AN[i]+="+";
}else{
AN[i]+="-";
}
AN[i]+="sin(";
AN[i]+=(char)(i+'1');
}
for(int i=0;i<n;i++){
for(int j=0;j<=i;j++){
AN[i]+=")";
}
}
}

int main()
{
int n;
string result="";
cin>>n;
An(n);
for(int i=2;i<=n;i++){
result+="(";
}
for(int i=n-1;i>=1;i--){
result+=AN[n-1-i];
result+="+";
result+=char(i+'1');
result+=")";
}
result+=AN[n-1];
result+="+1";
cout<<result;

return 0;
}

BASIC-22 FJ的字符串

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  FJ在沙盘上写了这样一些字符串:
  A1 = “A”
  A2 = “ABA”
  A3 = “ABACABA”
  A4 = “ABACABADABACABA”
  … …
  你能找出其中的规律并写所有的数列AN吗?

  • 输入格式

  仅有一个数:N ≤ 26。

  • 输出格式

  请输出相应的字符串AN,以一个换行符结束。输出中不得含有多余的空格或换行、回车符。

  • 样例输入

3

  • 样例输出

ABACABA

分析

这道题很明显可以看出一道考察递归的题目

递归公式也很容易看出即An=A(n-1)+n+A(n-1);

代码

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
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;

string A[27];

void An(int n){
if(n==1){
A[n]="A";
return;
}
An(n-1);
A[n]+=A[n-1];
A[n]+=char(n-1+'A');
A[n]+=A[n-1];

}

int main()
{
int n;
cin>>n;
An(n);
cout<<A[n]<<endl;
return 0;
}

BASIC-23 芯片测试

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  有n(2≤n≤20)块芯片,有好有坏,已知好芯片比坏芯片多。
  每个芯片都能用来测试其他芯片。用好芯片测试其他芯片时,能正确给出被测试芯片是好还是坏。而用坏芯片测试其他芯片时,会随机给出好或是坏的测试结果(即此结果与被测试芯片实际的好坏无关)。
  给出所有芯片的测试结果,问哪些芯片是好芯片。

  • 输入格式

  输入数据第一行为一个整数n,表示芯片个数。
  第二行到第n+1行为n*n的一张表,每行n个数据。表中的每个数据为0或1,在这n行中的第i行第j列(1≤i, j≤n)的数据表示用第i块芯片测试第j块芯片时得到的测试结果,1表示好,0表示坏,i=j时一律为1(并不表示该芯片对本身的测试结果。芯片不能对本身进行测试)。

  • 输出格式

  按从小到大的顺序输出所有好芯片的编号

  • 样例输入

3
1 0 1
0 1 0
1 0 1

  • 样例输出

1 3

分析

这道题是考察二维数组的题目,只要把题意理解,这道题难度就不大了

题目中提到好芯片总是大于坏芯片,好芯片的测试结果都一致,即二维数组中测试结果一致的行数总是大于不一致的行数

代码

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
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;

int A[21][21];

string B[21];

int main()
{
int n;
int Max=0;
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>A[i][j];
B[i]+=char(A[i][j]+'0');
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(B[i]==B[j]){
A[i][0]++;
}
}
if(A[i][0]>Max){
Max=A[i][0];
}
}
for(int i=1;i<=n;i++){
if(A[i][0]==Max){
cout<<i<<" ";
}
}
cout<<endl;

return 0;
}

BASIC-24 龟兔赛跑预测

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  话说这个世界上有各种各样的兔子和乌龟,但是研究发现,所有的兔子和乌龟都有一个共同的特点——喜欢赛跑。于是世界上各个角落都不断在发生着乌龟和兔子的比赛,小华对此很感兴趣,于是决定研究不同兔子和乌龟的赛跑。他发现,兔子虽然跑比乌龟快,但它们有众所周知的毛病——骄傲且懒惰,于是在与乌龟的比赛中,一旦任一秒结束后兔子发现自己领先t米或以上,它们就会停下来休息s秒。对于不同的兔子,t,s的数值是不同的,但是所有的乌龟却是一致——它们不到终点决不停止。
  然而有些比赛相当漫长,全程观看会耗费大量时间,而小华发现只要在每场比赛开始后记录下兔子和乌龟的数据——兔子的速度v1(表示每秒兔子能跑v1米),乌龟的速度v2,以及兔子对应的t,s值,以及赛道的长度l——就能预测出比赛的结果。但是小华很懒,不想通过手工计算推测出比赛的结果,于是他找到了你——清华大学计算机系的高才生——请求帮助,请你写一个程序,对于输入的一场比赛的数据v1,v2,t,s,l,预测该场比赛的结果。

  • 输入格式

  输入只有一行,包含用空格隔开的五个正整数v1,v2,t,s,l,其中(v1,v2<=100;t<=300;s<=10;l<=10000且为v1,v2的公倍数)

  • 输出格式

  输出包含两行,第一行输出比赛结果——一个大写字母“T”或“R”或“D”,分别表示乌龟获胜,兔子获胜,或者两者同时到达终点。
  第二行输出一个正整数,表示获胜者(或者双方同时)到达终点所耗费的时间(秒数)。

  • 样例输入

10 5 5 2 20

  • 样例输出

D
4

  • 样例输入

10 5 5 1 20

  • 样例输出

R
3

  • 样例输入

10 5 5 3 20

  • 样例输出

T
4

分析

这道题在一开始很容易陷入找寻规律的想法中,但实际上只要考虑将时间划分为每过一秒的情况,题目就会好解很多

代码

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
#include <iostream>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;

int main()
{
int v1,v2,t,s,l;
cin>>v1>>v2>>t>>s>>l;
int ontime=0,len1=0,len2=0,breaktime=0,flag=0;
while(len1<l&&len2<l){
if(flag==0&&len1-len2<t||flag==1&&breaktime>=s){
breaktime=0;
flag=0;
len1+=v1;
}else{
flag=1;
breaktime++;
}
len2+=v2;
ontime++;
}
if(len1>=l && len2<l){
cout<<"R"<<endl;
}else if(len1<l&&len2>=l){
cout<<"T"<<endl;
}else{
cout<<"D"<<endl;
}
cout<<ontime<<endl;


return 0;
}

BASIC-25 回形取数

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  回形取数就是沿矩阵的边取数,若当前方向上无数可取或已经取过,则左转90度。一开始位于矩阵左上角,方向向下。

  • 输入格式

  输入第一行是两个不超过200的正整数m, n,表示矩阵的行和列。接下来m行每行n个整数,表示这个矩阵。

  • 输出格式

  输出只有一行,共mn个数,为输入矩阵回形取数得到的结果。数之间用一个空格分隔,行末不要有多余的空格。

  • 样例输入

3 3
1 2 3
4 5 6
7 8 9

  • 样例输出

1 4 7 8 9 6 3 2 5

  • 样例输入

3 2
1 2
3 4
5 6

  • 样例输出

1 3 5 6 4 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <iostream>
#include <memory.h>
using namespace std;
int a[201][201];
int main() {
int m, n;
cin >> m >> n;
memset(a, -1, sizeof(a));
int i = 0, j = 0;
for(i = 0; i < m; i++)
for(j = 0; j < n; j++)
cin >> a[i][j];
i = 0, j = 0;
int total = 0;
while(total < m * n) {
while(i <= m-1 && a[i][j] != -1) {
cout << a[i][j] << " ";
a[i][j] = -1;
i++;
total++;
}
i--;
j++;
while(j <= n-1 && a[i][j] != -1) {
cout << a[i][j] << " ";
a[i][j] = -1;
j++;
total++;
}
j--;
i--;
while(i >= 0 && a[i][j] != -1) {
cout << a[i][j] << " ";
a[i][j] = -1;
i--;
total++;
}
i++;
j--;
while(j >= 0 && a[i][j] != -1) {
cout << a[i][j] << " ";
a[i][j] = -1;
j--;
total++;
}
j++;
i++;
}
return 0;
}

BASIC-26 报时助手

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  给定当前的时间,请用英文的读法将它读出来。
  时间用时h和分m表示,在英文的读法中,读一个时间的方法是:
  如果m为0,则将时读出来,然后加上“o’clock”,如3:00读作“three o’clock”。
  如果m不为0,则将时读出来,然后将分读出来,如5:30读作“five thirty”。
  时和分的读法使用的是英文数字的读法,其中0~20读作:
  0:zero, 1: one, 2:two, 3:three, 4:four, 5:five, 6:six, 7:seven, 8:eight, 9:nine, 10:ten, 11:eleven, 12:twelve, 13:thirteen, 14:fourteen, 15:fifteen, 16:sixteen, 17:seventeen, 18:eighteen, 19:nineteen, 20:twenty。
  30读作thirty,40读作forty,50读作fifty。
  对于大于20小于60的数字,首先读整十的数,然后再加上个位数。如31首先读30再加1的读法,读作“thirty one”。
  按上面的规则21:54读作“twenty one fifty four”,9:07读作“nine seven”,0:15读作“zero fifteen”。

  • 输入格式

  输入包含两个非负整数h和m,表示时间的时和分。非零的数字前没有前导0。h小于24,m小于60。

  • 输出格式

  输出时间时刻的英文。

  • 样例输入

0 15

  • 样例输出

zero fifteen

分析

这道题与前面的用中文表达数字的题思路是一致的,这里就不详述了

代码

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 <iostream>
#include <memory.h>
using namespace std;
string timeFlag[24] = {"zero", "one", "two", "three", "four", "five", "six", "seven", "eight", "nine", "ten", "eleven", "twelve", "thirteen",
"fourteen", "fifteen", "sixteen", "seventeen", "eighteen", "nineteen", "twenty", "twenty one", "twenty two", "twenty three"};
string reTimeFlag[6] = {"","","twenty","thirty","forty","fifty"};
int main() {
int h,m,t;
cin >> h >> m;
cout<<timeFlag[h]<<" ";
if(m == 0){
cout<<"o'clock";
}
t=m%10;
m/=10;
if(m==0&&t!=0){
cout<<timeFlag[t];
}
if(m==1){
cout<<timeFlag[t+10];
}
if(m!=0&&m!=1&&t!=0){
cout<<reTimeFlag[m]<<" "<<timeFlag[t]<<endl;
}

return 0;
}

BASIC-27 2n皇后问题

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  给定一个n*n的棋盘,棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后,使任意的两个黑皇后都不在同一行、同一列或同一条对角线上,任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法?n小于等于8。

  • 输入格式

  输入的第一行为一个整数n,表示棋盘的大小。
  接下来n行,每行n个0或1的整数,如果一个整数为1,表示对应的位置可以放皇后,如果一个整数为0,表示对应的位置不可以放皇后。

  • 输出格式

  输出一个整数,表示总共有多少种放法。

  • 样例输入

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

  • 样例输出

2

  • 样例输入

4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1

  • 样例输出

0

分析

这道很显然是涉及到皇后问题,只不过这里这里是多出来一个皇后即2n皇后问题

皇后问题的常规解法就是通过深度优先搜索算法

这里需要注意到,由于多出来一个皇后,所以在第一个皇后搜索完毕后,要将棋盘的信息复制给另一个皇后,包括第一个皇后的摆放位置,然后另一个皇后再进行一次深度优先搜索,

当另一个皇后找到了符合的放法后,便使result+1,最后输出result

代码

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 <iostream>
#include <math.h>
#include <vector>
using namespace std;

int result=0;

bool isSafe(vector<int>pos,int row){
for(int i=0;i<row;i++){
if( pos[i] == pos[row] || abs(i-row)== abs(pos[i]-pos[row])){
return false;
}
}
return true;
}

void reDfs(vector<vector<int> > reCb,vector<int> rePos,int n,int reRow){
if(reRow==n){
result++;
return;
}
for(rePos[reRow]=0;rePos[reRow]<n;rePos[reRow]++){
if(reCb[reRow][rePos[reRow]] == 1 && isSafe(rePos,reRow)){
reDfs(reCb,rePos,n,reRow+1);
}
}
}


void dfs(vector<vector<int> > cb,vector<int> pos,int n,int row){
if(row==n){
vector<vector<int> > reCb(n, vector<int>(n));
vector<int> rePos(n);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)reCb[i][j]=cb[i][j];
for(int i=0;i<n;i++)reCb[i][pos[i]]=0;
reDfs(reCb,rePos,n,0);
return;
}
for(pos[row]=0;pos[row]<n;pos[row]++){
if(cb[row][pos[row]] == 1 && isSafe(pos,row)){
dfs(cb,pos,n,row+1);
}
}
}

int main()
{
int n;
cin>>n;
vector<vector<int> > cb(n, vector<int>(n));
vector<int> pos(n);
for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>cb[i][j];
dfs(cb,pos,n,0);
cout<<result;
return 0;
}

BASIC-28 Huffuman树

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。
  给出一列数{pi}={p0, p1, …, pn-1},用这列数构造Huffman树的过程如下:

  1. 找到{pi}中最小的两个数,设为pa和pb,将pa和pb从{pi}中删除掉,然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
  2. 重复步骤1,直到{pi}中只剩下一个数。
  在上面的操作过程中,把所有的费用相加,就得到了构造Huffman树的总费用。
  本题任务:对于给定的一个数列,现在请你求出用该数列构造Huffman树的总费用。

  例如,对于数列{pi}={5, 3, 8, 2, 9},Huffman树的构造过程如下:
  1. 找到{5, 3, 8, 2, 9}中最小的两个数,分别是2和3,从{pi}中删除它们并将和5加入,得到{5, 8, 9, 5},费用为5。
  2. 找到{5, 8, 9, 5}中最小的两个数,分别是5和5,从{pi}中删除它们并将和10加入,得到{8, 9, 10},费用为10。
  3. 找到{8, 9, 10}中最小的两个数,分别是8和9,从{pi}中删除它们并将和17加入,得到{10, 17},费用为17。
  4. 找到{10, 17}中最小的两个数,分别是10和17,从{pi}中删除它们并将和27加入,得到{27},费用为27。
  5. 现在,数列中只剩下一个数27,构造过程结束,总费用为5+10+17+27=59。

  • 输入格式

  输入的第一行包含一个正整数nn<=100)。
  接下来是n个正整数,表示p0, p1, …, pn-1,每个数不超过1000。

  • 输出格式

  输出用这些数构造Huffman树的总费用。

  • 样例输入

5
5 3 8 2 9

  • 样例输出

59

分析

这道题比较简单,仅涉及到huffman的构建过程

可以利用排序得到最小位

也可以利用最小堆得到最小位

代码

  • 利用排序

    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
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;

    int cmp(int a,int b){
    return a > b;
    }


    int main()
    {
    int n;
    int result=0;
    cin>>n;
    vector<int> huffman;
    for(int i=0;i<n;i++)
    {
    int temp;
    cin>>temp;
    huffman.push_back(temp);
    }
    int size = huffman.size();
    while(size>=2){
    sort(huffman.begin(),huffman.end(),cmp);
    int t = huffman[size-1] + huffman[size-2];
    result+=t;
    huffman.pop_back();
    huffman.pop_back();
    huffman.push_back(t);
    size = huffman.size();
    }
    cout<<result;
    return 0;
    }
  • 利用最小堆

    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
    #include <iostream>
    #include <algorithm>
    #include <vector>
    using namespace std;

    int cmp(int a,int b){
    return a > b;
    }


    int main()
    {
    int n;
    int result=0;
    cin>>n;
    vector<int> huffman;
    for(int i=0;i<n;i++)
    {
    int temp;
    cin>>temp;
    huffman.push_back(temp);
    }

    make_heap(huffman.begin(),huffman.end(),greater<int>());
    int size = huffman.size();
    while(size>=2){
    pop_heap(huffman.begin(),huffman.end(),greater<int>());
    int num1=huffman.back();
    huffman.pop_back();
    pop_heap(huffman.begin(),huffman.end(),greater<int>());
    int num2=huffman.back();
    huffman.pop_back();
    int t = num1 + num2;
    result+=t;
    huffman.push_back(t);
    push_heap(huffman.begin(),huffman.end(),greater<int>());
    size = huffman.size();
    }
    cout<<result;
    return 0;
    }

BASIC-29 高精度加法

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  输入两个整数ab,输出这两个整数的和。ab都不超过100位。

  • 算法描述

  由于ab都比较大,所以不能直接使用语言中的标准数据类型来存储。对于这种问题,一般使用数组来处理。
  定义一个数组AA[0]用于存储a的个位,A[1]用于存储a的十位,依此类推。同样可以用一个数组B来存储b
  计算c = a + b的时候,首先将A[0]与B[0]相加,如果有进位产生,则把进位(即和的十位数)存入r,把和的个位数存入C[0],即C[0]等于(A[0]+B[0])%10。然后计算A[1]与B[1]相加,这时还应将低位进上来的值r也加起来,即C[1]应该是A[1]、B[1]和r三个数的和.如果又有进位产生,则仍可将新的进位存入到r中,和的个位存到C[1]中。依此类推,即可求出C的所有位。
  最后将C输出即可。

  • 输入格式

  输入包括两行,第一行为一个非负整数a,第二行为一个非负整数b。两个整数都不超过100位,两数的最高位都不是0。

  • 输出格式

  输出一行,表示a + b的值。

  • 样例输入

20100122201001221234567890
2010012220100122

  • 样例输出

20100122203011233454668012

分析

比较典型的大数相加问题

可以根据字符串也可以根据数组来解决,这里我用的是字符串

代码

  • 字符串
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main()
{
string a;
string b;
string c="";
cin>>a;
cin>>b;
int sizeA=a.size();
int sizeB=b.size();
int sizeMin=sizeA;
if(sizeA>=sizeB){
sizeMin=sizeB;
}
int up=0,down;
int num1,num2,sum;
for(int i=0;i<sizeMin;i++){
num1=a[sizeA-i-1]-'0';
num2=b[sizeB-i-1]-'0';
sum=num1+num2+up;
if(sum>9){
down=sum%10;
up=sum/10;
}else{
down=sum;
up=0;
}
c+=char(down+'0');
}
if(sizeA-sizeMin-1>=0){
for(int i=sizeA-sizeMin-1;i>=0;i--){
num1=a[i]-'0';
sum=num1+up;
if(sum>9){
down=sum%10;
up=sum/10;
}else{
down=sum;
up=0;
}
c+=char(down+'0');
}
if(up!=0){
c+=char(up+'0');
}
}
else if(sizeB-sizeMin-1>=0){
for(int i=sizeB-sizeMin-1;i>=0;i--){
num1=b[i]-'0';
sum=num1+up;
if(sum>9){
down=sum%10;
up=sum/10;
}else{
down=sum;
up=0;
}
c+=char(down+'0');
}
if(up!=0){
c+=char(up+'0');
}
}
else{
if(up!=0){
c+=char(up+'0');
}
}
string result="";

for(int i=c.size()-1;i>=0;i--){
result+=c[i];
}

cout<<result<<endl;

return 0;
}

BASIC-30 阶乘计算

  • 资源限制

时间限制:1.0s 内存限制:512.0MB

  • 问题描述

  输入一个正整数n,输出n!的值。
  其中n!=123…**n

  • 算法描述

  n!可能很大,而计算机能表示的整数范围有限,需要使用高精度计算的方法。使用一个数组A来表示一个大整数aA[0]表示a的个位,A[1]表示a的十位,依次类推。
  将a乘以一个整数k变为将数组A的每一个元素都乘以k,请注意处理相应的进位。
  首先将a设为1,然后乘2,乘3,当乘到n时,即得到了n!的值。

  • 输入格式

  输入包含一个正整数nn<=1000。

  • 输出格式

  输出n!的准确值。

  • 样例输入

10

  • 样例输出

3628800

分析

同样是大数运算的问题,即高精度问题,利用数组来解决比较容易

代码

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
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
int n;
cin>>n;
int A[10000]={1};
for(int i=1;i<=n;i++){
for(int j=0;j<10000;j++){
A[j] = A[j] * i;
}
for(int j=0;j<10000;j++){
if(A[j] >= 9){
A[j+1] = A[j+1] + A[j]/10;
A[j] = A[j] % 10;
}
}
}
int size = 0;
for(int i=9999;i>=0;i--){
if(A[i]!=0){
size = i;
break;
}
}
for(int i=size;i>=0;i--){
cout<<A[i];
}
return 0;
}
CATALOG
  1. 1. 蓝桥杯 基础练习(下)
    1. 1.1. BASIC-20 数的读法
      1. 1.1.1. 分析
      2. 1.1.2. 代码
    2. 1.2. BASIC-21 Sine之舞
      1. 1.2.1. 分析
      2. 1.2.2. 代码
    3. 1.3. BASIC-22 FJ的字符串
      1. 1.3.1. 分析
      2. 1.3.2. 代码
    4. 1.4. BASIC-23 芯片测试
      1. 1.4.1. 分析
      2. 1.4.2. 代码
    5. 1.5. BASIC-24 龟兔赛跑预测
      1. 1.5.1. 分析
      2. 1.5.2. 代码
    6. 1.6. BASIC-25 回形取数
      1. 1.6.1. 分析
      2. 1.6.2. 代码
    7. 1.7. BASIC-26 报时助手
      1. 1.7.1. 分析
      2. 1.7.2. 代码
    8. 1.8. BASIC-27 2n皇后问题
      1. 1.8.1. 分析
      2. 1.8.2. 代码
    9. 1.9. BASIC-28 Huffuman树
      1. 1.9.1. 分析
      2. 1.9.2. 代码
    10. 1.10. BASIC-29 高精度加法
      1. 1.10.1. 分析
      2. 1.10.2. 代码
    11. 1.11. BASIC-30 阶乘计算
      1. 1.11.1. 分析
      2. 1.11.2. 代码