【基础算法】模拟算法

算法简介

模拟，顾名思义，就是题目让你做什么你就做什么，考察的是将思路转化成代码的代码能力。 这类题一般较为简单，属于竞赛里面的签到题（但是，万事无绝对，也有可能会出现让人非常难受的模拟题），我们在学习语法阶段接触的题，大多数都属于模拟题。

下面我们通过几道 OJ 练习题来感受一下。

1. 多项式输出

【题目链接】

[P1067 NOIP 2009 普及组] 多项式输出 - 洛谷

【题目描述】

一元 $n$ 次多项式可用如下的表达式表示：

$$f(x)=a_n{x}^n+a_{n-1}{x}^{n-1}+\cdots +a_{1}x+a_0,a_n\ne 0$$

其中，$a_i{x}^i$ 称为 $i$ 次项，$a_i$ 称为 $i$ 次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：

1. 多项式中自变量为 $x$，从左到右按照次数递减顺序给出多项式。

2. 多项式中只包含系数不为 $0$ 的项。

3. 如果多项式 $n$ 次项系数为正，则多项式开头不出 + 号，如果多项式 $n$ 次项系数为负，则多项式以 - 号开头。

4. 对于不是最高次的项，以 + 号或者 - 号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于 $0$ 次的项，其系数的绝对值为 $1$，则无需输出 $1$）。如果 $x$ 的指数大于 $1$，则接下来紧跟的指数部分的形式为“$x^b$”，其中 $b$ 为 $x$ 的指数；如果 $x$ 的指数为 $1$，则接下来紧跟的指数部分形式为 $x$；如果 $x$ 的指数为 $0$，则仅需输出系数即可。

5. 多项式中，多项式的开头、结尾不含多余的空格。

【输入格式】

输入共有 $2$ 行

第一行 $1$ 个整数，$n$，表示一元多项式的次数。

第二行有 $n+1$ 个整数，其中第 $i$ 个整数表示第 $n-i+1$ 次项的系数，每两个整数之间用空格隔开。

【输出格式】

输出共 $1$ 行，按题目所述格式输出多项式。

【示例一】

输入

5 
100 -1 1 -3 0 10

输出

100x^5-x^4+x^3-3x^2+10

【示例二】

输入

3 
-50 0 0 1

输出

-50x^3+1

【说明/提示】

NOIP 2009 普及组 第一题

对于100%数据，$0\le n\le 100$，$-100 \le $系数$ \le 100$

---

解题思路

注意到多项式的每一项都是由符号、系数以及字母 $x$ 带上相应的次数构成的。所以我们不妨从这三个角度出发去模拟，构建出每一项。

• 符号

  • 负数：直接输出 -
  • 正数：
    • 是第 $n$ 项，不输出 +
    • 其余情况，直接输出 +

• 系数（先取绝对值）

  • 不是 $1$，直接输出这个数字
  • 是 $1$
    • 如果是末项，需要输出
    • 不是末项，不需要输出

• 次数

  • 次数为 $0$，什么都不输出
  • 次数为 $1$，输出 $x$ 即可
  • 其他情况，输出 x^ + 对应的次数

---

代码实现

