題目描述

小明正在學(xué)習(xí)一種新的編程語(yǔ)言 A++，剛學(xué)會(huì)循環(huán)語(yǔ)句的他激動(dòng)地寫(xiě)了好多程序并 給出了他自己算出的時(shí)間復(fù)雜度，可他的編程老師實(shí)在不想一個(gè)一個(gè)檢查小明的程序， 于是你的機(jī)會(huì)來(lái)啦！下面請(qǐng)你編寫(xiě)程序來(lái)判斷小明對(duì)他的每個(gè)程序給出的時(shí)間復(fù)雜度是否正確。

A++語(yǔ)言的循環(huán)結(jié)構(gòu)如下：

F i x y循環(huán)體 E

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

xx?和?yy?可以是正整數(shù)（xx?和?yy?的大小關(guān)系不定）或變量?nn。nn?是一個(gè)表示數(shù)據(jù)規(guī)模的變量，在時(shí)間復(fù)雜度計(jì)算中需保留該變量而不能將其視為常數(shù)，該數(shù)遠(yuǎn)大于?100100。

“E”表示循環(huán)體結(jié)束。循環(huán)體結(jié)束時(shí)，這個(gè)循環(huán)體新建的變量也被銷(xiāo)毀。

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

輸入輸出格式

輸入格式：

?

輸入文件第一行一個(gè)正整數(shù)?tt，表示有?tt（t \le 10t≤10）個(gè)程序需要計(jì)算時(shí)間復(fù)雜度。 每個(gè)程序我們只需抽取其中?F i x y和E即可計(jì)算時(shí)間復(fù)雜度。注意：循環(huán)結(jié)構(gòu) 允許嵌套。

接下來(lái)每個(gè)程序的第一行包含一個(gè)正整數(shù)?LL?和一個(gè)字符串，LL?代表程序行數(shù)，字符 串表示這個(gè)程序的復(fù)雜度，O(1)表示常數(shù)復(fù)雜度，O(n^w)表示復(fù)雜度為n^wnw，其 中w是一個(gè)小于100的正整數(shù)（輸入中不包含引號(hào)），輸入保證復(fù)雜度只有O(1)和O(n^w)?兩種類(lèi)型。

接下來(lái)?LL?行代表程序中循環(huán)結(jié)構(gòu)中的F i x y或者?E。 程序行若以F開(kāi)頭，表示進(jìn)入一個(gè)循環(huán)，之后有空格分離的三個(gè)字符（串）i x y， 其中?ii?是一個(gè)小寫(xiě)字母（保證不為nn），表示新建的變量名，xx?和?yy?可能是正整數(shù)或?nn?，已知若為正整數(shù)則一定小于 100。

程序行若以E開(kāi)頭，則表示循環(huán)體結(jié)束。

?

輸出格式：

?

輸出文件共?tt?行，對(duì)應(yīng)輸入的?tt?個(gè)程序，每行輸出Yes或No或者ERR（輸出中不包含引號(hào)），若程序?qū)嶋H復(fù)雜度與輸入給出的復(fù)雜度一致則輸出Yes，不一致則輸出No，若程序有語(yǔ)法錯(cuò)誤（其中語(yǔ)法錯(cuò)誤只有: ① F 和 E 不匹配 ②新建的變量與已經(jīng)存在但未被銷(xiāo)毀的變量重復(fù)兩種情況），則輸出ERR?。

注意：即使在程序不會(huì)執(zhí)行的循環(huán)體中出現(xiàn)了語(yǔ)法錯(cuò)誤也會(huì)編譯錯(cuò)誤，要輸出?ERR。

?

輸入輸出樣例

輸入樣例#1：?復(fù)制 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：?復(fù)制 Yes Yes ERR Yes No Yes Yes ERR

說(shuō)明

【輸入輸出樣例解釋1】

第一個(gè)程序?ii?從 1 到 1 是常數(shù)復(fù)雜度。

第二個(gè)程序?xx?從 1 到?nn?是?nn?的一次方的復(fù)雜度。

第三個(gè)程序有一個(gè)?F?開(kāi)啟循環(huán)卻沒(méi)有?E?結(jié)束，語(yǔ)法錯(cuò)誤。

第四個(gè)程序二重循環(huán)，nn?的平方的復(fù)雜度。

第五個(gè)程序兩個(gè)一重循環(huán)，nn?的一次方的復(fù)雜度。

第六個(gè)程序第一重循環(huán)正常，但第二重循環(huán)開(kāi)始即終止（因?yàn)?span id="ze8trgl8bvbq" class="katex">nn遠(yuǎn)大于100，100大于4）。

第七個(gè)程序第一重循環(huán)無(wú)法進(jìn)入，故為常數(shù)復(fù)雜度。

第八個(gè)程序第二重循環(huán)中的變量?xx?與第一重循環(huán)中的變量重復(fù)，出現(xiàn)語(yǔ)法錯(cuò)誤②，輸出?ERR。

【數(shù)據(jù)規(guī)模與約定】

