首页 > > 程序设计 > C/C++ >

Luogu P3952 时间复杂度

2018-06-17 21:28:33来源：未知阅读 ()

无心来刷令人发指的网络流的我今天终于填好了这个万人坑……

链接：https://www.luogu.org/problemnew/show/P3952

NOIP2017原题，各大针对OIer的OJ上应该都会出现。

这是一道数据多样化的模拟题……

用标准输入边输入边判错的代码量是很恐怖的。我辛辛苦苦地尝试了接近1.5h然后爆零。（Noip当天的情况）

今天最后决定采用字符串大法。把程序存下来先一遍判错然后才开始计算。同样也可以省掉程序错误时跳过一堆输入的判断。

1 #include<stack>
2 char prog[101][100];//存放比对答案和程序
3 stack<bool> hascomp;//循环是否使复杂度爬升（判断退出循环时是否需要减当前复杂度）

判错：只有两种错误情况，可以针对性地写。

 1 bool errordeal(int &l){
 2     stack<char> varin;
 3     bool chuse[26];//变量判重
 4     memset(chuse,0,sizeof(chuse));
 5     char ch;
 6     for(int i=0;i<=l;++i){//从1开始循环，因为prog[0]放了比对用的答案
 7         switch(prog[i][0]){
 8             case'F':
 9                 sscanf(prog[i],"%*c %c",&ch);//（题面上说是一个小写字母）读变量
10                 if(chuse[ch-'a']){//变量重复
11                     printf("ERR\n");
12                     return 1;
13                 }
14                 else{
15                     varin.push(ch);
16                     chuse[ch-'a']=1;//标记
17                 }
18                 break;
19             case'E':
20                 if(varin.size()==0){//F和E不匹配
21                     printf("ERR\n");
22                     return 1;
23                 }
24                 else{
25                     chuse[varin.top()-'a']=0;
26                     varin.pop();//清除标记
27                 }
28         }
29     }
30     if(varin.size()){//如果还有循环没清完就说明少了E，仍然错误
31         printf("ERR\n");
32         return 1;
33     }
34     return 0;
35 }
36 //有错返回1，无错返回0

判错完了之后就全是合法程序了。

不满足条件（初值比上界大）循环的处理

 1 int unloopdeal(int now){//接受当前行号
 2     int need=1;//需要多少个E来结束当前循环块
 3     for(int i=now+1;;++i){
 4         switch(prog[i][0]){
 5             case'F':
 6                 ++need; 
 7                 break;
 8             case'E':
 9                 --need;
10         }
11         if(!need) return i;//为0就说明到了这个循环块的结束，返回这个结束的行号
12     }
13 }

主程序：做输入及时间复杂度的统计。

 1 int main(){
 2     int t,l,lvalue,rvalue,comp,maxcomp;
 3     //t-组数，l-行数，lv-循环的初值，rv-循环的上界，comp-当前复杂度，mc-整体复杂度
 4     //都写在这里是因为处理里面简直有够乱了
 5     char ch,vari;
 6     char ans[100];
 7     //ch-变量名，vari-判断上界和循环是n还是数字
 8     scanf("%d",&t);
 9     while(t--){
10         comp=maxcomp=0;
11         scanf("%d ",&l);
12         memset(prog,0,sizeof(prog));
13         for(int i=0;i<=l;++i) while((ch=getchar())!='\n') prog[i][strlen(prog[i])]=ch;//读入程序，顺便也读了O(balabala)
14         if(errordeal(l)) continue;//有错直接读下一组数据；这组数据已经读完
15         for(int i=1;i<=l;++i){
16             switch(prog[i][0]){
17                 case'F':
18                     sscanf(prog[i],"%*c %c ",&ch);//读变量名
19                     sscanf(prog[i],"%*c %*c %c",&vari);//检查初值
20                     if(isdigit(vari)) sscanf(prog[i],"%*c %*c%d",&lvalue);
21                     else lvalue=-1;//是数字就读，如果不是数字（就是n）做标记-1
22                     if(lvalue!=-1) sscanf(prog[i],"%*c %*c %*d %c",&vari);
23                     else sscanf(prog[i],"%*c %*c %*c %c",&vari);
24                     if(isdigit(vari)){
25                         if(lvalue!=-1) sscanf(prog[i],"%*c %*c%*d%d",&rvalue);
26                         else sscanf(prog[i],"%*c %*c %*c%d",&rvalue);
27                     } 
28                     else rvalue=-1;//和上面一个原理，但要判断初值是否为n，不然格式化字符串没法写
29                     if(lvalue==-1){
30                         if(rvalue!=-1) i=unloopdeal(i);//处理1：初值为n，上界为常数，无法进入循环
31                         else hascomp.push(0);//处理2：初值为n，上界为n，常数复杂度
32                     }
33                     else if(rvalue==-1){
34                         maxcomp=max(maxcomp,++comp);
35                         hascomp.push(1);//处理3：初值为常数，上界为n，复杂度爬升
36                     }
37                     else if(lvalue<=rvalue) hascomp.push(0);//处理4：初值为常数，上界为常数，且初值小于上界，常数复杂度
38                     else i=unloopdeal(i);//处理4：初值为常数，上界为常数，且初值大于上界，无法进入循环
39                     //无法进入循环，就跳行号
40                     break;
41                 case'E':
42                     if(hascomp.top()) --comp;
43                     hascomp.pop();//出乎意料的简单，只需要判断是否是常数复杂度，以确定减不减当前复杂度
44             }
45         }
46         if(!maxcomp) sprintf(ans,"O(1)");
47         else sprintf(ans,"O(n^%d)",maxcomp);
48         if(!strcmp(ans,prog[0])) printf("Yes\n");
49         else printf("No\n");//字符串比对，判断答案对错
50     }
51     exit(0);
52 }