洛谷 P3952

题目描述

小明正在学习一种新的编程语言 A++，刚学会循环语句的他激动地写了好多程序并给出了他自己算出的时间复杂度，可他的编程老师实在不想一个一个检查小明的程序，于是你的机会来啦！下面请你编写程序来判断小明对他的每个程序给出的时间复杂度是否正确。

A++语言的循环结构如下：

F i x y
    循环体
E

其中F i x y表示新建变量

“E”表示循环体结束。循环体结束时，这个循环体新建的变量也被销毁。

注：本题中为了书写方便，在描述复杂度时，使用大写英文字母“O”表示通常意义下“Θ”的概念。

输入输出格式

输入格式：

输入文件第一行一个正整数

接下来每个程序的第一行包含一个正整数 $串表示这个程序的复杂度，O(1)表示常数复杂度，O(n^w)表示复杂度为n^wnw，其中w是一个小于100的正整数（输入中不包含引号），输入保证复杂度只有O(1)和O(n^w) 两种类型。$

接下来

程序行若以E开头，则表示循环体结束。

输出格式：

输出文件共

注意：即使在程序不会执行的循环体中出现了语法错误也会编译错误，要输出 ERR。

输入输出样例

输入样例#1：复制

8
2 O(1)
F i 1 1
E
2 O(n^1)
F x 1 n
E
1 O(1)
F x 1 n
4 O(n^2)
F x 5 n
F y 10 n
E
E
4 O(n^2)
F x 9 n
E
F y 2 n
E
4 O(n^1)
F x 9 n
F y n 4
E
E
4 O(1)
F y n 4
F x 9 n
E
E
4 O(n^2)
F x 1 n
F x 1 10
E
E

输出样例#1：复制

Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

说明

【输入输出样例解释1】

第一个程序

第二个程序

第三个程序有一个 F 开启循环却没有 E 结束，语法错误。

第四个程序二重循环，

第五个程序两个一重循环，

第六个程序第一重循环正常，但第二重循环开始即终止（因为

第七个程序第一重循环无法进入，故为常数复杂度。

第八个程序第二重循环中的变量

【数据规模与约定】

对于 $30\%30%的数据：不存在语法错误，数据保证小明给出的每个程序的前 L/2L/2 行一定为以 F 开头的语句，第 L/2+1L/2+1 行至第 LL 行一定为以 EE 开头的语句，L le 10L≤10，若 xx、yy 均为整数，xx 一定小于 yy，且只有 yy 有可能为 nn。$

对于 $50\%50%的数据：不存在语法错误，L le 100L≤100，且若 xx、yy 均为整数，xx 一定小于 yy，且只有 yy 有可能为 nn。$

对于 $70\%70%的数据：不存在语法错误，L le 100L≤100。$

对于 $100\%100%的数据：L le 100L≤100。$

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <string>
 5 #define inf 0x3f3f3f3f
 6 using namespace std;
 7 int T,len,Ti,tot;
 8 int shiji,f[207],se[207];
 9 bool changshu,Error;
10 char s[207];
11 
12 bool check(){
13     for(int i=1;i<=tot-1;i++)
14         if (s[tot]==s[i]) return 1;
15     return 0;
16 }
17 
18 void update(){
19     int sum=0;
20     for(int i=1;i<=tot;i++){
21         if (f[i]==inf&&se[i]!=inf){
22             shiji=max(shiji,sum);
23             return;
24         }
25         if (se[i]==inf&&f[i]!=inf) sum++;
26         if (f[i]>se[i]){
27             shiji=max(shiji,sum);
28             return;
29         }
30     }
31     shiji=max(shiji,sum);
32 }
33 
34 int main(){
35     scanf("%d",&T);
36     while(T--){
37         scanf("%d",&len);
38         Ti=0;
39         changshu=0;
40         Error=0;
41         shiji=0;
42         tot=0;
43         char ch=getchar();
44         while(ch!='O') ch=getchar();
45         ch=getchar();
46         ch=getchar();
47         if (ch=='1'){ 
48             Ti=1,changshu=1;
49             ch=getchar();
50             ch=getchar();
51         }
52         else{
53             for(;ch<'0'||ch>'9';ch=getchar());
54             for(;ch>='0'&&ch<='9';Ti=Ti*10+ch-'0',ch=getchar());
55             ch=getchar();  
56         }
57         for(int i=1;i<=len;i++){
58             ch=getchar();
59             if (ch=='F'){
60                 ch=getchar();
61                 s[++tot]=getchar();
62                 if (check()) Error=1;
63                 ch=getchar();
64                 ch=getchar();    
65                 int first=0,second=0;
66                 if (ch>='0'&&ch<='9'){
67                     for(;ch>='0'&&ch<='9';first=first*10+ch-'0',ch=getchar());
68                     f[tot]=first;
69                 }
70                 else    f[tot]=inf,ch=getchar();
71                 ch=getchar();
72                 if (ch>='0'&&ch<='9'){
73                     for(;ch>='0'&&ch<='9';second=second*10+ch-'0',ch=getchar());
74                     se[tot]=second;
75                 }
76                 else se[tot]=inf,ch=getchar();;
77             }
78             else{
79                 update();
80                 tot--;
81                 if (T!=0||i!=len)    ch=getchar();
82             }
83         }
84         if (tot!=0) Error=1;
85         if (Error) printf("ERR
");
86         else{
87             if (shiji==0&&changshu) printf("Yes
");
88             else if(shiji==Ti) printf("Yes
");
89             else printf("No
");
90         }
91     }
92 }

View Code