2024-01-23竞赛笔记

2024/1/23

【初一算法基础】高精度

P2437 蜜蜂路线

//P2437
//看了一下题解才知道可以用递归c 
#include<iostream>
using namespace std;
int f[10005][20010];//处理每个方格 
int m,n;
int len=1;//计数器计算总和位数 
void did(int k){//k指阶数
	int isBigten=0;//处理进位 
	for (int i=1;i<=len;i++) //开始高精度加法
	{
		f[k][i]=f[k-1][i]+f[k-2][i]+isBigten;//递推(只是多了一个加进位) 
		isBigten=f[k][i]/10;//获取进位值
		f[k][i]%=10;//得到进位后获取当前位的值
	}
	if(isBigten>0) //最后一位可能会进位
	{
		len++;//位数+1 
		f[k][len]+=isBigten;//进位加入总和 
	}
}
signed main() {
	cin>>m>>n;
	f[0][1]=0;
	f[1][1]=1;
	f[2][1]=1;//递推边界 
	for(int i=2;i<=n-m+1;i++)//循环n-m+1次（因为i=2） 
	{
		did(i);//一个个方格（阶数）开始递推 
	}
	for (int i=len;i>=1;i--)
	{
		cout<<f[n-m+1][i];//输出结果 
	}
	
}

---

P1601 A+B高精

//P1601 A+B高精
#include<bits/stdc++.h>
using namespace std;
int a[600],b[600],c[600],k1,k2,k3,maxn;//处理位数和存储 
string a1,b1;//存储两个加数
signed main()
{
	cin>>a1>>b1;
	for(int i=a1.size()-1;i>=0;i--)//字符串a1转到数组a存储 
	{
		a[++k1]=a1[i]-'0';//把高位放在数组的最后 
	}
	for(int i=b1.size()-1;i>=0;i--)//字符串b1转到数组b存储 
	{
		b[++k2]=b1[i]-'0';//把高位放在数组的最后 
	}
	maxn=max(k1,k2);//最大数的数位 
	k3=maxn+1;//初始化结果的数位 
	for(int i=1;i<=maxn;i++)
	{
		c[i]=a[i]+b[i];
	}	
	for(int i=1;i<=maxn+1;i++)//处理加法进位 
	{
		if(c[i]>=10)//如果有进位 
		{
			c[i+1]+=c[i]/10;//加上进位值 
			c[i]%=10;//得到进位后当前位的值 
		}
	}
	while(c[k3]==0)
		k3--;//慢慢消掉结果的位数 
	for(int i=max(k3,1);i>=1;i--)
		printf("%d",c[i]);//输出 
}

---

P2142 高精度减法

//P2142 高精度减法
#include<bits/stdc++.h>
using namespace std;
int a[100000]={0},b[100000]={0},c[100000]={0};//初始化数组 
int i,j,k,l,m,n,flag;
string a1,b1,c1;//存储被减数，减数和差 
void did(){
    int i=0;
    while(i<=a[0]){
        i++;
        if(a[i]<b[i]){//被减数比减数小 
            a[i+1]--;//前一位-- 
			a[i]+=10;//当前数位++ 
        }
        c[i]=a[i]-b[i];//相应数值相减 
        c[0]++;//位数++
    }
}
int main(){
    cin>>a1>>b1;
    a[0]=a1.length();//取长度 
    b[0]=b1.length();
    if(a[0]<b[0] || (a[0]==b[0] && a1<b1)){//比较大小，如果被减数小于减数就交换 
        c1=b1;b1=a1;a1=c1;
        swap(a[0],b[0]);//交换两数的位数 
        cout<<"-";//因为交换了，输出“-”
    }
    for(i=1;i<=a[0];i++) {//字符串a1转到数组a存储
    	a[i]=a1[a[0]-i]-'0';//最高位放到末尾 
	}
    for(i=1;i<=b[0];i++){//字符串b1转到数组b存储
	    b[i]=b1[b[0]-i]-'0';//最高位放到末尾 
	}
    did();//减法运算 
    while(c[c[0]]==0&&c[0]>1) c[0]--;//判断0是否有用,因为使用 “c[0]>1”减会减多，从而使c[0]=0
    for(i=c[0];i>=1;i--) {
	    cout<<c[i];//倒序输出
	}
    return 0;
}

---

高精度乘法

//P1303
#include<iostream>
#include<cstring>
using namespace std;
char a1[2000],b1[2000];
int a[20005]={0},b[20005]={0},c[40010]={0};//保存数子的数组 
int main()
{
	int la,lb,lc=0;
	cin>>a1>>b1;
	la=strlen(a1);//取位数 
	lb=strlen(b1);
	for(int i=0;i<=la;i++)//a1保存到数组a 
	{
		a[la-i]=a1[i]-'0';//最高为防末尾 
	}
	for(int i=0;i<lb;i++)//b1保存到数组b
	{
		b[lb-i]=b1[i]-'0';//最高为防末尾 
	}		
	for(int i=1;i<=la;i++)
	{
		for(int j=1;j<=lb;j++)
		{
			c[i+j-1]=a[i]*b[j]+c[i+j-1];
			if(c[i+j-1]>=10)//如果有进位 
			{
				c[i+j]+=c[i+j-1]/10;//加上进位的值 
				c[i+j-1]=c[i+j-1]%10;//更新当前位的值 
			}
		}
	}	
	lc=la+lb;//加 
	while(c[lc]==0 && lc>1)//毁灭积的位数 
	{
		lc--;
	}
	for(int i=lc;i>=1;i--)
	{
		cout<<c[i];//输出 
	}
	return 0;
}	

---

P1009 阶乘之和

#include <bits/stdc++.h>
using namespace std;
int n,a[1000],b[1000],len;//保存阶乘过程中的数字数组 
void jiechenghe()
{
	int x=0;//进位 
	for(int i=0; i<1000; i++)
	{
		b[i]=b[i]+a[i]+x;//加上所有阶乘并处理进位 
		x=b[i]/10;//取进位 
		b[i]%=10;//得到进位后获取当前位的值
	}
}
void jiecheng(int y)
{
	int x=0;//进位 
	for(int i=0; i<1000; i++){
		a[i]=a[i]*y+x;//阶乘 
		x=a[i]/10;//取进位 
		a[i]%=10;//得到进位后获取当前位的值
	}
}

signed main(){
	cin>>n;
	a[0]=1;//1!为1 
	for(int i=1;i<=n;i++){//阶乘解决 
		jiecheng(i);//每一步都计算并相加 
		jiechenghe();
	}
	len=1000;//一个定值，为去掉0做准备 
	while(b[len]==0){
		len--;//去掉多余的0 
	}	
	for(int i=len;i>=0;i--)
		cout<<b[i];//逆向输出 
	return 0;
}