算法入门教程（一、模拟）_模拟算法

模拟

什么是模拟？

模拟是对真实事物或者过程的虚拟。在编程时为了实现某个功能，可以用语言来模拟那个功能，模拟成功也就相应地表示编程成功。

模拟算法的思路

模拟算法是一种基本的算法思想，可用于考查程序员的基本编程能力，其解决方法就是根据题目给出的规则对题目要求的相关过程进行编程模拟，说白了，就是题目说什么就做什么。在解决模拟类问题时，需要注意字符串处理、特殊情况处理和对题目意思的理解。

在C语言中，通常使用函数 srand() 和 rand() 来生成随机数。其中，函数 srand() 用于初始化随机数发生器，然后使用函数 rand() 来生成随机数。如果要使用上述两个函数，则需要在源程序头部包含 time.h 文件。在程序设计过程中，可使用随机函数来模拟自然界中发生的不可预测情况。在解题时，需要仔细分析题目给出的规则，要尽可能地做到全面考虑所有可能出现的情况，这是解模拟类问题的关键点之一。

例题与解

例题1：洛谷：P4445 [AHOI2018初中组]报名签到

题目描述

$n$ 位同学（编号从 $1$ 到 $n$）同时来到体育馆报名签到，领取准考证和参赛资料。为了有序报名，这 $n$ 位同学需要按编号次序（编号为 $1$ 的同学站在最前面）从前往后排成一条直线。然而每一位同学都不喜欢拥挤，对于第 $i$ 位同学，如果有另外一位同学距离他/她的距离小于 $a_i$，那么就会发生冲突。小可可想知道如果要不发生任何冲突的情况下，这 $n$ 位同学排队的队列最短长度是多少。

输入格式

第一行一个整数 $n$ ，表示报名签到的同学人数。

第二行有 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个同学必须与其他同学保持的距离。

输出格式

输出一行，包括一个整数，表示这 $n$ 位同学排队队列的最小长度。

注意： $n$ 位同学要按 $1$ 到 $n$ 的次序从前往后排队。

样例 #1

样例输入 #1

3
3 1 2
1
2

样例输出 #1

5
1

提示

对于 $20\%$ 的数据满足：$1\le n\le 20$。

对于 $70\%$ 的数据满足：$1\le n\le 10^4$。

对于 $100\%$ 的数据满足：$1\le n\le 10^5$，$1\le a_i\le 10^5$。

C++解

#include <iostream>
#include <algorithm>
using namespace std;

int a[100005];
long long t = 0;

int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	for (int i = 1; i < n; i++)
	{
		t += max(a[i], a[i + 1]);
	}
	cout << t << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Python解

n = int(input())
l = map(int,input().split(' '))
lis = list(l)
ans = 0
for x in range(1, n):
    ans = ans + max(lis[x], lis[x-1])
print(ans)
1
2
3
4
5
6
7

Pascal解

Var
	ans:qword;
	n,i,x,y:longint;
	
Function max(x1,y1:longint):longint;
begin
	if x1>y1 then exit(x1)
		else exit(y1);
end;

Begin
	read(n);
	read(x); //用两个变量滚动，就不用开数组了
	ans:=0;
	for i:=1 to n-1 do
		begin
			read(y); //每次读入
			ans:=ans+max(x,y); //选最大的
			x:=y; //滚动
		end;
	writeln(ans);
End.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

例题2：洛谷：P1978集合

题目描述

集合是数学中的一个概念，用通俗的话来讲就是：一大堆数在一起就构成了集合。

集合有如下的特性：

• 无序性：任一个集合中，每个元素的地位都是相同的，元素之间是无序的。

• 互异性：一个集合中，任何两个元素都认为是不相同的，即每个元素只能出现一次。

• 确定性：给定一个集合，任给一个元素，该元素或者属于或者不属于该集合，二者必居其一，不允许有模棱两可的情况出现。

例如 A = { 1 , 2 , 3 } A = \{ 1, 2, 3 \} A={1,2,3} 就是一个集合。我们可以知道，$1$ 属于 $A$，即 $1\in A$；$4$ 不属于 $A$，即 $4\notin A$。一个集合的大小，就是其中元素的个数。

现在定义一个特殊的 $k$-集合，要求满足：

• 集合的所有特性
• 对任意一个该集合内的元素 $x$，不存在一个数 $y$，使得 $y=kx$ 并且 $y$ 属于该集合。即集合中的任意一个数，它乘以 $k$ 之后的数都不在这个集合内。

给你一个由 $n$ 个不同的数组成的集合，请你从这个集合中找出一个最大的 $k$-集合。

输入格式

第一行：两个整数：$n$ 和 $k$。

第二行：$n$ 个整数：$a_i$ 表示给定的集合。

输出格式

第一行：一个整数：$ans$ 表示最大的 $k$-集合的大小。

样例 #1

样例输入 #1

6 2	
2 3 6 5 4 10
1
2

样例输出 #1

3
1

提示

提示：在样例所给集合中，找出的最大的 $2$-集合为 { 4 , 5 , 6 } \{ 4, 5, 6 \} {4,5,6}

• 对于 $30\%$ 的数据：$n,k\le 100$。
• 对于 $40\%$ 的数据：$a_i\le 2^{31}-1$。
• 对于 $70\%$ 的数据：$n,k\le 5000$。
• 对于 $100\%$ 的数据：$2\le n,k\le {10}^5$，$1\le a_i\le 2^{63}-1$。

