通过模拟解决问题

通过模拟解决问题，这里的“模拟”指的是编写程序时，让程序按照题目的描述方式执行得到最终的答案，也就是程序来模拟题目中描述的问题处理方法。正因为如此，模拟并不是一种真正意义上的算法。但是模拟的技巧是关注问题的细节，做到完整处理每个技术细节。而竞赛时，能够用模拟解决的题目，往往是送分题。

因为模拟不是一种具体的算法，所以这里主要通过几个例题供大家举一反三，可以使用模拟方法处理的题目往往描述内容较多，需要我们仔细阅读充分梳理处理环节，编程时需要特别注意细节的处理。

一、P2615 神奇的幻方

分析：直接模拟题目中的填数过程即可。因为填写数字\(K\)时，要对前一个数字\(K-1\)的填写位置进行判断来决定本次填写位置，所以可以使用两个变量\(x,y\)来记录填数过程中每个数填写的位置\((x,y)\)。

#include<iostream>
using namespace std;
int a[40][40];
int main(){
	int n,x,y;
	cin>>n;
	a[x=1][y=n/2+1] = 1;       //填写数字1
	for(int i=2;i<=n*n;i++){   //依次填写剩下的数字
		if(x==1 && y!=n) a[x=n][++y] = i;
		else if(x!=1 && y==n) a[--x][y=1] = i;
		else if(x==1 && y==n) a[++x][y] = i;
		else if(!a[x-1][y+1]) a[--x][++y] = i;
		else a[++x][y] = i;
	}
	for(int x=1;x<=n;x++){
		for(int y=1;y<=n;y++){
			cout<<a[x][y]<<" ";
		}
		cout<<endl;
	}
	return 0;
} 

二、P1161 开灯

分析：使用数组来记录每个灯的状态（是否开着），借助循环来模拟\(n\)次操作过程即可：

#include<iostream>
using namespace std;
const int N = 500000;
int b[N+10];  //全局数组，每个元素初值全为0，正好表示开始时所有灯是关着的
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		double a;
		int t;
		cin>>a>>t;
		for(int j=1;j<=t;j++){
            int k = a*j;
            if(k<=N) b[k] = 1-b[k];
		}
	}
	for(int i=1;i<=N;i++){
		if(b[i]){
			cout<<i<<endl;
			break;
		}
	}
	return 0;
} 

三、P2670 扫雷游戏

分析：对于雷区第\(x\)行\(y\)列的格子\((x,y)\)来说，如果这个格子不是雷，那么就要统计其周围8个格子雷的数量。这里的坐标系和周围8个格子的坐标描述如下图所示：

那么如何高效地描述\((x,y)\)周围的8个格子呢？我们来看下面的双重循环：

//对于格子(x,y)，其周围（包括自身）的格子可以用如下双重循环来描述
for(int i=-1;i<=1;i++){
	for(int j=-1;j<=1;j++){
		if(x+i>=1 && x+i<=n && y+j>=1 && y+j<=m)
			//a[x+i][y+j];
	}
}

可以通过双重循环遍历雷区每一个格子\((x,y)\)，如果格子不是雷，那么再使用上面的方法统计周围8个格子的雷数量：

#include<iostream>
using namespace std;
int a[110][110];
int main() {
	int n,m;
	char ch;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>ch;
			a[i][j] = ch=='*'?1:0;   //标记是否是雷
		}
	}
	for(int x=1;x<=n;x++){
		for(int y=1;y<=m;y++){
			if(a[x][y]) {	//该格子是雷，输出* 
				cout<<"*";
				continue;
			}
			//该格子不是雷，统计周围格子雷的数量 
			int cnt = 0;
			for(int i=-1;i<=1;i++){
				for(int j=-1;j<=1;j++){
					if(x+i>=1 && x+i<=n && y+j>=1 && y+j<=m)
						cnt += a[x+i][y+j];
				}
			}
			cout<<cnt;
		}
		cout<<endl;
	}
	return 0;
}

其实还可以使用数组来记录格子\((x,y)\)周围的8个格子\(x\)坐标和\(y\)坐标的相对于\((x,y)\)的变化情况，通过遍历数组就能在\((x,y)\)的基础上计算出周围8个方向的格子的坐标：

int dxy[8][2] = {
	{-1,-1},	   //左上(x-1,y-1) 
	{-1,0},		//正上(x-1,y)
	{-1,1},		//右上(x-1,y+1)
	{0,-1},		//左(x,y-1)
	{0,1},		 //右(x,y+1)
	{1,-1},		//左下(x+1,y-1)
	{1,0},		 //正下(x+1,y)
	{1,1},		 //右下(x+1,y+1) 
};

