基础算法——模拟

2022.6.18

这种题想要做对，与要靠技巧和题感，它是没有模板和基础思路的。

一、简介：

模拟就是用计算机来模拟题目中要求的操作。

模拟题目通常具有码量大、操作多、思路繁复的特点。由于它代码量大，经常会出现难以查错的情况，如果在考试中写错是相当浪费时间的。

二、技巧：

1、写代码时，要在草稿纸上理清思路，简单写一下代码，不要妄想想一下思路就出来了。

2、因为模拟题代码都很长，而且重复的代码也很多，要多写几个函数（有时侯函数也会写的很多，所以一定要清楚每个函数的作用，搞乱了就又要在再推一遍代码）。

3、对于一些可能重复用到的概念，可以统一转化，方便处理。

4、写代码的时候一定要思路清晰，不要想到什么写什么，要按照落在纸上的步骤写。

三、真题演练：

因为模拟没有基础思路和模板，所以要多刷题锻炼题感。

1、洛谷 P1014 [NOIP1999 普及组] Cantor 表：
题目描述：

现代数学的著名证明之一是 Georg Cantor 证明了有理数是可枚举的。他是用下面这一张表来证明这一命题的：

我们以 Z 字形给上表的每一项编号。第一项是 1/1，然后是 1/2，2/1，3/1，2/2，…

输入格式：

整数N，

输出格式：

表中的第 N 项。

输入样例：

输出样例：

1/4

思路：

我们可以把他们分成几组（分子和分母的和相同为一组）：

分子和分母的和为偶数，以分子大为开头；为奇数，以分母大为开头；

若分母+分子=k，则这样的分数有（k-1）个。

