NOIP2017 D1T2时间复杂度

这道题在考试时看到感觉与第一题放反了位置（因为我还没有看到第一题是结论题）

对于每个语句进行栈的模拟，而如果有语法错误就特判。

对于每一条for语句我们将其与栈顶元素连边，复杂度是1的我们不用考虑，如果复杂度是n我们就算他的贡献加一。

这样我们求最大复杂度就相当于求一颗子树的最大深度，当然如果这条语句不合法我们就将其整颗子树贡献算为0。

                         #include<bits/stdc++.h>

 using namespace std;

 int top;

 struct node

 {

     int to,nex;

 }e[];

 int cnt,head[];

 void add(int x,int y)

 {

     e[++cnt].to=y;e[cnt].nex=head[x];head[x]=cnt;

 }

 int inf=1e9;

 struct poin

 {

     int l,r,id;

 }a[];

 stack<poin>qq;

 int dfs(int x)

 {

     int pre=;

     int ma=;

     if(a[x].l!=inf&&a[x].r==inf)pre=;

     if(a[x].l>a[x].r)return ;

     for(int i=head[x];i;i=e[i].nex)

     {

         ma=max(ma,dfs(e[i].to));

     }

     return ma+pre;

 }

 char s[];

 bool b[];

 int q[];

 int main()

 {

     int t,n;

     scanf("%d",&t);

     while(t--)

     {

         cnt=;

         memset(head,,sizeof(head));

         memset(b,,sizeof(b));

         memset(q,,sizeof(q));

         scanf("%d",&n);top=;while(!qq.empty())qq.pop();

         scanf("%s",s);int x=;bool flag=;

         if(s[]>=''&&s[]<='')

         for(int i=;s[i]>=''&&s[i]<='';++i)

         x=x*+s[i]-'';

         else{

             for(int i=;s[i]>=''&&s[i]<='';++i)

             x=x*+s[i]-'';

         }

         if(s[]!='n')x=;

         for(int i=;i<=n;++i)

         {

             scanf("%s",&s);

             if(s[]=='F')

             {

                 scanf("%s",&s);int d=s[]-'a'+;

                 if(b[d]){

                     flag=;

                 }int u=,v=;int w=,z=;

                 b[d]=;q[++top]=d;

                 scanf("%s",&s);

                 if(s[]=='n')w=inf;

                 else{while(s[u]>=''&&s[u]<='')w=w*+s[u]-'',++u;}

                 scanf("%s",&s);

                 if(s[]=='n')z=inf;

                 else{while(s[v]>=''&&s[v]<='')z=z*+s[v]-'',++v;}

                 a[i].l=w;a[i].r=z;a[i].id=i;

                 if(qq.empty())

                 add(,i);

                 else add(qq.top().id,i);

                 qq.push(a[i]);

             }

             else

             {

                 if(qq.empty())flag=;

                 else{b[q[top]]=;--top;qq.pop();}

             }

         }

         if(!qq.empty())flag=;

         if(flag){

             puts("ERR");continue;

         }

         int ans=dfs();

         if(ans!=x)puts("No");

         else puts("Yes");

     }

     return ;

 }

考试时我没有求max而是算的sum

还好noip数据水让我混了90分，谢天谢地。

巴特西

NOIP2017 D1T2时间复杂度

最新文章

热门文章