#2748 时间复杂度

 

描述

输入

输出

样例输入[复制]

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

样例输出[复制]

Yes

Yes

ERR

Yes

No

Yes

Yes

ERR

提示

【输入输出样例 1 说明】

第一个程序 i 从 1 到 1 是常数复杂度。

第二个程序 x 从 1 到 n 是 n 的一次方的复杂度。

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

第四个程序二重循环， n 的平方的复杂度。

第五个程序两个一重循环， n 的一次方的复杂度。

第六个程序第一重循环正常，但第二重循环开始即终止（因为n远大于 100，100大于4）。

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

第八个程序第二重循环中的变量 x 与第一重循环中的变量重复， 出现语法错误②，输出 ERR。

【数据规模与约定】

对于 30%的数据：不存在语法错误， 数据保证小明给出的每个程序的前 L/2 行一定 为以 F 开头的语句，第 L/2+1 行至第 L 行一定为以 E 开头的语句， L<=10，若 x、 y 均 为整数， x 一定小于 y，且只有 y 有可能为 n。

对于 50%的数据：不存在语法错误， L<=100， 且若 x、 y 均为整数， x 一定小于 y， 且只有 y 有可能为 n。

对于 70%的数据：不存在语法错误， L<=100。

对于 100%的数据： L<=100。

 

 

 

 

先读入，因为离线便于判断ERR，然后再在里面提取数字进行判断，记录不能进入循环的层数，注意要理清层数之间的加减和先后关系，（要不我就一次AC了）

code：

1 #include
       
         2 #include
        
          3 #include
         
           4 using namespace std; 5 int main() { 6     int T;cin>>T; 7     while(T--) { 8         string temp_offline[200]; 9         int num_hang;string comple;10         cin>>num_hang>>comple;getchar();11         for(int i=1; i<=num_hang; i++)12             getline(cin,temp_offline[i]);13         if(num_hang%2==1) {cout<<"ERR"<<'\n';continue;}14         int num_E=0,num_F=0;15         for(int i=1; i<=num_hang; i++) {16             if(temp_offline[i][0]=='E')num_E++;17             else num_F++;18         }19         if(num_E!=num_F){cout<<"ERR"<<'\n'; continue;}        20         char stack[200],top=0;int number_alphabet[30]={
     0},flag_used=0;21         for(int i=1;i<=num_hang;i++){22             if(temp_offline[i][0]=='E'){
     //top<0 23                 number_alphabet[stack[top]-'a']=0;top--;24                 if(top<0){25                     flag_used=1;break;26                 }27             }28             if(temp_offline[i][0]=='F'){29                 if(number_alphabet[temp_offline[i][2]-'a']){30                     flag_used=1;break;31                 }32                 else{33                     number_alphabet[temp_offline[i][2]-'a']=1;34                     stack[++top]=temp_offline[i][2];35                 }36             } 37         }38         if(flag_used){39             cout<<"ERR"<<'\n';continue;40         }    41         int num_ci=0;42         if(comple[2]=='1'){num_ci=0;}43         else{44             int now=4;45             while(isdigit(comple[now])){46                 num_ci=num_ci*10+comple[now]-'0';now++;47             }48         }49         int now_ci=0,max_ci=0,depth_layer=1,which_error=0,changshu[300]={
     0};50         for(int i=1;i<=num_hang;i++){51             if(temp_offline[i][0]=='E'){52                 depth_layer--;53                 if(which_error
          
           num_right_x){81                         which_error=depth_layer;fff=1;continue;82                     }83                     if(fff)continue;84                     changshu[depth_layer]=1;85                 }86                 else if(left_n==0&&right_n){87                     now_ci++,max_ci=max(max_ci,now_ci);88                 }89                 else if((left_n&&right_n==0))90                     which_error=depth_layer;91             }92         }93         if(max_ci==num_ci)cout<<"Yes"<<'\n';else cout<<"No"<<'\n';94     }95     return 0;96 }
          
         
        
       

over