算法竞赛集训笔记（二）

高精度算法模版（自拟自用） int -2147483648～2147483647

加法，其实就是模拟竖式计算，但是cin的数其高位在数组小脚标位置，我们做加法应该从自然数低位开始加法，因此在string转换为int数组（也可以vector）时倒序填入，然后用一个新数组存放两个数组相加得到的结果，最后倒序输出这个新数组即可。。 

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<bits/stdc++.h>
using namespace std;
int main()
{
	string s1,s2;
	cin>>s1>>s2;
	int i,j=0,k=0;
	int a[510];int b[510];
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	int maxn=max(s1.size(),s2.size());
	for(i=s1.size()-1;i>=0;i--) a[j++]=s1[i]-'0';
	for(i=s2.size()-1;i>=0;i--) b[k++]=s2[i]-'0';	//赋值出整数数组
	//模拟竖式加法
	int c[511];
	int t=0;//存储上一位进位数;
	for(i=0;i<maxn;i++)
	{
		c[i]=(a[i]+b[i]+t)%10;
		t=(a[i]+b[i]+t)/10; 
	}
	if(t) 
	{
		c[i]=t;
		for(i=maxn;i>=0;i--) printf("%d",c[i]);
	}
	else
	{
		for(i=maxn-1;i>=0;i--) printf("%d",c[i]);
	}	
}
高精度乘法
一定要特判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
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s1,s2;
	cin>>s1>>s2;
	int i,j=0,k=0;
	int a[2001];int b[2001];
	memset(a,0,sizeof(a));
	memset(b,0,sizeof(b));
	for(i=s1.size()-1;i>=0;i--) a[j++]=s1[i]-'0';
	for(i=s2.size()-1;i>=0;i--) b[k++]=s2[i]-'0';	//赋值出整数数组
	//模拟竖式乘法 
	int c[5000];
	for(i=0;i<s1.size();i++)  
	{
		for(j=0;j<s2.size();j++)
		{
			c[i+j]+=a[i]*b[j];
		}
	}
	int t=0;//表示上一位进位 
	if(s1.size()==1&&a[0]==0||s2.size()==1&&b[0]==0) printf("0");
	else
	{
		for(i=0;i<s1.size()+s2.size()-1;i++)
	{
		int pc=c[i];
		c[i]=(c[i]+t)%10;
		t=(pc+t)/10; 
	}
	if(t)
	{
		c[i]=t;
		for(i=s1.size()+s2.size()-1;i>=0;i--) printf("%d",c[i]);
	}
	else
	{
		for(i=s1.size()+s2.size()-2;i>=0;i--) printf("%d",c[i]);
	}
	}
}
洛谷P1009 阶乘之和 
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
#include<bits/stdc++.h>
using namespace std;
int a[105];
int s[105];
void ch(int x)
{
	int t=0;
	int i,j;
	for(i=0;i<105;i++)
	{
		a[i]=a[i]*x+t;
		t=a[i]/10;
		a[i]=a[i]%10;
	}
}
void add()
{
	int t=0;
	int i;
	for(i=0;i<105;i++)
	{
		s[i]=s[i]+a[i]+t;
		t=s[i]/10;
		s[i]=s[i]%10;
	}
}
int main()
{
	memset(a,0,sizeof(a));
	memset(s,0,sizeof(s));
	a[0]=1;
	s[0]=0;
	int n;
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++)
	{
		ch(i);
		add();
	}
	int flag=104;
	while(s[flag]==0)
	{
		flag--;
	}	
	for(i=flag;i>=0;i--)
	{
		printf("%d",s[i]);
	}
	 
	
}
快速幂模版 求a的n次方 考虑a进制下的幂次方求法
1
2
3
4
5
6
7
8
9
10
11
12
int qpow(int a,int n)
{
	int ans=1;
	while(n)
	{
		if(n&1) ans=ans*a;
		a*=a;
		n>>=1;
	}
	return ans;
	
}
解释 用ans来存储最后的结果乘积。n&1即n与1按位与，用来判断二进制下n最后一位是否为1，如果是则当前的a需要乘到ans中。之后n右移移位，相当于更新了二进制下的n末位。 常涉及到取模运算，记忆一些好用的性质。
(A + B)modb = (Amodb + Bmodb)modb
(A * B)modb = ((Amodb) * (Bmodb))modb
均可以通过待定系数法证明 (设A = Ka * b + Ra)
高精度运算乘法加法用的相对较多。
高精度减法 
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
83
84
85
86
87
88
89
90
91
92
#include<bits/stdc++.h>
using namespace std;
int main()
{
	
	int a[10]={1,1,3,1,1,1,1,1,1,1};
	int b[10]={9,9,9,9,0,0,0,0,0,0};
	int i,j;
	int ans[10]={0};
	for(i=0;i<10;i++)
	{
		if(a[i]>=b[i]) ans[i]=a[i]-b[i];
		else 
		{
			a[i+1]--;
			a[i]=a[i]+10;
			ans[i]=a[i]-b[i];
		}
	}
	for(i=9;i>=0;i--) printf("%d",ans[i]);
}
```   

## 枚举的思考方式
情况较多开 long long

## 地图类题目处理思路
一个利用特征值处理的方法
```c++
#include<bits/stdc++.h>
using namespace std;
int dx[4]={-1,0,1,0}; 
int dy[4]={0,1,0,-1};
int fx,fy,cx,cy,ff=0,cf=0,t=0;
bool flag[160005];
int main()
{
	int i,j;
	char a[11][11];
	for(i=0;i<10;i++)
	{
		for(j=0;j<10;j++)         //制图 
		{
			scanf(" %c",&a[i][j]);
			if(a[i][j]=='F')
			{
				fx=i;fy=j; a[i][j]='.';
			}
			if(a[i][j]=='C')
			{
				cx=i;cy=j;a[i][j]='.';
			}
			
		}
		getchar();
	}
	while(1)
	{
		if(cx==fx&&cy==fy)
		{
			printf("%d",t);
			return 0;
		}
		int index=fx+fy*10+cx*100+cy*1000+ff*10000+cf*40000;
		
		
		if(flag[index])//如果出现过了，则无解
        {
            printf("0");
            return 0;
        }
        flag[index]=1;
		if(fx+dx[ff]>=0&&fx+dx[ff]<10&&fy+dy[ff]>=0&&fy+dy[ff]<10&&a[fx+dx[ff]][fy+dy[ff]]!='*')
		{
			fx=fx+dx[ff];fy=fy+dy[ff];
		}
		else
		{
			ff=(ff+1)%4;
		}
		if(cx+dx[cf]>=0&&cx+dx[cf]<10&&cy+dy[cf]>=0&&cy+dy[cf]<10&&a[cx+dx[cf]][cy+dy[cf]]!='*')
		{
			cx=cx+dx[cf];cy=cy+dy[cf];
		}
		else
		{
			cf=(cf+1)%4;
		}
		t++;
		
	}
}

