【算法】模拟，高精度-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法】模拟，高精度。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

高精度加法

【算法】模拟，高精度

P1601 A+B Problem（高精） - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路就是模拟，值得注意的就是要用字符串类型输入。存进自己的int数组时要倒着存，因为如果是正着存的话，进位会有点trouble。

时间复杂度O（max(m,n))

【算法】模拟，高精度

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int a[N],b[N],c[N];
signed main()
{
	string A,B;
	cin>>A>>B;
	int len=max(A.length(),B.length());
	for(int i=A.length()-1,j=1;i>=0;i--,j++)
	{
		a[j]=A[i]-'0';//倒着存 
	}
	for(int i=B.length()-1,j=1;i>=0;i--,j++)
	{
		b[j]=B[i]-'0';//倒着存 
	}
	for(int i=1;i<=len;i++)
	{
		c[i]+=a[i]+b[i];
		c[i+1]=c[i]/10;
		c[i]%=10;	
	} 
	if(c[len+1]) len++;
	for(int i=len;i>=1;--i) cout<<c[i];
	return 0;
}

高精度乘法

【算法】模拟，高精度

P1303 A*B Problem - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<bits/stdc++.h>
using namespace std;
const int N=5010;
int a[N],b[N],c[N];
signed main()
{
	string A,B;
	cin>>A>>B;
	int lena=A.length(),lenb=B.length();
	int len=lena+lenb;
	for(int i=lena-1,j=1;i>=0;j++,i--)
	{
		a[j]=A[i]-'0';
	}
	for(int i=lenb-1,j=1;i>=0;j++,i--)
	{
		b[j]=B[i]-'0';
	}
	for(int i=1;i<=lena;i++)
	{
		for(int j=1;j<=lenb;j++)
		{
			c[i+j-1]+=a[i]*b[j];
		}
	}
	for(int i=1;i<=len;i++)
	{
		c[i+1]+=c[i]/10;
		c[i]%=10;
	}
	while(!c[len]) len--;
	for(int i=max(1,len);i>=1;i--) cout<<c[i];
	//注意0,0的情况 ,要输出一个0 
	return 0;
}

模拟习题

阶乘之和

P1009 [NOIP1998 普及组] 阶乘之和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

copy的题解，主要是高精的乘法和加法。要注意细节问题。

#include<bits/stdc++.h>
using namespace std;
signed main()
{
    int n,j,i,A[1005]={0},B[1005]={0};
    cin>>n;
    A[1]=B[1]=1;
    for(i=2;i<=n;i++)
	{
        for(j=1;j<100;j++)
        {
            B[j]*=i;//每一项都乘上i 
        }    
        for(j=1;j<100;j++)//对每一项进行讨论 
        {
            B[j+1]+=B[j]/10;//进位 
            B[j]%=10;
        }    
        for(j=1;j<100;j++)
		{
            A[j]+=B[j];
            A[j+1]+=A[j]/10;
            A[j]%=10;
        }
    }
    for(i=100;i>=0&&A[i]==0;i--);
    for(j=i;j>=1;j--) printf("%d", A[j]);
    return 0;
}

魔法少女小Scarlet

P4924 [1007]魔法少女小Scarlet - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

矩阵顺时针，逆时针旋转。

细节巨多，很恼人的一个题目！！（蒟蒻发言）

主要问题在于矩阵旋转带来的数值改变，要找关系。这里也是看到了题解的一个很聪明的做法，把（x，y）看成坐标原点，再对其讨论。在题解里也看到很多佬写题都是用函数，感觉结构会很清晰，

【算法】模拟，高精度

(太久没写博客了，图片怎么转都没转过来就这样吧，摆烂.jpg)

这里也要注意，转完之后（j,-i)=原来的(i,j)，不要小脑写反了，保持清醒！！

#include<bits/stdc++.h>
using namespace std;
const int N=600;
int n,m;
int g[N][N],t[N][N];

