算法基础——模拟

1 多项式输出

2.蛇形方阵

3.字符串的展开

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

1 多项式输出

题⽬来源：洛⾕

题⽬链接：P1067 [NOIP2009 普及组] 多项式输出

难度系数： ★

[解法]

根据题意模拟+分类讨论（分的越详细，越不会出现bug）：

仅需按照顺序，考虑每⼀项的三件事情：符号 + 系数 + 次数。

处理「符号」：

负数：直接输出
正数：(1) 是第n项，不输出+ （2）其余情况，直接输出+

处理「系数」：

先取绝对值：

（1）不是1，直接输出

（2）是1

末项 - 需要输出

不是末项 - 不需要输出

处理「次数」：

次数为 1 ，输出 "x"；

次数为0 ，什么也不输出

其他，输出 "x^" + 对应的次数；

【参考代码】

#include<iostream>
#include<cmath>
using namespace std;int main(){int n;cin >> n;//循环次数 for(int i = n;i >= 0;i--){int op;cin >> op;if(op == 0) continue;//出来系数为0的情况 //1.符号 if(op < 0) cout << "-";else{if(i != n) cout << "+";} //2.系数int a = abs(op);if(a != 1 || (a==1 && i== 0)) cout << a;//3.次数if(i == 1)cout << "x";else if(i == 0) ;else{cout << "x^" << i;} }return 0;
}

2.蛇形方阵

题⽬来源：洛⾕

题⽬链接：P5731 【深基5.习6】蛇形⽅阵

难度系数： ★

[解法]

模拟填数的过程。（实现的方式有很多种）

在⼀个矩阵中按照⼀定规律填数的通用解法：

定义方向向量

比如本题⼀共四个方向，分别是右、下、左、上，对应： (0, 1)、(1, 0)、(0, -1)、(-1, 0)

遇到其他类型的题只需要更改方向向量即可；

2.根据规则结合方向向量填数

（1）朝⼀个方向⾛，⼀边走⼀边填数，直到越界；

（2）越界之后，结合定义的方向向量，求出下⼀轮应该⾛的方向以及应该到达的正确

位置；

（3）重复上述过程，直到把所有的数填完为止；

【参考代码】

#include<iostream>
using namespace std;const int N = 15;//定义方向向量 右，下， 左，上 
int dy[] = {1,0,-1,0};
int dx[] = {0,1,0,-1};int arr[N][N];int main(){int n;cin >> n;//模拟填数过程 int cet = 1; //当前位置要填的数 int x = 1,y = 1;//初始位置 int pos = 0;//当前的方向 while(cet <= n*n){arr[x][y] = cet;//计算下一个位置 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];}cet++;x = a;y = b;} for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){printf("%3d",arr[i][j]);}printf("\n");}return 0;
}

3.字符串的展开

题⽬来源：洛谷

题⽬链接： P1098 [NOIP2007 提⾼组] 字符串的展开

难度系数： ★

【解法】

纯代码题 - 考察代码能力：>

【参考代码】

#include<iostream>
#include<algorithm>
using namespace std;int p1,p2,p3,n;
string s,ret;//判断是否是数字字符 
bool isdig(char ch){return ch >= '0' && ch <= '9';;
}//判断是否小写字母 
bool islet(char ch){return ch >= 'a' && ch <= 'z';
}//展开 把(left,right)之间的字符展开 
void add(char l,char r){string t;//遍历中间的字符for(char ch = l + 1;ch < r;ch++){char tmp = ch;//处理p1 if(p1 == 2 && islet(tmp)) tmp -= 32; //小写变大写 else if(p1 == 3) tmp = '*';//变成星号 //处理p2 for(int i = 1;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) && left < right) || (islet(left) && islet(right) && left < right)){//展开add(left,right); }else{ret += ch; }}}cout << ret << endl;return 0;
}