代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int n,k,l,r,op;
signed main(){
	cin >>n;
	for(int i=1;i*(i+1)/2 
 
2、oiclass #P1118. 身份证： 
题目描述： 
        身份证号码是由十七位数字本体码和一位校验码组成。排列顺序从左到右依次为：六位数字“地址码”、八位数字“出生日期码”、三位数字“顺序码”和一位数字“校验码”。
         “地址码”用来表示公民常住户口所在地区的行政区划代码。
         “出生日期码”表示公民的出生年、月、日。
         “顺序码”表示在同一“地址码”所表示的区域范围内，对同年、同月、同日出生的人编定的顺序号，顺序码的奇数分配给男性，偶数分配给女性。 

         “校验码”是根据前面十七位数字计算得到，计算方法为：
         第$1$步：将前面的身份证号码$17$位数分别乘以不同的系数。从第$1$位到第$17$位的系数分别为：7、9、10、5、8、4、2、1、6、3、7、9、10、5、8、4、2；
         第$2$步：将这17位数字和系数相乘的结果相加；
         第$3$步：用加出来的和除以11，得到余数；
         第$4$步：余数只可能有0、1、2、3、4、5、6、7、8、9、10这11个数字，其分别对应的校验码为1、0、X(注意是大写)、9、8、7、6、5、4、3、2；也就是说如果上面得到的余数为2，那校验码就是X，如果余数为10，那校验码就是2。
         现在你只记得自己身份证上的前$17$位，你能否不用回家拿身份证就可以知道最后一位是多少？ 
输入格式： 
输入只有一行，由17个数字组成，表示身份证号码的前17位，数字和数字之间用空格隔开。 
输出格式： 
输出该身份证的最后一位校验码。 
输入样例： 
4 4 2 0 0 0 1 9 9 6 0 1 0 1 0 2 3
 
输出样例： 
4 
思路： 
开三个数组进行计算。
代码：
   
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int a[20],b[20]={0,7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2},sum=0;
char c[20]={'1','0','X','9','8','7','6','5','4','3','2'}; 
signed main(){
	for(int i=1;i<=17;i++){
		cin >>a[i];
		sum+=(a[i]*b[i]);
	}
	cout < 
 
3、洛谷 P1532 卡布列克圆舞曲  
题目描述： 
卡布列克是一位数学家，他在研究数字时发现：任意一个不是用完全相同数字组成的四位数，如果对它们的每位数字重新排序，组成一个较大的数和一个较小的数，然后用较大数减去较小数，差不够四位数时补零，类推下去，最后将变成一个固定的数：61746174，这就是卡布列克常数，例如： 
4321-1234=3087 
8730-378=8352 
8532-2358=6174 
7641-1467=6174 
如果 K 位数也照此办理，它们不是变成一个数，而是在几个数字之间形成循环，称作卡布列克圆舞曲。例如对于五位数 54321： 
54321-12345=41976 
97641-14679=82962 
98622-22689=75933 
97533-33579=63954 
96543-34569=61974 
97641-14679=829629 
我们把 82962,75933,63954,61974 称作循环节，即卡布列克圆舞曲。 
输出格式： 
若干行，每行为一个待求“卡布列克圆舞曲”的起始整数 n。 
输入格式：
 每行为对应整数的循环节，数据之间用空格隔开。 
输入样例： 
4321
54321 
输出样例： 
6174
82962 75933 63954 61974 
思路： 
用函数枚举每一个数，装入数组，再写一个函数寻找是否出现过。 
代码： 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int n,a[20],q[N],len,t,k;
void move(int n){
	memset(a,0,sizeof(a));
	int p=0;
	while(n>=1){
		a[++p]=(n%10);
		n/=10;
	} 
	sort(a+1,a+1+p);
	int x=0,y=0;
	for(int i=1;i<=p;i++){
		x*=10;
		x+=a[i];
	}
	for(int i=p;i>=1;i--){
		y*=10;
		y+=a[i];
	}
	t=y-x;
}
int find(int t){
	for(int i=1;i<=len;i++){
		if(q[i]==t)return i;
	}
	return 0;
}
signed main(){
	while(cin >>n){
		memset(q,0,sizeof(q));
		len=0;
		move(n); 
		q[++len]=n;
		k=find(t);
		while(!k){
			q[++len]=t;
			move(t);
			k=find(t);
		}
		for(int i=k;i 
 
4、oiclass P2704. 2048 
题目描述： 
此时，Conan却在一旁玩着2048。 
这是一个4∗4的矩阵，初始全为0。每次一个没有数字的格子中会随机出现一个2或4，每次可以选择上下左右其中一个方向去滑动，每滑动一次，所有的数字方块都会往滑动的方向靠拢外，相同数字的方块在靠拢、相撞时会相加。 
Conan想看看今天自己运气咋样，于是就闭着眼睛，在屏幕上随便滑来滑去。所以这个模拟的任务就交给你了。过了一会，他然后睁开眼睛，如果游戏没有结束（滑动后如果没有空格子，则游戏结束），请输出矩阵（格式参见样例），否则输出“Game over!”（不包含引号）。 
输入样例：
 输入第一行包含一个整数N，表示Conan滑了几下。
 接下来N 行，x，y，v，f表示第x行与第y列出现数字为v后，Conan滑的方向为f（f为字符，U; D; L; R分别表示向上下左右滑）。
 行从上往下1-4标号，列从左往右1-4标号。
 数据保证在游戏未结束时，只会在空白区域出现数字。 
输出格式：
 输出按题目描述。 
输入样例： 
8
1 3 4 L
2 3 2 U
2 4 2 R
4 1 2 L
3 4 2 L
3 2 2 D
1 3 4 R
1 3 2 U
 
输出格式： 
0 0 2 8
0 0 0 2
0 0 0 8
0 0 0 0
 
思路： 
用函数来枚举上下左右的移动。 
代码： 
#include 
#include 
#include 
using namespace std;
int a[6][6],n,x,y,v;
char f;
bool flag[5][5],check; 
void Up(){
	for(int i=1;i<=4;i++){
	  	int t=1;
	  	for(int j=1;j<=4;j++){
		   	if(a[j][i]!=0){
			    swap(a[t][i],a[j][i]);
			    if(a[t][i]==a[t-1][i]&&flag[t-1][i]==0){
			     	flag[t-1][i]=1;
			     	a[t-1][i]*=2;
			     	a[t][i]=0;
			     	t--;
			    }
			    t++; 
			}
	  	}
 	}
 	if(a[4][1]&&a[4][2]&&a[4][3]&&a[4][4])check=1;
}
void Down(){
 	for(int i=1;i<=4;i++){
	  	int t=4;
	  	for(int j=4;j>=1;j--){
		   	if(a[j][i]!=0){
			    swap(a[j][i],a[t][i]);
			    if(a[t][i]==a[t+1][i]&&flag[t+1][i]==0){
			     	flag[t+1][i]=1;
			     	a[t+1][i]*=2;
			     	a[t][i]=0;
			     	t++;
			    }
			    t--;
		   	}
	  	}
 	}
 	if(a[1][1]&&a[1][2]&&a[1][3]&&a[1][4])check=1;
}
void Left(){
 	for(int i=1;i<=4;i++){
	  	int t=1;
	  	for(int j=1;j<=4;j++){
		   	if(a[i][j]!=0){
			    swap(a[i][j],a[i][t]);
			    if(a[i][t-1]==a[i][t]&&flag[i][t-1]==0){
			     	flag[i][t-1]=1;
			     	a[i][t-1]*=2;
			     	a[i][t]=0;
			     	t--;
			    }
			    t++;
		   	} 
	  	} 
 	}
 	if(a[1][4]&&a[2][4]&&a[3][4]&&a[4][4])check=1;
}
void Right(){
 	for(int i=1;i<=4;i++){
	  	int t=4;
	  	for(int j=4;j>=1;j--){
		   	if(a[i][j]!=0){
		    swap(a[i][j],a[i][t]);
		    if(a[i][t]==a[i][t+1]&&flag[i][t+1]==0){
			    flag[i][t+1]=1;
			    a[i][t+1]*=2;
			    a[i][t]=0;
			    t++;
		    }
		    t--;
		   	}
	  	}
 	}
 	if(a[1][1]&&a[2][1]&&a[3][1]&&a[4][1])check=1;
}
int main(){
 	scanf("%d",&n);
 	for(int i=1;i<=n;i++){
	  	memset(flag,0,sizeof(flag));
	  	cin >>x>>y>>v>>f;
	  	a[x][y]=v;
	  	if(f=='U')Up();
	  	if(f=='D')Down();
	  	if(f=='L')Left();
	  	if(f=='R')Right();
	  	if(check){
		   	printf("Game over!");
		   	return 0;
	  	}
 	}
 	for(int i=1;i<=4;i++){
	  	for(int j=1;j<=4;j++)
	   		printf("%d ",a[i][j]);
	  	printf("n");
 	}
 	return 0;
}

基础算法——模拟

C/C++/C#相关栏目本月热门文章