简单的模拟。
1. 题意
给定一串语句，并有变量 $x$，初始为 $0$，仅含有一下三种类型：
for n：表示循环 $n$ 次，直到与之匹配的 end。end：表示循环结束。add：将 $x$ 加一。
执行完后，如果 $x\geq2^{32}$，输出 OVERFLOW!!!，否则输出 $x$ 的值。
2. 思路
$x$ 的值就是 add 的执行次数。
我们可以在记录一个变量 $mul$，表示当前的语句将会被执行多少次。
所以碰到 add 的时候，将当前的 $x$ 加上 $mul$ 即可。
注意，这道题 $mul$ 最大会达到 $100^{5000}$，所以注意我们如果 $mul\geq 2^{32}$，就可以直接赋值为 $2^{32}$。
但是，这里又有一个问题：$mul=2^{32}$ 之后，碰上 end，我们将要 $mul$ 除以当前的循环次数，明显就错误了。
处理方法也很简单：用一个栈记录所有的 for n，然后使用前缀积 $pre$ 维护，于是退栈的时候，我们直接将当前的 $mul$ 赋值为 $pre[top-1]$ 即可。
3. 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
const ll INF = (1ll << 32) - 1;
char str[N];
int n, top;
ll x, stk[N], tmp, pre[N];
void overflow()
{
puts("OVERFLOW!!!");
exit(0);
}
int main()
{
cin >> n;
pre[0] = 1;
while (n --)
{
scanf("%s", str + 1);
if (str[1] == 'a') x += pre[top];
else if (str[1] == 'f')
{
scanf("%lld", &tmp);
stk[++ top] = tmp;
pre[top] = pre[top - 1] * tmp;
if (pre[top]) ;
}
else if (str[1] == 'e') top --;
if (pre[top] > INF) pre[top] = INF + 1;
if (x > INF) overflow();
}
cout << x << endl;
return 0;
}
|