C++解（1）

#include<iostream>
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
long long a[100005];
set<long long> A;
int n,k;
int main(){
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    sort(a+1,a+1+n);
    for(int i=1;i<=n;i++){
        if(a[i]%k||A.find(a[i]/k)==A.end()){//如果不能整除k或者集合中没有a[i]/k，满足条件就进入集合
            A.insert(a[i]);
        }
    }
    printf("%d\n",A.size());
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

C++解（2）

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define res register int
const int MAXN=100000+10;
ll n,k,total,s[MAXN];
map<ll,bool> mmp;

int main(){
	cin>>n>>k;
	for(res i=1;i<=n;++i) cin>>s[i];
	sort(s+1,s+n+1);
	for(res i=1;i<=n;++i){
		if(!mmp[s[i]]&&(s[i]%k||!mmp[s[i]/k])) mmp[s[i]]=1,++total;
	}
	cout<<total;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

C++解（3）（使用二叉树）

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define LL long long
#define int long long
void read(int &x){
	char c=getchar();
	int k=1;
	while(c<'0'||c>'9') {if(c=='-') k=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
	x=x*10+c-'0';
	x*=k;
}
const int N=1000005,oo=2147483647;
struct FHQ{
	int lc,rc,rnd,size;LL val;
}t[N];
int n,m,cnt,tot,x,y,k,op,root;LL a[N];
#define ls t[rt].lc
#define rs t[rt].rc
void up(int rt){
if(!rt)return;t[rt].size=t[ls].size+t[rs].size+1;
}
int build(LL v){
	tot++;t[tot].rnd=rand()<<15|rand();t[tot].size=1;t[tot].val=v;return tot;
}
void split(int rt,int &l,int &r,int k){
	if(k==0){l=0;r=rt;return;}
	if(k==t[rt].size){l=rt;r=0;return;}
	if(k<=t[ls].size)r=rt,split(ls,l,ls,k);
	else l=rt,split(rs,rs,r,k-1-t[ls].size);
	up(rt);
}
void merge(int &rt,int l,int r){
	if(!l||!r){rt=l+r;return;}
	if(t[l].rnd<t[r].rnd)rt=l,merge(rs,rs,r);
	else rt=r,merge(ls,l,ls);
	up(rt);
}
int rank(int rt,int v){
	if(!rt)return 0;
	if(v<=t[rt].val) return rank(ls,v);
	else return rank(rs,v)+t[ls].size+1;
}
void ins(int v){
	int a,b,c,rk=rank(root,v);
	split(root,a,b,rk);c=build(v);merge(b,c,b);
	merge(root,a,b);
}
bool find(int rt,LL x){
	if(!rt) return false;
	if(t[rt].val==x) return true;
	if(t[rt].val>x) return find(ls,x);
	return find(rs,x);
}
signed main(){
	t[0].rnd=oo;t[0].val=oo;read(n);read(k);
	for(int i=1;i<=n;i++)read(a[i]);
	sort(a+1,a+n+1);
	for(int i=1;i<=n;i++){
		if(a[i]%k!=0)ins(a[i]);
		else{
			if(!find(root,a[i]/k))ins(a[i]);
		}
	}
	printf("%d\n",t[root].size);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

Pascal解

var
  n,k,i,ans,num:longint;
  m,s:int64;
  a,t:array[-1..100002] of int64;
  f:array[-1..100002] of boolean;
procedure q(l,r:longint);
var
  i,j,m,k:longint;
begin
  if l=r then exit;
  m:=(l+r) div 2;
  q(l,m);
  q(m+1,r);
  i:=l;
  j:=m+1;
  k:=l;
  while (i<=m) and (j<=r) do
    if a[i]>=a[j] then begin t[k]:=a[i]; inc(i); inc(k); end else begin t[k]:=a[j]; inc(j); inc(k); end;
  while i<=m do
    begin t[k]:=a[i]; inc(i); inc(k); end;
  while j<=r do
    begin t[k]:=a[j]; inc(j); inc(k); end;
  for i:=l to r do
    begin
      a[i]:=t[i];
    end;
end;
function find(x:int64):longint;
var
  l,r,m:longint;
begin
  l:=1;
  r:=n;
  while l<r do
    begin
      m:=(l+r) div 2;
      if a[m]>x then l:=m+1 else r:=m;
    end;
  exit(l);
end;
begin
  readln(n,k);
  for i:=1 to n do read(a[i]);
  q(1,n);//大到小
  ans:=n;//答案，鄙人用的是减法，加法也可。
  for i:=1 to n do if not f[i] then//找到没有被排除的
    begin
      f[i]:=true;
      s:=a[i];
      num:=1;//这个数列的总个数
      while (a[find(s div k)]=s div k) and (s mod k=0) do//首先要能整除，然后再保证有这个数
        begin
          s:=s div k;
          f[find(s)]:=true;//排除
          inc(num);//+1
        end;
      ans:=ans-num div 2;//如果长度为偶数可取一半，奇数可取头尾，故+1后一半，即不可取一半
    end;
  write(ans);
end.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

本文完。关于模拟算法的题还有很多，可以在洛谷上刷。本文由于代码有一些已经加了注释，所以就不在文章里说明了，如果不懂，欢迎在评论区留言。