Luogu P3952 时间复杂度

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

新老客户大回馈,云服务器低至5折

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

链接: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 }

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:在Visual Studio中使用Debug Visualizers在C++中实现对原始类的

下一篇:新博客开通啦!