洛谷P3952 时间复杂度【字符串】【模拟】
題目描述
小明正在學(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)題。
- 上一篇: Django的Field(字段)
- 下一篇: Qt消息机制和事件、事件过滤