#include<iostream>
#include<cmath>using namespace std;int main()
{int n; cin >> n;for(int i = n; i >= 0; --i){int k; cin >> k;if(k == 0) continue;// 1.处理符号if(k < 0) cout << '-';else{if(i != n) cout << '+';}// 2.处理系数k = abs(k);if(k != 1 || (k == 1 && i == 0)) cout << k;// 3.处理次数if(i == 1) cout << 'x';if(i > 1) cout << "x^" << i;}return 0;
}

---

2. 蛇形方阵

【题目链接】

P5731 【深基5.习6】蛇形方阵 - 洛谷

【题目描述】

给出一个不大于 $9$ 的正整数 $n$，输出 $n\times n$
的蛇形方阵。

从左上角填上 $1$ 开始，顺时针方向依次填入数字，如同样例所示。注意每个数字有都会占用 $3$ 个字符，前面使用空格补齐。

【输入格式】

输入一个正整数 $n$，含义如题所述。

【输出格式】

输出符合题目要求的蛇形矩阵。

【示例一】

输入

4

输出

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

【说明/提示】

数据保证，$1\le n\le 9$。

---

解题思路

由于我们填数的时候是按照右下左上四个方向依次填入的，因此像这样的问题，我们有一个较为通用的方法就是使用方向向量。

首先我们需要定义一个二位数组（矩阵），这里我们以向下为 $x$ 轴正方向，向右为 $y$ 轴建立平面直角坐标系。那么向右走就对应 $y$ +1，$x$ 不变；向下走就对应 $x$ +1，y 不变；向左向上同理。这样一来我们就可以定义出方向向量如下：

int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

4 个位置从左往右依次对应右上左下 4 个方向。比如当我们需要向右走时，我们只需：

x += dx[0], y += dx[0];

定义好了方向向量之后，我们就开始填数。思路很简单，朝着一个方向填数，直到越界或者遇到已经填过的位置。如果越界或者遇到已经填过的位置，那么就更新方向向量再朝另一个方向填数。总共填 n * n 个数字，填完之后遍历数组输出即可。

---

代码实现

#include<iostream>using namespace std;#define N 15
int arr[N][N];int dx[] = {0, 1, 0, -1};  // 方向向量
int dy[] = {1, 0, -1, 0};int main()
{int n; cin >> n;int x = 1, y = 1;  // 起始位置int pos = 0;int cnt = 1;while(cnt <= n * n){arr[x][y] = cnt;// 要填的下一个位置int a = x + dx[pos];int b = y + dy[pos];if(a < 1 || a > n || b < 1 || b > n || arr[a][b])  // 如果这个位置不能填{pos = (pos + 1) % 4;  // 换方向a = x + dx[pos];b = y + dy[pos];}x = a, y = b;++cnt;}for(int i = 1; i <= n; ++i){for(int j = 1; j <= n; ++j){printf("%3d", arr[i][j]);  // 注意输出格式}puts("");}return 0;
}

---

3. 字符串的展开

【题目链接】

[P1098 NOIP 2007 提高组] 字符串的展开 - 洛谷

【题目描述】

在初赛普及组的“阅读程序写结果”的问题中，我们曾给出一个字符串展开的例子：如果在输入的字符串中，含有类似于 d-h 或者 4-8 的字串，我们就把它当作一种简写，输出时，用连续递增的字母或数字串替代其中的减号，即，将上面两个子串分别输出为 defgh 和 45678。在本题中，我们通过增加一些参数的设置，使字符串的展开更为灵活。具体约定如下：

(1) 遇到下面的情况需要做字符串的展开：在输入的字符串中，出现了减号 - ，减号两侧同为小写字母或同为数字，且按照 ASCII 码的顺序，减号右边的字符严格大于左边的字符。

(2) 参数 $p_1$：展开方式。$p_1=1$ 时，对于字母子串，填充小写字母；$p_1=2$ 时，对于字母子串，填充大写字母。这两种情况下数字子串的填充方式相同。$p_1=3$ 时，不论是字母子串还是数字字串，都用与要填充的字母个数相同的星号 * 来填充。

(3) 参数 $p_2$：填充字符的重复个数。$p_2=k$ 表示同一个字符要连续填充 $k$ 个。例如，当 $p_2=3$ 时，子串d-h 应扩展为 deeefffgggh。减号两边的字符不变。

(4) 参数 $p_3$：是否改为逆序：$p_3=1$ 表示维持原来顺序，$p_3=2$ 表示采用逆序输出，注意这时候仍然不包括减号两端的字符。例如当 $p_1=1$、$p_2=2$、$p_3=2$ 时，子串 d-h 应扩展为 dggffeeh。

(5) 如果减号右边的字符恰好是左边字符的后继，只删除中间的减号，例如：d-e 应输出为 de，3-4 应输出为 34。如果减号右边的字符按照 ASCII 码的顺序小于或等于左边字符，输出时，要保留中间的减号，例如：d-d 应输出为 d-d，3-1 应输出为 3-1。

【输入格式】

共两行。

第 $1$ 行为用空格隔开的 $3$ 个正整数，依次表示参数 $p_1,p_2,p_3$。

第 $2$ 行为一行字符串，仅由数字、小写字母和减号 - 组成。行首和行末均无空格。

【输出格式】

共一行，为展开后的字符串。

【示例一】

输入

1 2 1
abcs-w1234-9s-4zz

输出

abcsttuuvvw1234556677889s-4zz

【示例二】

输入

2 3 2
a-d-d

输出

aCCCBBBd-d

【说明/提示】

$40\%$ 的数据满足：字符串长度不超过 $5$。

$100\%$ 的数据满足：$1\le p_1\le 3,1\le p_2\le 8,1\le p_3\le 2$。字符串长度不超过 $100$。

NOIP 2007 提高第二题

---

解题思路

这道题的要求都在题干中说清楚了，重点就是转化为代码，考察的是代码能力。

依次遍历字符串，遇到除 - 以外的其他字符，不做特殊处理。遇到 -，就按照题目要求做处理即可。

---

代码实现

#include <iostream>
#include <algorithm>using namespace std;int p1, p2, p3, n;
string s;    // 读入的字符串 
string ret;  // 最终展开后的字符串// 判断是否是数字字符 
bool isdig(char ch)
{return ch >= '0' && ch <= '9';
}// 判断是否是⼩写字⺟ 
bool islet(char ch)
{return ch >= 'a' && ch <= 'z';
}// 把 [left, right] 之间的字符展开 
// left, right 这两个字符是不做处理的
void add(char left, char right)
{string t;// 遍历中间的字符 for (char ch = left + 1; ch < right; ch++){char tmp = ch;// 处理 p1 if (p1 == 2 && islet(tmp)) tmp -= 32; // ⼩写变⼤写else if (p1 == 3) tmp = '*'; // 变成星号 // 处理 p2 for (int i = 0; i < p2; i++){t += tmp;}}// 处理 p3 if (p3 == 2) reverse(t.begin(), t.end());ret += t;
}int main()
{cin >> p1 >> p2 >> p3 >> s;n = s.size();for (int i = 0; i < n; i++){char ch = s[i];if (s[i] != '-' || i == 0 || i == n - 1) ret += ch;else{char left = s[i - 1], right = s[i + 1];// 判断是否展开 if (isdig(left) && isdig(right) && right > left ||islet(left) && islet(right) && right > left){// 展开 add(left, right);}else{ret += ch;}}}cout << ret << endl;return 0;
}