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

A++語言的循環結構如下：

F i x y循環體 E

其中F i x y表示新建變量 ii（變量 ii 不可與未被銷毀的變量重名）并初始化為 xx， 然后判斷 ii 和 yy 的大小關系，若 ii 小于等于 yy 則進入循環，否則不進入。每次循環結束后 ii 都會被修改成 i +1i+1，一旦 ii 大于 yy 終止循環。

xx 和 yy 可以是正整數（xx 和 yy 的大小關系不定）或變量 nn。nn 是一個表示數據規模的變量，在時間復雜度計算中需保留該變量而不能將其視為常數，該數遠大于 100100。

“E”表示循環體結束。循環體結束時，這個循環體新建的變量也被銷毀。

注：本題中為了書寫方便，在描述復雜度時，使用大寫英文字母“O”表示通常意義下“Θ”的概念。

輸入格式
輸入文件第一行一個正整數 tt，表示有 tt（t \le 10t≤10）個程序需要計算時間復雜度。 每個程序我們只需抽取其中 F i x y和E即可計算時間復雜度。注意：循環結構 允許嵌套。

接下來每個程序的第一行包含一個正整數 LL 和一個字符串，LL 代表程序行數，字符 串表示這個程序的復雜度，O(1)表示常數復雜度，O(n^{w)表示復雜度為n}wn
w
，其 中w是一個小于100的正整數（輸入中不包含引號），輸入保證復雜度只有O(1)和O(n^w) 兩種類型。

接下來 LL 行代表程序中循環結構中的F i x y或者 E。 程序行若以F開頭，表示進入一個循環，之后有空格分離的三個字符（串）i x y， 其中 ii 是一個小寫字母（保證不為nn），表示新建的變量名，xx 和 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 是常數復雜度。

第二個程序 xx 從 1 到 nn 是 nn 的一次方的復雜度。

第三個程序有一個 F 開啟循環卻沒有 E 結束，語法錯誤。

第四個程序二重循環，nn 的平方的復雜度。

第五個程序兩個一重循環，nn 的一次方的復雜度。

第六個程序第一重循環正常，但第二重循環開始即終止（因為nn遠大于100，100大于4）。

第七個程序第一重循環無法進入，故為常數復雜度。

第八個程序第二重循環中的變量 xx 與第一重循環中的變量重復，出現語法錯誤②，輸出 ERR。

【數據規模與約定】

對于 30%30%的數據：不存在語法錯誤，數據保證小明給出的每個程序的前 L/2L/2 行一定為以 F 開頭的語句，第 L/2+1L/2+1 行至第 LL 行一定為以 EE 開頭的語句，L \le 10L≤10，若 xx、yy 均 為整數，xx 一定小于 yy，且只有 yy 有可能為 nn。

對于 50%50%的數據：不存在語法錯誤，L \le 100L≤100，且若 xx、yy 均為整數，xx 一定小于 yy， 且只有 yy 有可能為 nn。

對于 70%70%的數據：不存在語法錯誤，L \le 100L≤100。

對于 100%100%的數據：L \le 100L≤100。

/*
本題首先要統一使用O（n^m）的形式來表達時間復雜度，O(1) =O(n^0).
每一條F語句都可以算出一個m值。
我們可以發現，這些F語句與E的配對類似我們遇到的括號匹配問題。
那么我們就把它當做括號匹配吧：
我們需要維護一個類似棧的東東.

同時明確語法錯誤的情況：
1.F 與 E的個數不匹配
2.E開頭，即E之前沒有與之匹配的F
3.循環沒有結束在同一個循環體F里面用相同的變量

然后要明確每條F語句需要記錄的東西：

1.變量名，因為后面要根據它來判斷語法是否錯誤
2.m值
*/
AC_code:

#include <bits/stdc++.h> #include <sstream> using namespace std; typedef pair<string,int>pr; const int MAXN = 105; pr st[MAXN]; int t; int getNum(string s)//字符串中提取數字 {stringstream sst(s);int num;sst>>num;return num; } int getTime(string s) //得到給的復雜度，即m值 {if(s == "O(1)") return 0;int pos = s.find('^');s = s.substr(pos+1);return getNum(s); } bool isExit(string s)//判斷前面沒有結束的F中是否存在變量s {for(int i = 1; i <= t; i++){if(s == st[i].first)return true;}return false; } int getNowTime(string s1,string s2)//處理F語句的復雜度，返回m值，F語句沒有執行返回-1 {if(s1=="n"){if(s2=="n") return 0;else return -1;}else{if(s2=="n") return 1;else{int x = getNum(s1);int y = getNum(s2);if(x > y) return -1;}}return 0; } int main() {ios::sync_with_stdio(false);int T;cin>>T;while(T--){int n;string s;cin>>n>>s;int time = getTime(s);bool error = false;int maxTime = 0;t = 0;/*way1:cin.clear();cin.sync();*/cin.get(); //way2//cin.ignore(); //way3for(int i = 0; i < n; i++){string line;getline(cin,line);if(error) continue;string a[5];stringstream sst(line);int k = 0;while(sst>>a[++k]) {}if(isExit(a[2])){error = true;continue;}int nowTime = getNowTime(a[3],a[4]);if(t == 0)//棧為空時{if(a[1]=="F")st[++t] = make_pair(a[2],nowTime);elseerror = true;}else{if(a[1]=="E")//出棧，匹配掉一個F{--t;continue;}else{int tmp = -1;//只有當前棧頂m值有效并且當前獲得的m值有效才可累加（m!=-1）if(st[t].second>=0&&nowTime>=0)//累計m值tmp = st[t].second+nowTime;st[++t] = make_pair(a[2],tmp);}}maxTime = max(maxTime,st[t].second);//記錄最大值}if(error||t) cout<<"ERR"<<endl;else if(maxTime == time) cout<<"Yes"<<endl;else cout<<"No"<<endl;}return 0; }

總結

以上是生活随笔為你收集整理的P3952 时间复杂度（模拟）的全部內容，希望文章能夠幫你解決所遇到的問題。

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