• 欢迎光临~

P2186 小Z的栈函数(毒瘤)

开发技术 开发技术 2022-07-31 次浏览

我们今天来看一个有关于栈的神仙毒瘤题,他就是洛谷的P2186小Z的栈函数,我还是想像以前一样爆踩,可惜结果又又又把我的脸打得生疼,与上一篇一模一样,先来看题

题目描述

小 Z 最近发现了一个神奇的机器,这个机器的所有操作都是通过维护一个栈来完成的,它支持如下 11 个操作:

  • NUM x:栈顶放入 x。
  • POP:抛弃栈顶元素。
  • INV:将栈顶元素取出,然后放入它的相反数。
  • DUP:再放入一个和栈顶元素相同的数。
  • SWP:交换栈顶的两个元素。
  • ADD:取出栈顶的两个元素,两元素相加,所得结果放入栈内。
  • SUB:取出栈顶的两个元素,第二个元素减去第一个元素,所得结果放入栈内。
  • MUL:取出栈顶的两个元素,两元素相乘,所得结果放入栈内。
  • DIV:取出栈顶的两个元素,第二个元素整除以第一个元素,所得结果放入栈内。
  • MOD:取出栈顶的两个元素,第二个元素取模以第一个元素,所得结果放入栈内。
  • END:结束这个程序。

 

然后,小 Z 用上面的 11 种操作写了一个一元函数 f(x)。x 就是放入栈里面第一个初始元素。然后经过这个函数的一系列操作,当函数结束的时候,正常情况下,栈里面会

有唯一的一个元素。剩下的这个元素就作为函数 f(x) 的返回值。

小 Z 有 n 个询问,询问每个值 x 经过上述函数所映射出的 f(x) 是多少。但是这个由于机器太老了,跑起东西来太慢了,小 Z 又是一个急性子,所以请你们写一个程序,来帮

助小 Z 计算他查询的 f(x)。

还有,由于这台机器太破了,所以如果运算过程中有数字的绝对值大于 1000000000,机器将产生故障。

输入格式

输入首先有若干行,仅包含上述 11 个操作,用来描述函数 f(x) 的操作,函数的结束保证以 END 结尾.

接下来有一个整数,表示询问的个数 n。

接下来 n 行,每行一个整数 x,表示询问 f(x) 的值。

输入数据不保证合法。

输出格式

输出 n 行,每行表示一个询问的结果。按如下规则输出:

  • 如果最后栈内不是一个元素,输出 ERROR
  • 如果运算过程中有数字的绝对值大于 1000000000,输出 ERROR
  • 如果输入数据不合法,导致中途退出,输出 ERROR
  • 否则输出对应的 f(x)

输入输出样例

输入 #1
NUM 600000000
ADD
END
3
0
600000000
1
输出 #1
600000000
ERROR
600000001

说明/提示

数据规模与约定

对于全部测试点,保证函数的操作步数不超过 2000,1n2000,x10^9。

我滴天,乍一看吓一跳,小Z的要求还真多,我上一回的代码栽到“破机器”上了,一输入,栈直接爆炸,测试点全WA,我真是服了

P2186 小Z的栈函数(毒瘤)

(AC之路)

非常真实

继续正题,那么这道题的正确做法是什么的呢,我在绞尽脑汁的思考下(在大佬的帮助下)我终于破解了这道题。

看一下过程:

我们先把不合法的例子都给他列出来:

1.取出一个或两个元素时栈内元素不够

2.除和mod的时候除以或mod了0

3.运算过程中有数字的绝对值大于1000000000

4.最后栈内是多个元素

知道了就好了,挨个排除就完了,代码还是能过的

