算法基础篇--模拟

模拟

模拟的含义

模拟，顾名思义就是题目让你干什么，你就干什么。考察的是将思路转化成代码的代码能⼒。这类题⼀般较为简单，属于竞赛⾥⾯的签到题（但是，万事⽆绝对，也有可能会出现让⼈⾮常难受的模拟题），我们在学习语法阶段接触的题，⼤多数都属于模拟题。

现在我们就通过下面的几道题目来了解一下模拟的特点：

1. 多项式输出

题目来源：洛谷

题目链接：多项式输出

题目就是下面的样子：
在这里插入图片描述

模拟题没有什么可以详细讲解的思路，大家直接看地阿妈就可以搞懂这道题目的实现思路是什么。

#include<iostream>using namespace std;
int n;
const int N = 105;
int a[N];
int main()
{cin >> n;for (int i = n; i >= 0; i--) cin >> a[i];for (int i = n; i >= 0; i--){if (a[i] == 0) continue;if (a[i] < 0) cout << '-';else if (i != n && a[i] > 0) cout << '+'; if (abs(a[i]) != 1 || i == 0)cout << abs(a[i]);if (i == 0) continue;else if (i == 1) cout << 'x';else cout << "x^" << i;}return 0;
}

2. 蛇形方阵

题目来源：洛谷
题目链接：蛇形方阵
题意大致如下：

这道题目就是要求我们用正确的规则正确完成填表的任务。
这里使用的都是简单的语法，同时思路也十分的简单，知识需要大家将这个问题给看懂。
这里我就直接先展示相应的代码，再来讲解相关的原理思路。

#include <iostream>using namespace std;
const int N = 15;
int a[N][N];
// zdl:: 定义方向矢量
int dy[] = {1, 0, -1, 0};
int dx[] = {0, 1, 0, -1};
int main()
{int n;cin >> n;int cnt = 1;int pos = 0;// zdl:: 起始坐标int i = 1, j = 1;a[i][j] = cnt++;while (cnt <= n * n){int x = i + dx[pos], y = j + dy[pos];if (x > n || x < 1 || y > n || y < 1 || a[x][y]){pos = (pos + 1) % 4;x = i + dx[pos], y = j + dy[pos];}i = x; j = y;a[i][j] = cnt++;}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){printf("%3d", a[i][j]);}cout << endl;}return 0;
}

上面的代码就可以解决问题。这里我就解释一些解题的思路。

我们需要正确的定义方向向量在题目中，我们就是在 在遇到越界访问和已经填好的格子此时就需要我们进行转向；转向就是从上下左右这四个方向的点坐标进行分析的

(x - 1, y - 1)	(x - 1, y)	(x - 1, y + 1)
(x, y - 1)	(x, y)	(x, y + 1)
(x + 1, y - 1)	(x + 1, y)	(x + 1, y + 1)

从上面的表格就可以很直观的看出关于方向向量的使用规则，以后在进行BFS（宽度优先遍历）的学习时，我们就会使用到8个方向遍历的情况。

在走到一个越界的格子或者是一个已经填好数字的格子时，我们就会调转方向，在定义方向向量时，我们就要将方向向量的移动顺序确定，pos = (pos + 1) % 4 就是在移动方向确定好之后，简单的调转方向的方法。

3. 字符串的展开

题目来源：洛谷
题目链接：字符串展开
题目详情：

我们还是先来看代码：

#include <iostream>
#include <algorithm>
#include <string>
#include <cctype>
using namespace std;
string ret;
int main()
{int p1, p2, p3;string s;cin >> p1 >> p2 >> p3 >> s;int n = s.size();for (int i = 0; i < n; i++){char ch = s[i];if (ch != '-')ret += ch;else if (ch == '-'){char prev = s[i - 1], next = s[i + 1];if (next <= prev){ret += '-';continue;}string tmp;if (isdigit(prev) && isdigit(next) && next > prev || isalpha(prev) && isalpha(next) && next > prev){for (char i = prev + 1; i < next; i++)tmp += string(p2, i);if (p1 == 2 && !isdigit(tmp[0]))for (auto &ch : tmp)ch = toupper(ch);else if (p1 == 3)for (auto &ch : tmp)ch = '*';if (p3 == 2)reverse(tmp.begin(), tmp.end());}else{ret += ch;}ret += tmp;}}cout << ret << endl;return 0;
}