對(duì)于?30\%30%的數(shù)據(jù)：不存在語(yǔ)法錯(cuò)誤，數(shù)據(jù)保證小明給出的每個(gè)程序的前?L/2L/2?行一定為以?F?開(kāi)頭的語(yǔ)句，第?L/2+1L/2+1?行至第?LL?行一定為以?EE?開(kāi)頭的語(yǔ)句，L \le 10L≤10，若?xx、yy?均 為整數(shù)，xx?一定小于?yy，且只有?yy有可能為?nn。

對(duì)于?50\%50%的數(shù)據(jù)：不存在語(yǔ)法錯(cuò)誤，L \le 100L≤100，且若?xx、yy?均為整數(shù)，xx?一定小于?yy， 且只有?yy?有可能為?nn。

對(duì)于?70\%70%的數(shù)據(jù)：不存在語(yǔ)法錯(cuò)誤，L \le 100L≤100。

對(duì)于?100\%100%的數(shù)據(jù)：L \le 100L≤100。

---

如果需要Hack請(qǐng)私信@zhouyonglong或發(fā)討論，提供數(shù)據(jù)和能Hack掉的P3952或本題的AC記錄。

?

題意：

一個(gè)循環(huán)表示為$F i x y$其中$i$表示這一層循環(huán)的變量$x$表示循環(huán)開(kāi)始的值$y$表示當(dāng)變量小于等于$y$時(shí)始終執(zhí)行循環(huán)

$E$是一層循環(huán)的結(jié)束標(biāo)志。

現(xiàn)在給定一段程序判斷這段程序的復(fù)雜度和給定的是否一致。

思路：

啊我好菜。剛開(kāi)始思路不清晰對(duì)著樣例debug半天。

后來(lái)列了個(gè)表格分了情況稍微重新寫(xiě)了一次，但是情況沒(méi)有考慮全面。

ERR的情況是，E和F的個(gè)數(shù)不匹配（計(jì)數(shù)）或外層循環(huán)和內(nèi)層循環(huán)的變量名重復(fù)了（set和stack并用），比較好判斷。

當(dāng)出現(xiàn)x是數(shù)字而y是n時(shí)，這層循環(huán)對(duì)復(fù)雜度有1的貢獻(xiàn)。

當(dāng)出現(xiàn)數(shù)字?jǐn)?shù)字和nn時(shí)，這層循環(huán)對(duì)復(fù)雜度沒(méi)有貢獻(xiàn)。

當(dāng)出現(xiàn)n數(shù)字，或是x的數(shù)字比y的數(shù)字大的時(shí)候這層循環(huán)以及這層循環(huán)內(nèi)部的循環(huán)都不會(huì)進(jìn)入。

?

1 //#include<bits/stdc++.h> 2 #include<set> 3 #include<iostream> 4 #include<stdio.h> 5 #include<stdlib.h> 6 #include<cstring> 7 #include<stack> 8 #include<algorithm> 9 10 using namespace std; 11 12 int t, lines; 13 14 int getO(string s) 15 { 16 int i = 4, res = 0; 17 if(s[2] == '1')return 0; 18 while(s[i] != ')'){ 19 res *= 10; 20 res += s[i] - '0'; 21 i++; 22 } 23 return res; 24 } 25 26 int getnumber(string s) 27 { 28 int i = 0, len = s.length(); 29 int res = 0; 30 while(i < len){ 31 res *= 10; 32 res += s[i] - '0'; 33 i++; 34 } 35 return res; 36 } 37 38 int main() 39 { 40 scanf("%d", &t); 41 while(t--){ 42 scanf("%d", &lines); 43 string O; 44 cin>>O; 45 46 stack<string>v_ar; 47 set<string>var; 48 int deep = 0, now = 0; 49 bool flag = true; 50 bool allone = false; 51 int EFs = 0; 52 for(int i = 0; i < lines; i++){ 53 char ch; 54 getchar(); 55 scanf("%c", &ch); 56 if(ch == 'E'){ 57 EFs -= 1; 58 now -= 1; 59 if(!v_ar.empty()){ 60 string v = v_ar.top();v_ar.pop(); 61 var.erase(v); 62 } 63 if(!EFs){ 64 allone = false; 65 now = 0; 66 //var.clear(); 67 } 68 } 69 else if(ch == 'F'){ 70 EFs += 1; 71 string v, x, y; 72 cin>>v>>x>>y; 73 if(var.find(v) != var.end())flag = false; 74 else{ 75 var.insert(v); 76 v_ar.push(v); 77 if(x[0] >= '0' && x[0] <= '9' && y[0] == 'n'){ 78 if(!allone)now += 1; 79 deep = max(deep, now); 80 } 81 else if(x[0] == 'n' && y[0] >= '0' && y[0] <= '9' || getnumber(x) > getnumber(y))allone = true; 82 } 83 } 84 } 85 86 //cout<<deep<<endl; 87 if(EFs || !flag){ 88 printf("ERR\n"); 89 } 90 else if(getO(O) == deep){ 91 printf("Yes\n"); 92 } 93 else{ 94 printf("No\n"); 95 } 96 } 97 98 return 0; 99 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/wyboooo/p/10274334.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P3952 时间复杂度【字符串】【模拟】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。