代码:

  1 #include<bits/stdc++.h>
  2 using namespace std;
  3 inline void read(long long &x) {
  4     x=0;
  5     long long p=1;
  6     char c=getchar();
  7     while(!isdigit(c)) {
  8         if(c=='-')p=-1;
  9         c=getchar();
 10     }
 11     while(isdigit(c)) {
 12         x=(x<<1)+(x<<3)+(c^'0');
 13         c=getchar();
 14     }
 15     x*=p;
 16 }
 17 struct node {
 18     string s;
 19     long long x;
 20 } e[2100];
 21 int cnt;
 22 string c;
 23 void fun(long long x) {
 24     stack<long long>sta;
 25     if(abs(x)>1000000000) {
 26         printf("ERRORn");
 27         return ;
 28     }
 29     sta.push(x);
 30     for(int i=1; i<=cnt; i++) {
 31         if(e[i].s=="NUM") {
 32             if(abs(e[i].x)>1000000000) {
 33                 printf("ERRORn");
 34                 return ;
 35             }
 36             sta.push(e[i].x);
 37         } else if(e[i].s=="POP") {
 38             if(sta.empty()) {
 39                 printf("ERRORn");
 40                 return ;
 41             }
 42             sta.pop();
 43         } else if(e[i].s=="INV") {
 44             if(sta.empty()) {
 45                 printf("ERRORn");
 46                 return ;
 47             }
 48             long long k=sta.top();
 49             sta.pop();
 50             sta.push(-k);
 51         } else if(e[i].s=="DUP") {
 52             if(sta.empty()) {
 53                 printf("ERRORn");
 54                 return ;
 55             }
 56             sta.push(sta.top());
 57         } else if(e[i].s=="SWP") {
 58             if(sta.size()<2) {
 59                 printf("ERRORn");
 60                 return ;
 61             }
 62             long long tmp=sta.top();
 63             sta.pop();
 64             long long tmpp=sta.top();
 65             sta.pop();
 66             sta.push(tmp);
 67             sta.push(tmpp);
 68         } else if(e[i].s=="ADD") {
 69             if(sta.size()<2) {
 70                 printf("ERRORn");
 71                 return;
 72             }
 73             long long tmp=sta.top();
 74             sta.pop();
 75             long long tmpp=sta.top();
 76             sta.pop();
 77             if(abs(tmpp+tmp)>1000000000) {
 78                 printf("ERRORn");
 79                 return;
 80             }
 81             sta.push(tmp+tmpp);
 82         } else if(e[i].s=="SUB") {
 83             if(sta.size()<2) {
 84                 printf("ERRORn");
 85                 return;
 86             }
 87             long long tmp=sta.top();
 88             sta.pop();
 89             long long tmpp=sta.top();
 90             sta.pop();
 91             if(abs(tmpp-tmp)>1000000000) {
 92                 printf("ERRORn");
 93                 return;
 94             }
 95             sta.push(tmpp-tmp);
 96         } else if(e[i].s=="MUL") {
 97             if(sta.size()<2) {
 98                 printf("ERRORn");
 99                 return;
100             }
101             long long tmp=sta.top();
102             sta.pop();
103             long long tmpp=sta.top();
104             sta.pop();
105             if(abs(tmpp*tmp)>1000000000) {
106                 printf("ERRORn");
107                 return;
108             }
109             sta.push(tmp*tmpp);
110         } else if(e[i].s=="DIV") {
111             if(sta.size()<2) {
112                 printf("ERRORn");
113                 return;
114             }
115             long long tmp=sta.top();
116             sta.pop();
117             long long tmpp=sta.top();
118             sta.pop();
119             if(tmp==0) {
120                 printf("ERRORn");
121                 return;
122             }
123             if(abs(tmpp/tmp)>1000000000) {
124                 printf("ERRORn");
125                 return;
126             }
127             sta.push(tmpp/tmp);
128         } else if(e[i].s=="MOD") {
129             if(sta.size()<2) {
130                 printf("ERRORn");
131                 return;
132             }
133             long long tmp=sta.top();
134             sta.pop();
135             long long tmpp=sta.top();
136             sta.pop();
137             if(abs(tmpp%tmp)>1000000000) {
138                 printf("ERRORn");
139                 return;
140             }
141             sta.push(tmpp%tmp);
142         }
143     }
144     if(sta.size()==1)printf("%lldn",sta.top());
145     else printf("ERRORn");
146 }
147 long long n;
148 int main() {
149     while(cin>>c) {
150         if(c[0]=='E')break;
151         cnt++;
152         e[cnt].s=c;
153         if(c=="NUM") {
154             long long x;
155             read(x);
156             e[cnt].x=x;
157         }
158     }
159     read(n);
160     for(int i=1; i<=n; i++) {
161         long long x;
162         read(x);
163         fun(x);
164     }
165     return 0;
166 }

还算好~~

CSDN博客

P2186 小Z的栈函数(毒瘤)

程序员灯塔
转载请注明原文链接:P2186 小Z的栈函数(毒瘤)
喜欢 (0)