Description

小明正在學習一種新的編程語言 A++，剛學會循環語句的他激動地寫了好多程序并給出了他自己算出的時間復雜度，可他的編程老師實在不想一個一個檢查小明的程序，于是你的機會來啦！下面請你編寫程序來判斷小明對他的每個程序給出的時間復雜度是否正確。A++語言的循環結構如下：

其中“ F i x y ”表示新建變量 i （變量 i 不可與未被銷毀的變量重名）并初始化為 x，然后判斷 i 和 y 的大小關系，若 i 小于等于 y 則進入循環，否則不進入。每次循環結束后 i 都會被修改成 i +1，一旦 i 大于 y 終止循環。x 和 y 可以是正整數（x 和 y 的大小關系不定） 或變量 n。n 是一個表示數據規模的變量，在時間復雜度計算中需保留該變量而不能將其視為常數，該數 遠大于 100?！?E ”表示循環體結束。循環體結束時，這個循環體新建的變量也被銷毀。注：本題中為了書寫方便，在描述復雜度時，使用大寫英文字母“O”表示通常意義下“Θ”的概念。

Input

輸入文件第一行一個正整數 t，表示有 t（t ≤ 10）個程序需要計算時間復雜度。每個程序我們只需抽取其中 “F i x y” ” 和“ “E” ”即可計算時間復雜度 。 注意： 循環結構允許嵌套 。接下來每個程序的第一行包含一個正整數 L 和一個字符串，L 代表程序行數，字符串表示這個程序的復雜度，“O(1)”表示常數復雜度，“O(n^w)”表示復雜度為n^w ，其中w是一個小于100的正整數（輸入中不包含引號），輸入保證復雜度只有O(1)和O(n^w)兩種類型。接下來 L 行代表程序中循環結構中的“F i x y”或者 “E”。程序行若以“F”開頭，表示進入一個循環，之后有空格分離的三個字符（串）i x y，其中 i 是一個小寫字母（保證不為“n”），表示新建的變量名，x 和 y 可能是正整數或n ，已知若為正整數則一定小于 100。程序行若以“E”開頭，則表示循環體結束。

Output

輸出文件共 t 行，對應輸入的 t 個程序，每行輸出“Yes”或“No”或者“ERR”（輸出中不包含引號），若程序實際復雜度與輸入給出的復雜度一致則輸出“Yes”，不一致則輸出“No”，若程序有語法錯誤（其中語法錯誤只有: ① F 和 E 不匹配 ②新建的變量與已經存在但未被銷毀的變量重復兩種情況），則輸出“ERR”。注意：即使在程序不會執行的循環體中出現了語法錯誤也會編譯錯誤，要輸出“ERR”。

Sample Input

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

Sample Output

Yes
Yes
ERR
Yes
No
Yes
Yes
ERR

【輸入輸出樣例 1 說明】

第一個程序 i 從 1 到 1 是常數復雜度。
第二個程序 x 從 1 到 n 是 n 的一次方的復雜度。
第三個程序有一個 F 開啟循環卻沒有 E 結束，語法錯誤。
第四個程序二重循環，n 的平方的復雜度。
第五個程序兩個一重循環，n 的一次方的復雜度。
第六個程序第一重循環正常，但第二重循環開始即終止（因為n遠大于100，100大于4）。
第七個程序第一重循環無法進入，故為常數復雜度。
第八個程序第二重循環中的變量 x 與第一重循環中的變量重復，出現語法錯誤②，輸出ERR。

Data Constraint

對于 30%的數據：不存在語法錯誤，數據保證小明給出的每個程序的前 L/2 行一定為以 F 開頭的語句，第 L/2+1 行至第 L 行一定為以 E 開頭的語句，L<=10，若 x、y 均為整數，x 一定小于 y，且只有 y 有可能為 n。
對于 50%的數據：不存在語法錯誤，L<=100，且若 x、y 均為整數，x 一定小于 y，且只有 y 有可能為 n。
對于 70%的數據：不存在語法錯誤，L<=100。
對于 100%的數據：L<=100。

Solution

• 這題直接模擬，注意一些細節即可。

• 比如當循環時 x>y 要標記一下啊。

Code

#include<cstdio> #include<cstring> using namespace std; const int N=101,inf=1e9; int st[N],val[N],top; bool bz[N]; int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } int get() {char ch=getchar();while((ch<'0' || ch>'9') && ch!='n') ch=getchar();if(ch=='n') return inf;int ret=ch-'0';ch=getchar();while(ch>='0' && ch<='9') ret=ret*10+ch-'0',ch=getchar();return ret; } void readln() {char ch=getchar();while(ch!='O' && ch!='F' && ch!='E') ch=getchar();if(ch=='O'){getchar(),getchar();}elseif(ch=='F'){getchar(),getchar();get(),get();} } int main() {int T=read();while(T--){int n=read();if(n&1){printf("ERR\n");for(int i=0;i<=n;i++) readln();continue;}getchar(),getchar();char s=getchar();int t=0,pd=top=0,mx=0;memset(bz,false,sizeof(bz));memset(st,0,sizeof(st));memset(val,0,sizeof(val));if(s=='n'){while(s<'0' || s>'9') s=getchar();while(s>='0' && s<='9') t=t*10+s-'0',s=getchar();}else s='0';for(int i=1;i<=n;i++){s=getchar();while(s!='F' && s!='E') s=getchar();if(s=='E'){bz[val[top--]]=false;if(top<0){for(int j=i+1;j<=n;j++) readln();pd=2;break;}continue;}while(s<'a' || s>'z') s=getchar();if(bz[s-'a'+1]){for(int j=i+1;j<=n;j++) readln();pd=2;break;}bz[val[top+1]=s-'a'+1]=true;int x=get(),y=get();if(x>y){st[++top]=-1;continue;}if((x==inf && y==inf) || (x<=100 && y<=100) || st[top]<0){st[top+1]=st[top];top++;}else{st[top+1]=st[top]+1;top++;if(st[top]>mx) mx=st[top];}}if(pd==2 || top>0){printf("ERR\n");continue;}if(mx==t) printf("Yes\n"); else printf("No\n");}return 0; } 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的JZOJ 5474. 【NOIP2017提高组正式赛】时间复杂度的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。