欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷 P3952 时间复杂度

程序员文章站 2024-03-19 09:08:28
...

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

做这道题的最大收获就是坚持不懈,勇往直前,这道题是一个“码力题”,不能说无脑,但绝对恶心。总共花了3h+才调出来。果然当时NOIp放弃这道题是明智的

好了,闲话放一边,我们来搞一搞这道题。

这道题思路很简单,就是模拟。t<=10和L<=100也提示了我们时间不是问题,要大胆的去模拟。我是在线判断程序是否ERR,离线判断时间复杂度计算是否正确。如果程序ERR,就标记一下,输入完之后直接结束这次循环(continue),不再进行接下来的计算。至于判断Yes和No,我先将输入的时间复杂度记录下来,自己再算一遍时间复杂度,和所给的比对,来判断Yes和No(做法很乱,请读者老爷们包容)。

这是一个基本思路,中间还有许多特判,包括:

  1. 两个ERR的判断:第一个用的栈的思想,第二个用的桶的思想

  2. 因为我是输入的字符串,所以还要将字符串中的数字扣下来,便于使用和比对

  3. 判断该层循环能否进去

  4. 有可能出现几个循环并列在同一层的情况

  5. 寻找O(n)最大循环层数,就是时间复杂度,O(1)的情况直接不考虑

这就是我的一个大致思路,具体实现可以看我的代码

#include<bits/stdc++.h>
using namespace std;
int t;
string ans[101];
bool flag[127];//虽然这是一个数组,但却只用到了flag[22]
               //flag[22]:判断该层循环能否进入。 
int flag2,tong[27];//flag2用来判断ERR 1;tong用来判断ERR 2 
int yyy,tot,a,maxx;//yyy记录当前所在循环的时间复杂度
                   //tot记录当前所在的循环 
                   //a记录输入的时间复杂度 n^w中的w 
                   //maxx记录正确的w 
bool boom[100];    //boom[i]记录第i层循环是否到过 
int main()
{
    cin>>t;
    //======输入,同时判断是否ERR 
    for(int i=1;i<=t;i++)
    {
        tot=0,flag2=0,memset(tong,0,sizeof(tong)),a=0;
        int l; cin>>l;
        string o; cin>>o;
        if(o[2]=='n')  //因为n的位置固定,所以直接判断该位置是否为n
                        //下面的求a和抠数也是同理 
        {
            a=o[4]-'0';
            if(o[5]>='0'&&o[5]<='9')
              a=a*10+o[5]-'0';
        }
        char codes[101][101];
        getchar();
        for(int j=1;j<=l;j++)
          for(int k=0;k<=10;k++)
          {
            codes[j][k]=' ';
          }
        for(int j=1;j<=l;j++)
        {
            
            gets(codes[j]);
            //=====ERR 1
            if(codes[j][0]=='F') flag2++; //栈的思想,类似于括号匹配 
            if(codes[j][0]=='E') flag2--;
            if(flag2<0) ans[i]="ERR";
            
            //=====ERR 2
            if(codes[j][0]=='F')
            {
                if(tong[codes[j][2]-'a'+1]==0)  //桶的思想
                  tong[codes[j][2]-'a'+1]=++tot; //因为循环结束后变量销毁,所以要记录循环层数 
                else
                  ans[i]="ERR";
            }
            if(codes[j][0]=='E')
            {
                for(int i=1;i<=26;i++)
                {
                    if(tong[i]==tot)  // 销毁变量 
                      tong[i]=0;
                }
                tot--;
            }
        }
        if(flag2>0) ans[i]="ERR";
        
        if(ans[i]=="ERR")  continue; //如果ERR,不执行下面的操作 
        //================ERR finish
        
        tot=0;int zzz=0;flag[22]=0;yyy=0;memset(boom,0,sizeof(boom));maxx=0;  //一定要初始化 
        for(int j=1;j<=l;j++)
        {
            if(codes[j][0]=='F')
            {
                tot++;
                if(codes[j][4]=='n'&&((codes[j][6]>'0'&&codes[j][6]<='9')||(codes[j][7]>'0'&&codes[j][7]<='9'))&&!flag[22])
                {
                    flag[22]=1;  //因为n>任何一个整数,所以该层循环无法进入 
                    zzz=tot;     //zzz记录无法进入的循环层数 
                }
                if(codes[j][4]>='0'&&codes[j][4]<='9'&&!flag[22]&&(codes[j][6]!='n'&&codes[j][7]!='n'))
                {
                    // 如果两个都是常数,那么暴力抠数,比较两个数的大小 
                    int c1=codes[j][4]-'0';
                    int c2;
                    if(codes[j][5]>='0'&&codes[j][5]<='9')
                      c1=c1*10+codes[j][5]-'0';
                    
                    if(c1<10)  
                      if(codes[j][6]>='0'&&codes[j][6]<='9')
                      {
                          c2=codes[j][6]-'0';
                          if(codes[j][7]>='0'&&codes[j][7]<='9')
                            c2=c2*10+codes[j][7]-'0';  
                      }
                    if(c1>10)
                      if(codes[j][7]>='0'&&codes[j][7]<='9')
                      {
                          c2=codes[j][7]-'0';
                          if(codes[j][8]>='0'&&codes[j][8]<='9')
                            c2=c2*10+codes[j][8]-'0';  
                      }
                    if(c1>c2)  //前面的数大于后面的数 
                    {
                        flag[22]=1;
                        zzz=tot;
                    }  
                }
                if((codes[j][6]=='n'||codes[j][7]=='n')&&codes[j][4]!='n'&&!flag[22])  //该层循环可以进去 
                {
                    if(!boom[tot])  //且没有进去过同层的循环,因为如果进去过同层的循环,那么这次循环不会影响时间复杂度 
                    {
                        boom[tot]=1; //标记 
                        yyy++;  //记录当前的时间复杂度 
                        if(yyy>maxx)  //如果yyy此时大于maxx,更新maxx 
                          maxx=yyy;
                    }
                }
                
            }
            if(codes[j][0]=='E')
            {
                if(tot==zzz)
                  flag[22]=0;  //如果之前该层循环无法进入,那么到同层的E,该层循环结束,以后的循环就可以进去了 
                if(boom[tot])
                {
                    yyy--; //如果到过这层循环,退出这层循环 
                    boom[tot]=0; //再次标记该层循环未到过,防止特判4出现 
                }
                tot--;  //层数减一 
            }
        }
        if(maxx==a)  //比较输入的时间复杂度和我们算出的正解 
          ans[i]="Yes";
        else
          ans[i]="No";  
    }
    for(int i=1;i<=t;i++)
      cout<<ans[i]<<endl;
    
    return 0;
} // 140行,完结撒花