[NOIP 2017]時間複雑度

タイトルの説明
明ちゃんは新しいプログラミング言語A++を勉強しています.循環文を覚えたばかりの彼は興奮してたくさんのプログラムを書いて、自分で計算した時間の複雑さを与えましたが、彼のプログラミング先生は本当に明ちゃんのプログラムをチェックしたくないので、あなたのチャンスが来ました.次に、明ちゃんが彼の各プログラムに与えた時間の複雑さが正しいかどうかを判断するためにプログラムを書いてください.
A++言語の循環構造は以下の通りである.

F i x y
       
E

そのうちF i x yは新規変数を表します ii(変数 ii 破棄されていない変数と名前を変更することはできません). xx、そして判断 ii および yy の大小関係 ii 以下 yy ループに入ります.そうしないと入りません.サイクルが終わるたびに ii 変更されます i+1 i+1,いったん ii より大きい yy ループを終了します.
xx および yy 正の整数(xx) および yy のサイズ関係が不定)または変数 nn.nn データ規模を表す変数で、時間複雑度計算では定数と見なすことなく変数を保持する必要があり、この数ははるかに大きい 100100.
「E」は、循環体が終了することを示す.ループが終了すると、このループの新しい変数も破棄されます.
注:本題では、書きやすいように、複雑さを説明する際に、大文字の「O」を使って通常の意味を表す.Θ”という形式のものになります.
にゅうしゅつりょくけいしき
入力形式:
 
ファイルの最初の行に正の整数を入力 tt,表示有 tt(tle 10 t≦10)個のプログラムは時間複雑度を計算する必要があります.各プログラムはF i x yとEを抽出するだけで時間複雑度を計算できます.注意:ループ構造はネストを許可します.
次に、各プログラムの最初の行には正の整数が含まれます. LL 文字列、LL プログラムの行数を表し、文字列はこのプログラムの複雑さを表し、O(1)は定数の複雑さを表し、O(n^w)は複雑度がn^wnwであることを表し、wは100未満の正の整数(入力には引用符を含まない)であり、入力保証複雑度はO(1)とO(n^w)のみである. 2種類です.
次の LL 行は、プログラム内の循環構造のF i x yまたは  E.プログラム行がFで始まると、1つのループに入り、その後、スペースが分離された3つの文字(列)i x yが表示されます. ii 新しい変数名、xxを表す小文字(nnでないことを保証)です. および yy 正の整数または nn ,正の整数であれば100未満であることが知られている.
プログラム行がEで始まると、循環体が終了することを示す.
 
出力フォーマット:
 
出力ファイル共 tt 行、入力に対応 tt 個のプログラムは、各行YesまたはNoまたはERR(引用符を含まない出力)を出力し、プログラムの実際の複雑度が入力から与えられた複雑度と一致すればYesを出力し、一致しなければNoを出力し、プログラムに文法エラーがある場合(構文エラーは、①FとEが一致しない②新規の変数が既に存在するが破棄されていない変数と重複する場合のみ)の場合、出力ERR .
注意:プログラムが実行されないループで構文エラーが発生してもコンパイルエラーが発生し、出力する  ERR .
 
入出力サンプル
サンプル#1を入力:  コピー

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

出力サンプル#1:  コピー

Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

説明
【入出力サンプル解釈1】
最初のプログラム ii 1から1は定数複雑度です.
2番目のプログラム xx 1から nn はい nn を選択します.
3番目のプログラムは  F  ループを開いてもない  E  終了、構文エラー.
4番目のプログラムの二重サイクル、nn の双曲線コサインを返します.
5番目のプログラムは2つの1重ループで、nn を選択します.
6番目のプログラムの第1の再サイクルは正常であるが、第2の再サイクルの開始は終了する(nnは100100より4よりはるかに大きいため).
7番目のプログラムは第1の再ループが入らないため,定数複雑度である.
8番目のプログラム第2のループの変数 xx 第一重ループの変数と重複し、構文エラー②が発生し、出力  ERR .
【データ規模と約束】
について 30%30%のデータ:構文エラーは存在せず、データは明ちゃんが与えた各プログラムの前に L/2L/2 行は必ず  F  最初の文 L/2+1L/2+1 行至第 LL 行は必ず EE 冒頭の文、Lle 10 L≦10、もし xx、yy いずれも整数、xx より小さい yy、しかも yy 可能性がある nn.
について 50%50%のデータ:構文エラーなし、Lle 100 L≦100、および xx、yy いずれも整数、xx より小さい yy、しかも yy 可能性がある nn.
について 70%70%のデータ:構文エラーは存在せず、Lle 100 L≦100.
について 100%100%のデータ:Lle 100 L≦100.
 
