前言

本文章为合集“年轻人的第一节算法课”中的第一篇文章。

众所周知，入门算法一共有九个：

今天，我们来讲前面三个——模拟、枚举、排序。

在学习之前，你最好保证你满足如下条件：

热爱编程与 C++
会熟练使用 Dev-C++ 或其他 IDE
会熟练使用洛谷进行评测
学习过 C++ 基础语法，如循环、递归
学习过 STL
学习过本系列文章前面的课程

开始吧！

任何一个伟大的理想，都有一个微不足道的开始。

模拟

算法解释

最简单的算法，没有之一。

一般的模拟题面可能稍微长一点，但数据范围很小。直接依照题面来写程序即可，不需要任何优化。

各大考试中经常以一道模拟题来作为“签到题”。如 CSP-J2024 T2 就是一道典型的模拟题。

模拟题主要注重选手的思考能力与编码能力。一般模拟题目的代码都比较长，但我们依然可以稍微减少编码难度。一般可以使用这些技巧：

多使用结构体来面向对象编程。一般模拟题中都有很多“角色”，例如人、武器、敌人等，给每个角色都套一个结构体可以增加代码可读性。
多使用 STL。适当使用 STL 可以让代码简化许多，比如用 map 来映射。
多写函数。函数名可以提供“语义”功能，让人知道这段函数在干什么；而且函数使用起来非常方便。函数也可以放到结构体中，作为成员函数。
多写注释。用注释来解释一段代码在干什么。

上面都是一些编码时的技巧。除此之外，还有很多辅助的技巧：

把每个版本的代码都保存下来，不要只存一个文件。如果你想重构一段代码就能方便地找回历史代码。
写完一个功能要及时测试。如果全到最后一起测试很可能出错，而且错了也不知道错在哪。一定要保证这个功能一定正确再写下一个功能。
可以针对各种情况手造数据。如果不确定答案是否正确，可以用题解和自己的代码对拍。

除此之外，模拟就没什么好讲的了。直接放例题。

例题 P1067

题目链接

依照题目描述模拟即可。

CPP

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n;
int a[105];
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n+1;i++) cin>>a[i];//输入
	for(int i=1;i<=n+1;i++){
		if(a[i]>0&&i!=1) cout<<'+';//不是第一项且系数为正，输出正号
		if(a[i]==0) continue;//系数为0，不输出，跳过
		if(a[i]==-1){//系数为-1
			if(i!=n+1) cout<<'-';//不是最后一项，输出负号
			else cout<<-1;//最后一项，输出-1
		}
		else if(a[i]!=1) cout<<a[i];//系数不是1，直接输出
		else if(a[i]==1&&i==n+1) cout<<1;//最后一项，输出1
		if(n+1-i!=0){//次数不为0
			if(n==i) cout<<'x';//一次项
			else cout<<"x^"<<n+1-i;//不是一次项，按格式输出
		}
	}
	return 0;
}

这题有不少坑点，下面一一说明。

系数为 $1$ 或 $-1$ 时只需要输出符号，但最后一项除外；
$x$ 的次数如果是 $1$ 那只输出 $x$
$x$ 的系数如果是 $0$ 就不输出这一项
有可能只有一个常数

注意到这些坑点，就不难写出代码了。

习题

然而，模拟有时也特别难。主要是因为比赛时间短、标准代码长，考场上几乎没人写得出来。下面给出一些特别有难度的模拟：

总结

出大模拟题的人，离神近不近我不知道，反正离人很远了。

枚举

算法解释

枚举又叫暴力，以高到爆炸的时间复杂度换取正确的答案。一般打暴力有两种方法：for 循环嵌套或 dfs。作为面向新手的教程，这里只介绍循环嵌套。

计算机唯一的优点就是运算速度极快。一般的机器每秒可以运行

10^8

到

10^9

次代码，洛谷神机基本可以顶到头。所以，在数据范围非常小时，暴力就是很好的选择。我们只需要枚举出所有的可能性，再对每种可能性进行处理即可。

当然，不是每次我们都这么好运，直接枚举就能通过。我们需要对枚举进行优化，让时间复杂度降低。优化的方法千奇百怪，这里只讲最基础的。

例题 P3392

题目链接

我们发现，每一行的颜色是唯一的。我们可以枚举有多少行是白色的，有多少行是蓝色的，剩下的行就是红色的。

接着，我们遍历整张图，计算把原图修改为当前图所需的代价，取最小值即可。时间复杂度

O(n^4)

。

CPP

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n,m;
int a[55][55];
ll ans=2147483647,sum=0;
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=m;j++){
    		char x;
    		cin>>x;
    		if(x=='W') a[i][j]=1;
    		if(x=='B') a[i][j]=2;
    		if(x=='R') a[i][j]=3;
		}
	}
	for(int w=1;w<=n;w++){//枚举白色行
		for(int r=w+2;r<=n;r++){//枚举蓝色行
			//B:w+1 - r-1
			sum=0;//计算代价
			for(int i=1;i<=w;i++){
				for(int j=1;j<=m;j++){
					if(a[i][j]!=1) sum++;
				}
			}
			for(int i=r;i<=n;i++){
				for(int j=1;j<=m;j++){
					if(a[i][j]!=3) sum++;
				}
			}
			for(int i=w+1;i<=r-1;i++){
				for(int j=1;j<=m;j++){
					if(a[i][j]!=2) sum++;
				}
			}
			ans=min(ans,sum);//取最小值
		}
	}
	cout<<ans<<endl;
	return 0;
}

例题 P2241

题目链接

用

a,b

记录两个答案。首先想到的是枚举棋盘中两个正方形作为矩形的左上、右下角，判断矩形的形状记录答案即可。这样时间复杂度为

O(n^2m^2)

，不能通过。

考虑优化，当我们枚举到一个正方形

(i,j)

时，分别来看对

a

和

b

的贡献。先看正方形，分类讨论

i

和

j

谁大谁小

年轻人的第一节算法课（1）——模拟、枚举、排序

文章操作

前言

模拟

算法解释

例题 P1067

习题

总结

枚举

算法解释

例题 P3392

例题 P2241

相关推荐

评论

年轻人的第一节算法课（1）——模拟、枚举、排序