C++课程总结————模拟法

模拟法

1）模拟定义：

• 模拟类问题，就是根据计算机的相关功能，按照要求，一步一步求出结果。

2）个人理解：

• 模拟类题目一般会规定好规则，大部分不需要贪心。 不过，既然有这么高大上的名字，所以模拟绝非简单。 因为模拟类题目都有一个工同的特点： 1.题目长 2.题目复杂 3.题目细节要求多 。所以，一不小心就掉到了题目的坑里，需要静下心来排查细节。

3）例题：[usaco2019jan bronze]shell 果壳游戏

• 题目描述：

• [一]，
• 为了消磨时光，奶牛Bessie和她的朋友Elsie喜欢玩一种她们在农业展览会上看到的游戏。
  [二]（关键），
  游戏准备阶段，Bessie在桌子上放置三个倒置的坚果壳，并在其中一个坚果壳下面藏了一块小的鹅卵石。随后Bessie会两两调换坚果壳，同时Elsie试着去猜鹅卵石的位置。
  [三].
  奶牛们在农业展览会上看到的这个游戏的标准形式是玩家可以看到鹅卵石初始的位置，然后要求玩家猜所有交换完成之后鹅卵石最终的位置。
  [四]（关键）.
  然而，现在奶牛们想要去进行这样一种玩法，Elsie不知道鹅卵石的初始位置，同时她可以在每一次交换之后猜一下鹅卵石的位置。Bessie知道正确答案，在游戏结束后会给Elsie一个分数，等于她猜对的次数。
  [五].
  给定所有的交换和Elsie的猜测，但是不给出鹅卵石的初始位置，请求出Elsie最高可能获得的分数。

4）样例

输入

• 输入的第一行包含一个整数N，为交换的次数（1≤N≤100）。
• 以下NN行每行描述了游戏的一个回合，包含三个整数a，b和g。
  表示Bessie交换了坚果壳a和b，然后Elsie猜的是坚果壳g。
  所有这三个数均为1、2、3之一，并且a≠b。

3
1 2 1
3 2 1
1 3 1

输出

• 输出Elsie可以得到的最高分数。
• 在这个例子中，Elsie最多可以获得2分。
  如果开始时位于坚果壳1下面，那么她猜中了一次（最后一次）。
  如果开始时位于坚果壳2下面，那么她猜中了两次（开始两次）。
  如果开始时位于坚果壳3下面，那么她没有猜对任何一次。

2

5）思路：

• 首先解决输入，定义数组，把a,b,g都存起来。
• 接着就是模拟的过程，本题的主要想法是：假设第一个果壳下有石头，经过循环看一下哪个g是猜对的，加起来。
  同理假设第二个，第三个，比较最高的，输出。

6） 上代码：

核心代码

for(int i=1;i<=3;i++){//循环表示假设三个数的过程
		sum=0;//计数器清零
		for(int l=1;l<=3;l++)//模拟数组清零
		{
			other[l]=0;
		}
		other[i]=1;//假设过程
		for(int j=1;j<=n;j++){//模拟每一次交换
			swap(other[a[j]],other[b[j]]);//(swap)是交换函数
				if(other[g[j]]==1) sum++;//判断g是否有石头
		}
		if(sub<sum){//打擂台
			sub=sum;
		}
	}

• 1
• 2
• 3
• 4
• 5
• 6
• 7
• 8
• 9
• 10
• 11
• 12
• 13
• 14
• 15

总结:

• 模拟题目，
• 难题可以特比难（难在算法上），
• 简单题也可以特别难（难在理解题目上），
• 对待模拟类题目需要仔细检查；
• 模拟类题目一般会和字符串连用，在下一个博客里，我会分享 【noip2007提高】字符串展开 （模拟类的典型题目）；