DFS/BFS

关于搜索算法，先考虑深度优先搜索dfs，dfs的思路就是枚举各种可能，一条路走到黑，发现走不通就回溯，回到上一个节点继续枚举其他可能的路径。 

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
//上楼梯问题，每次可以走一阶或两阶或三阶，问走法。
#include<bits/stdc++.h>
using namespace std;
int n,a[100000],ans=0;
void dfs(int sum,int num)
{
	int i;
	if(sum==n)   //函数出口
	{
		
		for(i=0;i<num;i++) printf("%d ",a[i]);
		printf("走了%d步",num);
		printf("\n");
		ans++;
		return;
	}
	if(sum>n) return;
	for(i=1;i<=3;i++)
	{
		a[num]=i;          //用数组a存储某一次探路中节点是哪些
		dfs(sum+i,num+1);  //解决这样的子问题，在for循环内保证了所有节点的遍历
	}
}
int main()
{
	scanf("%d",&n);
	dfs(0,0);
	printf("一共有%d种走法",ans);
}
关于广度优先搜索bfs，其思路则是一层一层遍历，使用队列来存储正在遍历的该层节点，每次将q.front()元素的全部向下连接节点入队后，再令这个去q.front()出队（使用q.pop()),在while(!q.empty())的情况下不断遍历，直到队列为空，则遍历完成。 
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
/*有一个 n×m 的棋盘，在某个点 (x,y) 上有一个马，
要求你计算出马到达棋盘上任意一个点最少要走几步*/
#include<bits/stdc++.h>
using namespace std;
queue<int> qx,qy;
int a[401][401]={0},ans[401][401]={0};   a记录每一个节点是否已经遍历过
int dx[8]={-2,-2,2,2,1,-1,1,-1};
int dy[8]={-1,1,-1,1,2,-2,-2,2};
int main()
{
	int n,m,x,y;
	scanf("%d%d%d%d",&n,&m,&x,&y);
	qx.push(x);
	qy.push(y);
	ans[x][y]=0;a[x][y]=1;
	while(!qx.empty())
	{
        for(int i=0;i<8;i++)
        {
        	int tx=qx.front()+dx[i];
        	int ty=qy.front()+dy[i];
        	if(tx>0&&tx<=n&&ty>0&&ty<=m&&a[tx][ty]==0)
        	{
        		a[tx][ty]=1;  //使得树向下分叉，避免无限循环 
        		ans[tx][ty]=ans[qx.front()][qy.front()]+1;
        		qx.push(tx);
        		qy.push(ty);
			}
		}
		qx.pop();
		qy.pop();
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(ans[i][j]==0)
			{
				if(i!=x||j!=y) ans[i][j]=-1;
			}
			printf("%-5d",ans[i][j]);
		}
		printf("\n");
	}
	return 0;
	
}

算法 > 题目总结
#c++ #算法竞赛
算法竞赛集训笔记（二）
http://example.com/2024/07/26/算法/算法竞赛集训笔记（二）/
作者
bradin
发布于
2024年7月26日
许可协议