やっとこの問題をQQQで書きました.書いて+調整して全部で1時間半です.
以前はこのような問題を見ても怖かったです.今、問題を作る前に考えを整理して、細部を頭の中でよく考えて、紙に書いたほうがいいことに気づきました.それからやるときは変数ごとに注釈をつけます.
この問題はやっているうちに頭が混乱するのが一番怖い.
コード:

  1 #include
  2 #include
  3 #include
  4 using namespace std;
  5 int T;//     
  6 int len;//    
  7 int fzd;//         
  8 int maxn;//               
  9 struct order
 10 {
 11     int opt;//  ：1->   2->  
 12     int ch;//   
 13     int x,y;// 10000   n 
 14 }q[101];
 15 int top;
 16 int st[101]; 
 17 bool vis[101];//        
 18 bool flag[101];//              
 19 int read()
 20 {
 21     char ch=getchar(); int x=0;
 22     while((ch>'9'||ch<'0')&&ch!='n') ch=getchar();
 23     if(ch=='n') {getchar();return 10000;}    
 24     while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar();
 25     return x;
 26 }
 27 void clear()
 28 {
 29     len=fzd=maxn=top=0;
 30     memset(st,0,sizeof(st));
 31     memset(vis,0,sizeof(vis));
 32     memset(flag,0,sizeof(flag));
 33     memset(q,0,sizeof(q));
 34 }
 35 int getfzd()
 36 {
 37     char c=getchar();int x=0;
 38     while(c!='(') c=getchar();
 39     c=getchar();
 40     if(c=='1')  {c=getchar();return 0;}
 41     while(c>'9'||c<'0') c=getchar();
 42     while(c<='9'&&c>='0') x=x*10+c-'0',c=getchar();
 43     c=getchar(); return x;
 44 }
 45 bool judge()
 46 {
 47     int top=0;
 48     for(int i=1;i<=len;i++)
 49     {
 50         if(q[i].opt==1)
 51         {
 52             if(!vis[q[i].ch]) vis[st[++top]=q[i].ch]=true;
 53             else return true;
 54         }
 55         else
 56         {
 57             if(!top) return true;
 58             else vis[st[top--]]=false;
 59         } 
 60     }
 61     return top!=0;
 62 }
 63 int get()
 64 {
 65     int now=0,ans=0;
 66     int stop=0;//  x>y，              
 67     for(int i=1;i<=len;i++)
 68     {
 69         if(q[i].opt==1)
 70         {
 71             int del=q[i].y-q[i].x;
 72             if(stop) ++top;
 73             else if(del<0) stop=++top;
 74             else if(del<=100) ++top;
 75             else now++,ans=max(ans,now),flag[++top]=true;
 76         }
 77         else
 78         {
 79             if(flag[top]) now--,flag[top]=false;
 80             if(stop&&stop==top) stop=0;
 81             top--;
 82         }
 83     }
 84     return ans;
 85 }
 86 void work()
 87 {
 88     clear(); cin>>len; fzd=getfzd();
 89     for(int i=1;i<=len;i++)
 90     {
 91         char c[5]; scanf("%s",c);
 92         if(c[0]=='F')
 93         {
 94             q[i].opt=1;
 95             scanf("%s",c); q[i].ch=c[0]-'a';
 96             q[i].x=read(); q[i].y=read();
 97         }
 98         else q[i].opt=2;
 99     }
100     if(judge()) {printf("ERR
");return;}
101     maxn=get(); printf(maxn==fzd?"Yes
":"No
");
102 }
103 int main()
104 {
105     scanf("%d",&T);
106     while(T--) work();
107     return 0;
108 }

 
転載先:https://www.cnblogs.com/Slrslr/p/9588212.html