博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
【NOIP2017】时间复杂度
阅读量:5457 次
发布时间:2019-06-15

本文共 2170 字,大约阅读时间需要 7 分钟。

本题在洛谷上的链接:


 

堪称史上最恶心的模拟题!花了我几乎一天时间才调出来。。。

思路没啥好说的,开栈模拟即可,细节说一说。

1、每次处理一个新的程序时,将所有该初始化的都初始化,这点估计都能想到。

2、关于读入语句,可以一次读一行,也可以分开读,建议分成三个变量读,我用的一次读一行,坑死了!不过趁机学了一下c++关于读入行的知识,cin.getline(char*,int)用来操作字符数组,需要指定读入字符串大小,getline(istream,string)用来操作字符串,从指定流中读取一行。非常坑的一点,cin读字符串的时候,并不会读换行符,如果在此之后紧接着用getline读了一行,会什么也读不到,需要手动用getchar()把换行符杀掉。

3、如果遇到语法错误,别急着跳出,还要把剩下的读完。这个坑了我好久,最后把读入的全输出才发现。。。

剩下的自己看代码吧,估计也没耐心看,还是自己写慢慢调最靠谱。。。

1 #include 
2 #include
3 #include
4 #include
5 #include
6 7 using namespace std; 8 9 int vis[130];10 11 stack
s, s2, s3;12 13 int main() {14 int t, l;15 string cpx, com;16 cin >> t;17 while (t--) {18 int flag = 1, now = 0, ans = 0;19 memset(vis, 0, sizeof(vis));20 while (!s.empty()) s.pop();21 while (!s2.empty()) s2.pop();22 while (!s3.empty()) s3.pop();23 cin >> l >> cpx;24 getchar();25 for (int i = 1; i <= l; ++i) {26 getline(cin, com);27 if (!flag) continue;28 if (com[0] == 'E') {29 if (s.empty()) {30 flag = 0;31 continue;32 }33 else {34 if (s3.empty()) {35 if (!s2.empty() && s.top() == s2.top()) s2.pop();36 else --now;37 } else if (s3.top() == s.top()) s3.pop();38 vis[(int)s.top()] = 0;39 s.pop();40 }41 } else {42 char x = com[2];43 if (vis[(int)x]) {44 flag = 0;45 continue;46 }47 else {48 vis[(int)x] = 1;49 s.push(x);50 }51 int a = 0, b = 0, p = 4;52 if (com[p] == 'n') a = 10005, ++p;53 else while (com[p] != ' ')54 a = a * 10 + com[p++] - '0';55 ++p;56 if (com[p] == 'n') b = 10005;57 else while (com[p])58 b = b * 10 + com[p++] - '0';59 if (a > b) s3.push(x);60 if (a < b && a < 10005 && b < 10005 && s3.empty())61 s2.push(x);62 if (a < b && b == 10005 && s3.empty()) ++now;63 ans = max(ans, now);64 }65 }66 if (!flag || !s.empty()) {67 printf("ERR\n");68 continue;69 }70 if (cpx[2] == '1' && cpx[3] == ')') {71 if (!ans) printf("Yes\n");72 else printf("No\n");73 } else {74 int aans = 0, p = 4;75 while (cpx[p] != ')')76 aans = aans * 10 + cpx[p++] - '0';77 if (aans == ans) printf("Yes\n");78 else printf("No\n");79 }80 }81 return 0;82 }
AC代码

 

转载于:https://www.cnblogs.com/Mr94Kevin/p/9812771.html

你可能感兴趣的文章
【BZOJ1803】Spoj1487 Query on a tree III 主席树+DFS序
查看>>
jQuery 遍历 - map() 方法
查看>>
jQuery事件绑定、解绑、命名空间
查看>>
C#类,对象,构造方法
查看>>
学习笔记: AOP面向切面编程和C#多种实现
查看>>
学习笔记: 特性Attribute详解,应用封装
查看>>
java的垃圾回收方法finalize()
查看>>
Android NDK构建资料
查看>>
Linux搭建Scrapy爬虫集成开发环境
查看>>
LeetCode(21)题解:Merge Two Sorted Lists
查看>>
Ubuntu 16.04 samba 配置
查看>>
Python——文件操作
查看>>
OPENCV学习笔记2-3_图像遍历(迭代器)
查看>>
DEM转换为Features
查看>>
会计简要学习
查看>>
jquery用户自定义选择器及选择器高级用法实验
查看>>
js学习笔记3:with语句的使用
查看>>
MFC_1.2 消息映射宏 数据绑定和交换
查看>>
抽象工厂模式
查看>>
Android中Button
查看>>