signed main()
{
	cin>>n>>m;
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			g[i][j]=(i-1)*n+j;
		}
	}
	while(m--)
	{
		int x,y,r,z;//z=0 表示顺时针，z=1 表示逆时针
		cin>>x>>y>>r>>z;
		memset(t,0,sizeof(t));
		for(int i=x-r;i<=x+r;i++)
		{
			for(int j=y-r;j<=y+r;j++)
			{
				t[i][j]=g[i][j];
			}
		} 
		if(z==0)
		{
			for(int i=-r;i<=r;i++)
			{
				for(int j=-r;j<=r;j++)
				{ 	
					g[x+j][y-i]=t[x+i][y+j];
				}
			}
		}
		if(z==1)
		{
			for(int i=-r;i<=r;i++)
			{
				for(int j=-r;j<=r;j++)
				{
					g[x-j][y+i]=t[x+i][y+j];
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout<<g[i][j]<<" ";
		}
		cout<<endl;
	} 

	return 0;
}

生活大爆炸版石头剪刀布

（生活大爆炸好耶。高中疫情在家那会可爱边吃饭边看了，偏题bushi）

P1328 [NOIP2014 提高组] 生活大爆炸版石头剪刀布 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

纯打表，有点无脑其实。。。。注意细节就好，没有思维难度。

#include<bits/stdc++.h>
using namespace std;
const int N=600;
int n,na,nb;
int a[N],b[N];
int cnta,cntb;
signed main()
{
	cin>>n>>na>>nb;
	for(int i=0;i<na;i++) cin>>a[i];
	for(int i=0;i<nb;i++) cin>>b[i]; 
	
	for(int i=0;i<n;i++)
	{
		if(a[i%na]==0)
		{
			if(b[i%nb]==2||b[i%nb]==3) cnta++;
			else if(b[i%nb]==0) continue;
			else cntb++;
		}
		if(a[i%na]==1)
		{
			if(b[i%nb]==3||b[i%nb]==0) cnta++;
			else if(b[i%nb]==1) continue;
			else cntb++;
		}
		if(a[i%na]==2)
		{
			if(b[i%nb]==1||b[i%nb]==4) cnta++;
			else if(b[i%nb]==2) continue;
			else cntb++;
		}
		if(a[i%na]==3)
		{
			if(b[i%nb]==4||b[i%nb]==2) cnta++;
			else if(b[i%nb]==3) continue;
			else cntb++;
		}
		if(a[i%na]==4)
		{
			if(b[i%nb]==0||b[i%nb]==1) cnta++;
			else if(b[i%nb]==4) continue;
			else cntb++;
		}
	}
	cout<<cnta<<" "<<cntb;
	return 0;
}

两只塔姆沃斯牛

P1518 [USACO2.4]两只塔姆沃斯牛 The Tamworth Two - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

是一个模拟，没想象中难，自我感觉很对但输出不对看了好久，结果是方向向量有问题。

要注意在这种二维数组里坐标要这样画

【算法】模拟，高精度

#include<bits/stdc++.h>
using namespace std;
const int N=600;
char g[15][15];
int tox[]= {-1, 0, 1, 0};//方向 
int toy[]={0, 1, 0, -1};
typedef pair<int,int> PII;
PII niu,ren; 
signed main()
{//能往前就往前，否则掉头，每分钟动一次 
	memset(g,'*',sizeof(g));
	int n=10;
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>g[i][j];
			if(g[i][j]=='C') niu.first=i,niu.second=j;
			if(g[i][j]=='F') ren.first=i,ren.second=j;
		}
	} 
	//牛的路是固定的 	
	int nn=0,nr=0;//记录朝向，初始都为北 
	for(int i=1;i<=100000;i++)//时间，分钟 
	{
		int a=niu.first+tox[nn%4];
		int b=niu.second+toy[nn%4];
		if(g[a][b]=='*'||a<1||a>10||b<1||b>10)
		{
			/*a=niu.first;
			b=niu.second;*///如果前面是障碍物，则不走 
			nn++;
		}else{
			niu.first=a;//可以走，更新点的坐标 
			niu.second=b;
		}
		
		int c=ren.first+tox[nr%4];
		int d=ren.second+toy[nr%4];
		if(g[c][d]=='*'||c<1||c>10||d<1||d>10)
		{
			/*c=ren.first;
			d=ren.second;*///如果前面是障碍物，则不走 
			nr++;
		}else{
			ren.first=c;
			ren.second=d;
		}
		if(niu.first==ren.first&&niu.second==ren.second)
		{
			cout<<i;
			return 0;
		}
	}
	cout<<"0";
	return 0;
}