for(int i=0;i<8;i++){
	int nx = x+dxy[i][0],ny = y+dxy[i][1];
	if(nx>=1 && nx<=n && ny>=1 && ny<=m)
		//a[nx][ny];
}

完整的参考程序如下：

#include<iostream>
using namespace std;
int a[110][110];
int dxy[8][2] = {
	{-1,-1},	   //左上(x-1,y-1) 
	{-1,0},		//正上(x-1,y)
	{-1,1},		//右上(x-1,y+1)
	{0,-1},		//左(x,y-1)
	{0,1},		 //右(x,y+1)
	{1,-1},		//左下(x+1,y-1)
	{1,0},		 //正下(x+1,y)
	{1,1},		 //右下(x+1,y+1) 
};
int main() {
	int n,m;
	char ch;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>ch;
			a[i][j] = ch=='*'?1:0;
		}
	}
	for(int x=1;x<=n;x++){
		for(int y=1;y<=m;y++){
			if(a[x][y]) {	//格子是雷，输出* 
				cout<<"*";
				continue;
			}
			//格子不是雷，统计周围区域雷的数量 
			int cnt = 0;
			for(int i=0;i<8;i++){
				int nx = x+dxy[i][0],ny = y+dxy[i][1];
				if(nx>=1 && nx<=n && ny>=1 && ny<=m)
					cnt += a[nx][ny];
			}
			cout<<cnt;
		}
		cout<<endl;
	}
	return 0;
}

四、P1563 玩具谜题

分析：题目中给出的数据规模还是比较大的，如果使用双重循环来模拟整个过程（对于每条指令玩具小人一个接一个计数）会出现超时。使用两个数组分别记录每个玩具小人的朝向和职业，可以使用变量来记录指令执行后达到的玩具小人的编号\(j\)，对于要执行指令的玩具小人，如果玩具小人的朝向值和指令的方向值相同（玩具小人朝向圈内并且向左数数，或者玩具小人朝向圈外并且向右数数），那么下一个玩具小人的编号是\(j-s\)；否则下一个玩具小人的编号是\(j+s\)。此外就是一些细节的处理了：

#include<iostream>
using namespace std;
int dir[100000];
char name[100000][20];
int main()
{
    int n,m,i,j,a,s;

    cin>>n>>m;
    for(i=0;i<n;i++){
    	cin>>dir[i]>>name[i];
    }
    
    j = 0;            //j记录指令执行后到达的小人对应的数组下标 
    for(i=1;i<=m;i++){
        cin>>a>>s;
        s %= n;       //避免s太大（超过n） 
        if(dir[j]==a){  //玩具小人的朝向值和指令的方向值相同
            j -= s;
            if(j<0) j += n;
        }else{               //玩具小人的朝向值和指令的方向值不同
            j += s;
            if(j>=n) j -= n;
        }
    }
	cout<<name[j]<<endl;
    return 0;
} 

五、P1328 生活大爆炸版石头剪刀布

分析：本问题的难点在于如何高效地比较两人出拳结果，从题目描述中给出的表格可以得到提示，可以使用二维数组来记录两人出拳的比较结果：

int score[5][5] = {
	{0,0,1,1,0},
	{1,0,0,1,0},
	{0,1,0,0,1},
	{0,0,1,0,1},
	{1,1,0,0,0}
};

二维数组就是根据题目游戏结果表格得出来的。有了这个二维数组，可知如果小A出拳是a，小B拳是b，那么本轮小A的得分是score[a][b]，本轮小B的得分是score[b][a]。剩下的问题就是在\(n\)次循环中，根据两人的出拳规律得出每次的出拳情况：

#include<iostream>
using namespace std;
int score[5][5] = {
    {0,0,1,1,0},
    {1,0,0,1,0},
    {0,1,0,0,1},
    {0,0,1,0,1},
    {1,1,0,0,0}
};
int loopa[210],loopb[210];
int main()
{
    int n,na,nb;
    cin>>n>>na>>nb;
    
    for(int i=0;i<na;i++) cin>>loopa[i];
    for(int i=0;i<nb;i++) cin>>loopb[i];
    
    int sa = 0,sb = 0;    //两人得分 
    int ia = 0,ib = 0;    //两人出拳（在出拳规律的数组中的下标） 
    for(int i=1;i<=n;i++){
        sa += score[loopa[ia]][loopb[ib]];
        sb += score[loopb[ib]][loopa[ia]];
        ia ++;if(ia==na) ia = 0;
        ib ++;if(ib==nb) ib = 0;
    }
	
	cout<<sa<<" "<<sb<<endl;
    return 0;
}