大模拟
昨天刷了几道普通的大模拟后写了一道整整 \(113\) 行的 \(\text{NOIP}2018\) 提高组，第一天第二题——时间复杂度 累死我了，难度是惊人的绿题(相当于 \(\text{CSP-J}\) 压轴)，非常吓人，只需要用到栈，但是状态非常复杂，这就是大模拟题目的令人苦恼之处——耗时间，而且细节很多，稍有不慎就会WA,甚至 \(0\) 分，下面就结合题目本身来讲一下大模拟的解法。
首先，过滤掉无用信息。大模拟类型题目几乎都有着非常长的题面，比如这道题里面，有些东西讲的很少，却极其重要，如本题中的时间复杂度计算方法，都放在了输入格式里面。这里告诉大家输入输出格式里蕴含的信息会占题目的 \(50\%\)，必须认真阅读。在读完题后，可以得出以下精简版的题面。
在一个语言中，循环语句的格式为F i x y，结束语句为E，一一对应。如果 \(x ≤ y\) 则进入循环，否则不进入，其中会出现一个整数 \(n\)，其大于 \(100\)，而 \(x\) 与 \(y\) 如果是数字，小于 \(100\)，现在给出你 \(T\) 组数据，每组数据的语句数量以及格式为 O(1) 或者 O(n^w) 的时间复杂度，求是否正确，输出Yes或者No如果循环与结束语句不对应或者变量没有用完的情况下重复使用，输出ERR。
其次，考虑怎么去模拟，这一部分无疑是模拟中最难的那一部分。我们可以考虑循环的特点：可以嵌套，那么后进去的先退出，这让你想起了什么？是的，栈啊！那么我们就可以用栈来存储循环语句的信息，一切就水到渠成了。
最后，就只需要写代码，讲几个坑点：
- 算时间复杂度是不可以直接加的，要用变量找最大值，退出循环后再减回去。
- 不能开过多的栈，否则栈空间会爆掉。
- 不能发现错误后直接
break，会影响后续输入，应该标记。
#include <bits/stdc++.h>
using namespace std;
char a[1005],b[1005];
string c[105],d[1005];
int f[2000];
int numcmp(string a,string b)
{
if (a.size() > b.size() || (a.size() == b.size() && a > b)) return 1;
return 2;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t,n;
cin >> t;
while (t--)
{
memset(f,0,sizeof f);
int f2 = 1,f3 = 1,sa = 0,sb = 0,o = 0,x = 0,f4 = 1,ma = 0;
stack<string> s1;
stack<char> s2;
char e;
string k;
cin >> n >> k;
if (k[2] == '1')
{
x = 0;
}
else
{
x = 0;
for (int i = 4;i < k.size() - 1;i++)
{
x = x * 10 + (k[i] - '0');
}
}
for (int i = 1;i <= n;i++)
{
cin >> a[i];
if (a[i] == 'F')
{
sa++;
cin >> b[i] >> c[i] >> d[i];
if (f[b[i]] == 0)
{
s2.push(b[i]);
f[b[i]]++;
if (c[i] != "n" && d[i] == "n" && f4)
{
o++;
ma = max(ma,o);
s1.push("F1");
}
else if (c[i] == "n" && d[i] != "n")
{
f4 = 0;
s1.push("F2");
}
else if (numcmp(c[i],d[i]) == 1)
{
f4 = 0;
s1.push("F2");
}
else
{
s1.push("F2");
}
}
else
{
f2 = 0;
}
}
if (a[i] == 'E')
{
sb++;
if (!s1.empty())
{
if (s1.top() == "F1") o--;
s1.pop();
f4 = 1;
if (!s2.empty())
{
char t = s2.top();
f[t]--;
s2.pop();
}
}
else
{
f3 = 0;
}
}
}
if (f2 == 0 || f3 == 0 || sa != sb)
{
cout << "ERR\n";
}
else if (ma == x)
{
cout << "Yes\n";
}
else
{
cout << "No\n";
}
}
return 0;
}
枚举
算法简介
枚举，是一种通过找出每一种可能的答案，来求解整个问题的算法。同时可以通过排除一些已经不可能满足要求的情况，减去需要枚举的情况数量，以提升效率。
方法解析
简单枚举，通常使用循环来实现，用伪代码来表示如下。同时，在循环内部，加上一些语句，来判断是否可行，常用的有分支语句。同时，有一些问题可以使用 \(\text{break/continue}\)，做优化。这类问题的重点，就是在优化。除了刚刚利用 \(\text{break,continue}\) 优化，可以用根号优化，通常用在判断质数，因数与倍数等等方面，对称性优化。最后就是数学方法。这些题目主要运用代数方法，把本来需要枚举的答案直接求出，效率非常高。这种题目需要很强的思考能力，不容易做对。** 但由于篇幅原因，优化部分将在下篇文章更新**。同时，枚举本身也分为循环枚举、子集枚举与排列枚举(其中子集枚举不讲)。
例题解析
三连击
题意简述
通过组合 \(1\)，\(2\)，\(......\)，\(9\) 组合出三个数，输出所有满足比例为 \(A:B:C\) 的方案，误解输出 No!!!。
思路
本题中，如果枚举每一个数位，要循环 \(9^9\) 次，通过很危险。实际上，由于比例确定，我们知道了 \(A\)，就可以推导出 \(B\) 和 \(C\)，因此只需要枚举一个三位数，即可，只需要枚举 \(987-123=864\) 次，效率极高，再标记判断是否刚好每个数码各出现一次即可。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main()
{
int a,b,c,s = 0;
cin >> a >> b >> c;
for (int x = 1;c * x <= 987;x++)
{
int i = x * a,j = x * b,k = x * c,ti = i,tj = j,tk = k,f[15] = {0},fn = 1;
while (ti != 0) f[ti % 10]++,ti /= 10;
while (tj != 0) f[tj % 10]++,tj /= 10;
while (tk != 0) f[tk % 10]++,tk /= 10;
for (int t = 1;t <= 9;t++)
{
if (f[t] != 1) fn = 0;
}
if (fn) cout << i << ' ' << j << ' ' << k << '\n',s++;
}
if (s == 0) cout << "No!!!";
return 0;
}
全排列问题
题意简述
按照字典序输出自然数 \(1\) 到 \(n\) 所有不重复的排列，即 \(n\) 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。
思路
只需要枚举每一位上的数字即可，难点在枚举层数，可以使用一个计数变量，当变量到 \(n\) 时退出循环，返回所谓的上一层。这种思路严格意义上虽然没有使用递归，但用到了回溯思想，也就是 \(\text{DFS}\)。
参考代码
#include <bits/stdc++.h>
using namespace std;
int a[1005];
bool b[1005];
int main()
{
int n,m,x = 1,s = 0;
cin >> n;
m = n;
for (int i = 1;i <= m;i++)
{
a[i] = i;
b[i] = true;
}
while (x > 0)
{
s++;
cout << s << ": ";
for (int i = 1;i <= m;i++) printf("%5d", a[i]);
puts('\n');
x = m;
while (x > 0)
{
b[a[x]] = 0;
for (int i = a[x] + 1;i <= n;i ++ )
{
if (b[i] == false)
{
a[x] = i;
b[i] = true;
break;
}
}
if (i <= n) break;
x--;
}
if (x > 0)
{
int ans = 1;
for (int i = 1;x + ans <= m && i <= n;i ++)
{
if (b[i] == 0)
{
a[x + ans] = i;
b[i] = 1;
ans++;
}
}
}
}
cout << s;
return 0;
}