模拟专题（普及- — 普及+）
模拟通常比较简单，所以经常会作为第一题进行考察
P1724 东风谷早苗
高中的时候最喜欢的角色之一就是早苗了， 我还买了个早苗的抱枕，hh。
分析
按照题目的意思，我们就是根据字符移动对应次数显然我们时不需要完全的模拟，只需要计算出一次完整的运动后
x 与 y的变化量然后 x 循环的次数 再加上 剩余的移动即可
代码
#include <iostream>#include <map>#include <string>using namespace std;#define x first#define y secondtypedef pair<int, int> PII;map<char, PII> p;string s;int sec;void operator+=(PII& a, PII& b) {a.x += b.x;a.y += b.y;}void operator*= (PII& a, int& nums) {a.x *= nums;a.y *= nums;}int main() {p['E'] = {1, 0 };p['S'] = {0, -1 };p['W'] = {-1, 0 };p['N'] = {0, 1 };cin >> s >> sec;int once = s.size(), nums = sec / s.size();PII pos = {0, 0 };for (auto e : s) pos += p[e];pos *= nums;for (int i = 0; i < sec % s.size(); ++i) {pos += p[s[i]];}cout << pos.x << " " << pos.y << endl;return 0;}
P2615 神奇的幻方
分析
就是开一个足够大的数组 然后按照题目描述进行填充即可代码
#include <iostream>#include <map>using namespace std;#define x first#define y secondconst int N = 40;typedef pair<int, int> PII;int g[N][N];int n;map<int, PII> pos;PII cal(int z) {auto t = pos[z];int x = t.x, y = t.y;if (x == 0 && y != n - 1) return {n - 1, y + 1 };else if (y == n - 1 && x != 0) return {x - 1, 0 };else if (x == 0 && y == n - 1) return {x + 1, y };else if (g[x - 1][y + 1] == 0) return {x - 1, y + 1 };else return {x + 1, y };}int main() {cin >> n;g[0][n / 2] = 1;pos[1] = {0, n / 2 };for (int i = 2; i <= n * n; ++i) {auto t = cal(i - 1);g[t.x][t.y] = i;pos[i] = {t.x, t.y };}for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j)cout << g[i][j] << " ";puts("");}return 0;}
P8870 B-莲子的机械动力学
分析这题本质就是一个高精度加法， 但是注意考虑特殊进制
代码
#include <iostream>#include <string>#include <vector>using namespace std;const int N = 200010;vector<int> s1, s2;int n, m;vector<int> a, b;vector<int> add(vector<int>& a, vector<int>& b) {if (a.size() < b.size()) return add(b, a);vector<int> res;for (int i = 0, t = 0; i < a.size() || t; ++i) {if (i < a.size()) t += a[i];if (i < b.size()) t += b[i];res.push_back(t % (i + 2));t /= i + 2;}while (res.size() > 1 && !res.back()) res.pop_back();return res;}void input(vector<int>& s, int n) {for (int i = 0; i < n; ++i) {int x;cin >> x;s.push_back(x);}}int main() {cin >> n >> m;int in = 0;input(s1, n);input(s2, m);for (int i = s1.size() - 1; i >= 0; --i) a.push_back(s1[i]);for (int i = s2.size() - 1; i >= 0; --i) b.push_back(s2[i]);auto res = add(a, b);for (int i = res.size() - 1; i >= 0; --i) cout << res[i] << " ";return 0;}
P1076 寻宝
分析
唯一值得一提的是在我们对寻找上楼房间次数优化的时候，如果恰好只需要转整数圈 （也就是%出来结果为0 ）那么我们的答案其实是在该点的前一个有楼梯的房间， 所以我们可以特殊处理f (z % nums) z %= nums;
else z = nums;
当恰好循环整数圈时 我们直接让次数等于 nums即可 （nums是该层楼有楼梯房间的个数）
代码
#include <iostream>using namespace std;#define x first#define y secondconst int N = 10010, M = 110;const int MOD = 3;typedef pair<int, int> PII;typedef long long LL;PII g[N][M];int n, m;LL res;void play(int q, int p) {if (q == n) return;res = (res + g[q][p].y) % MOD;int nums = 0;for (int i = 0; i < m; ++ i) {if (g[q][i].x == 1) nums ++;}int z = g[q][p].y;int i = 0;if (g[q][p].x == 1) i ++;//p --;if (z % nums) z %= nums;else z = nums;for (; i < z;) {p ++;p %= m;if (g[q][p].x == 1) i ++;}play(q + 1, p);}int main() {cin >> n >> m;for (int i = 0; i < n; ++ i) {for (int j = 0; j < m; ++ j) {int x, y;cin >> x >> y;g[i][j] = {x, y};}}int st;cin >> st;play(0, st);cout << res << endl;return 0;}
P8676 自描述序列
分析
看数据个数 显然我们是没法将所有的数据存储来内存中的，但是通过观察可以发现 数据出现的个数同样满足g(x)函数 所有我们可以左这样的一层嵌套处理i += g[j] * j;
这句话的意思就是（我们在加的时候直接加上重复了j次的所有数据）
j表示当前数的长度（例如g(2) = g(3) == 2·g(4) == g(5) == 2所以j == 2 && g[j] == 2） 也就是我们一次性跳过的是重复出现了j次的所有数
*扩展：
由刚刚的性质可以得出， 每一层的次数其实都跟g(x)有关 所以我们完全可以继续嵌套 即让g[g[j]]表示为 重复出现了g[g[j]]次的 每次循环次数为g[j]的长为j || j + 1 || j + 2 || ... ||j + g[j]的数 对于j怎么求不细讲（其实是可以直接求出总和的）；
注： 扩展只为帮助大家理解自描述序列，理论上来说在嵌套循环足够多的情况下可以做到不开数组求出结果（嵌套越多 精度越大 2层嵌套可以精确的算出50以内的数据, 在最后一层循环不会终止的情况下 数据就是精确的！！！）
代码
#include <iostream>using namespace std;typedef unsigned long long ULL;const int MOD = 1e9 + 7;const int N = 1e7;ULL n;ULL res;int g[N];int q[N];int main() {cin >> n;g[1] = 1;g[2] = 2;for (int i = 1, k = 1, nums = 1; i < N; ++i, nums++) {for (int j = 0; j < g[i] && k < N; j++) {g[k++] = nums;}}for (ULL i = 1, j = 1; i <= n; j++) {i += g[j] * j;res += g[j];if (i > n) {i -= g[j] * j;res -= g[j];res += (n - i + 1) / j + 1;break;}}if (n < N) cout << g[n] << endl;else cout << res << endl;return 0;}
P3952 时间复杂度
分析
为了求取时间复杂度 我们可以想到用栈去模拟循环的代码块接下来我们分析一下实现过程中具体的细节
1计算时间复杂度
(1) 当 x 为 n时
如果 y为n 那么时间复杂度不变
如果y为 常数 那么时间复杂度叠加
(2) 当y为n时
如果x为n 那么时间复杂度不变
如果x为常数 那么该循环不执行， 后面的循环直接跳过
(3) 当 x y 都为常数时
比较x y的大小 若x >= y 那么时间复杂度不变
否者 该循环不执行 后面的循环跳过
2计算ERR
只有三种情况会出现ERR
（1） 当前变量前面出现过 我们可以遍历栈来排查出这种情况（注： 由于要遍历栈里的元素 所以我们需要实现自己的栈）
（2）当栈为空时要求弹出元素
（3）当函数结束时 栈不为空
代码
#include <iostream>#include <string>#include <cstring>using namespace std;const int N = 1010;char stk[N];int top;char T[100];bool flag;int isT[N];bool check(char ch) {for (int i = 0; i < top; ++i) {if (stk[i] == ch) return true;}return false;}bool check(string& s) {int i = 4;string ch1, ch2;bool flag1 = true;while (i < s.size()) {if (flag1) ch1 += s[i++];else ch2 += s[i++];if (s[i] == ' ') flag1 = false, i++;}if (ch1 == "n" && ch2 != "n") {flag = false;return false;}if (ch2 == "n" && ch1 == "n") return false;if (ch2 == "n") return true;if (stoi(ch1) > stoi(ch2)) flag = false;if (ch1 == "n") return false;return false;}int getNum() {int res = 0, j = 4;while (T[j] >= '0' && T[j] <= '9')res = res * 10 + T[j++] - '0';return res;}void clear(int& n) {string s;while (n--) getline(cin, s);n = 0;}int main() {int t;cin >> t;while (t--) {flag = true;top = 0;int res = 0, temp = 0;int n;cin >> n;cin >> T;getchar();memset(isT, 0, sizeof isT);bool cc = false;while (n--) {string s;getline(cin, s);if (s[0] == 'F') {// 处理循环if (check(s[2])) {cout << "ERR" << endl;cc = true;clear(n);break;} // 变量冲突if (check(s)) {temp++;res = max(res, temp);}else if (flag) {isT[temp]++;}int F = 0, E = 0;bool bb = false;while (!flag) {getline(cin, s);n--;if (s.size() > 1 && check(s[2])) {cout << "ERR" << endl;clear(n);cc = bb = true;break;} // 变量冲突if (s[0] == 'F') F++;else if (s[0] == 'E') E++;if (E > F) flag = true;}if (bb) break;if (!E) stk[top++] = s[2];}else if (s[0] == 'E') {if (top == 0) {cout << "ERR" << endl;cc = true;clear(n);break;}top--;if (!isT[temp]) temp--;else isT[temp]--;}}if (cc) continue;if (top != 0) cout << "ERR" << endl;else if (res == 0 && T[2] == '1') cout << "Yes" << endl;else if (T[2] == '1') cout << "No" << endl;else {if (res == getNum()) cout << "Yes" << endl;else cout << "No" << endl;}}}
本次模拟专题就到此结束啦！！！完结撒花~~~
