算法基础篇--模拟

模拟

模拟的含义

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

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

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;
}