蓝桥杯——练习（3.9）

蓝桥杯——练习（3.9）

基础练习 高精度加法

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T70

资源限制

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

问题描述

输入两个整数a和b，输出这两个整数的和。a和b都不超过100位。

算法描述

由于a和b都比较大，所以不能直接使用语言中的标准数据类型来存储。对于这种问题，一般使用数组来处理。
　　定义一个数组A，A[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

解题思路

• 由于数据量太大，用普通的数据类型存放不下，因此用数组来存放数据，开辟三个数组来解决问题。
• 从数组最后一位开始遍历，每一位减去‘0’就是每位对应的数，r存放进位，临时变量tmp存放对应位上的和，包含进位，然后让r存放tmp除以10的商，c数组存放tmp对10的余数。
• 当一个数组的数据已经处理完后，只对另外剩下的进行处理。
• 因为存放的时候是低位存放到0号位置，最后输出应从数组的最后一位开始遍历输出。

代码

#include<iostream>
#include<cstring>
using namespace std;
char   a[1111];
char   b[1111];
int    c[1111];
int main()
{
	cin>>a>>b;
	int i,j,k=0;
	int r=0;
	for(i=strlen(a)-1,j=strlen(b)-1;i>=0&&j>=0;i--,j--)
	{
		int tmp=(a[i]-'0')+(b[j]-'0')+r;
		r=tmp/10;
		c[k++]=tmp%10;
	}
	while(i>=0)
	{
		int tmp=(a[i]-'0')+r;
		r=tmp/10;
		c[k++]=tmp%10;
		i--;
	}
	while(j>=0)
	{
		int tmp=(b[j]-'0')+r;
		r=tmp/10;
		c[k++]=tmp%10;
		j--; 
	}
	if(r)
	{
		c[k++]=r;
	}
	for(int i=k-1;i>=0;i--)
	{
		cout<<c[i];
	}
	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

视频学习——深搜的剪枝策略视频讲解

视频链接：https://www.bilibili.com/video/BV1jE411g76D?p=17

学习心得

• 什么是剪枝？剪枝就是通过一些判断，去掉搜索树上不必要的子树。有些时候我们会发现某个节点对应的子树的状态并不是我们所需要的结果，因此我们没必要对这个分支进行搜索，去掉这个子树，就是剪枝。

• 可行性剪枝，就是把能够想到的它不可能出现的情况给它剪掉。

• 对求最优解的一类问题，通常可以用最优性剪枝，在求迷宫的最短路的时候，如果发现当前的步数已经超过了当前最优解，那从当前状态开始的搜索都是多余的，因为这样搜索下去永远都搜不到更优的解。通过剪枝，可以省去大量冗余的计算。

• 在搜索可行解的过程中，一旦找到一组可行解，后面所有的搜索都不必再进行了，这算是最优性剪枝的一个特例。

练习题目 2n皇后问题

题目链接：http://lx.lanqiao.cn/problem.page?gpid=T68

资源限制

时间限制：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

代码

#include<iostream>
#include<cmath>
using namespace std;
int n,i;
int a[10][10]={0};
int b[10]={0}; 
int c[10]={0};
int sum=0;
int white(int num)
{
	if(a[num][c[num]]==0)
		return 0;
	if(b[num]==c[num])
		return 0;
	int j;
	for(j=1;j<num;j++)
	{
		if(abs(c[j]-c[num])==abs(j-num)||c[j]==c[num])
			return 0;
	}
	return 1;
}
int put_white(int i)
{
	if(i>n)
	{
		sum++;
		return 0;
	}
	int j;
	for(j=1;j<=n;j++)
	{
		c[i]=j;
		if(white(i))
			put_white(i+1);
	}
	return 0;
}
int black(int num)
{
	if(a[num][b[num]]==0)
		return 0;
	int j;
	for(j=1;j<num;j++)
		if(abs(b[j]-b[num])==abs(j-num)||b[j]==b[num])
			return 0;
	return 1;
}
int put_black(int i)
{
	if(i>n)
	{
		put_white(1);
		return 0;
	}
	int j;
	for(j=1;j<=n;j++)
	{
		b[i]=j;
		if(black(i))
			put_black(i+1);
	}
	return 0;
}
int main()
{
	cin>>n;
	int j,k;
	for(j=1;j<=n;j++)
	{
		for(k=1;k<=n;k++)
		{
			cin>>a[j][k];
		}
	}
	put_black(1);
	cout<<sum<<endl;
	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
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