（有一個月沒有寫簡書了......）
(這次終于開始拿Markdown寫了，富文本可以走開了)
說說為什么我要寫這道題...
因為...dalao們寫的都是兩百多行的代碼看不懂
于是我決定自己寫一篇...
也是第一次拿markdown寫
錯誤連篇請原諒
原諒我可好 我傲慢的青春
題目索引 [NOIP 2017 Day1 T2 時間復(fù)雜度]
LOJ.ac #2315
loj老卡呀狼，可能我家網(wǎng)不好
題面如下
都給我老老實實看題 巡验，[不想看題的戳這][1]
題目描述
給出了他自己算出的時間復(fù)雜度，可他的編程老師實在不想一個一個檢查小明的程序哼审，于是你的機會來啦谐腰！下面請你編寫程序來判斷小明對他的每個程序給出的時間復(fù)雜度是否正確。 A++ 語言的循環(huán)結(jié)構(gòu)如下：
F i x y
循環(huán)體
E
然后判斷 i 和 y 的大小關(guān)系涩盾，若 i 小于等于 y 則進入循環(huán)十气，否則不進入。每次循環(huán)結(jié)束后 i 都會被修改成 i+1春霍，一旦 i 大于 y 終止循環(huán)砸西。 x 和 y 可以是正整數(shù)（x 和 y 的大小關(guān)系不定）或變量 n。n 是一個表示數(shù)據(jù)規(guī)模的變量，在時間復(fù)雜度計算中需保留該變量而不能將其視為常數(shù)芹枷，該數(shù)遠大于 100衅疙。 E表示循環(huán)體結(jié)束。循環(huán)體結(jié)束時鸳慈，這個循環(huán)體新建的變量也被銷毀饱溢。
注：本題中為了書寫方便，在描述復(fù)雜度時走芋，使用大寫英文字母 O 表示通常意義下 Θ的概念理朋。
輸入格式
輸入文件第一行一個正整數(shù) t，表示有 t(t≤10)個程序需要計算時間復(fù)雜度绿聘。
每個程序我們只需抽取其中 F i x y和E即可計算時間復(fù)雜度嗽上。注意：循環(huán)結(jié)構(gòu)允許嵌套。
接下來每個程序的第一行包含一個正整數(shù) L 和一個字符串熄攘，L 代表程序行數(shù)兽愤，字符串表示這個程序的復(fù)雜度，O(1)表示常數(shù)復(fù)雜度挪圾，O(n^w) 表示復(fù)雜度為 n^w浅萧，其中 w 是一個小于 100 的正整數(shù)（輸入中不包含引號），輸入保證復(fù)雜度只有 O(1) 和 O(n^w) 兩種類型哲思。
接下來 L 行代表程序中循環(huán)結(jié)構(gòu)中的 F i x y 或者 E洼畅。 程序行若以 F 開頭，表示進入一個循環(huán)棚赔，之后有空格分離的三個字符（串）i x y帝簇，其中 iii 是一個小寫字母（保證不為 n ），表示新建的變量名靠益，x 和 y 可能是正整數(shù)或 n 丧肴，已知若為正整數(shù)則一定小于 100。 程序行若以 E開頭胧后，則表示循環(huán)體結(jié)束芋浮。
樣例
樣例輸入(好心的我已經(jīng)tab好了)
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
樣例輸出
Yes
Yes
ERR
Yes
No
Yes
Yes
ERR
樣例說明
第一個程序 i 從1 到 1 是常數(shù)復(fù)雜度。
第二個程序 x 從 1 到 n 是 n 的一次方的復(fù)雜度壳快。
第三個程序有一個 F 開啟循環(huán)卻沒有E結(jié)束纸巷，語法錯誤。
第四個程序二重循環(huán)眶痰，n的平方的復(fù)雜度瘤旨。
第五個程序兩個一重循環(huán)，n 的一次方的復(fù)雜度凛驮。
第六個程序第一重循環(huán)正常裆站，但第二重循環(huán)開始即終止（因為 n 遠大于 100条辟，100 大于 4）黔夭。
第七個程序第一重循環(huán)無法進入宏胯，故為常數(shù)復(fù)雜度。
第八個程序第二重循環(huán)中的變量 x 與第一重循環(huán)中的變量重復(fù)本姥，出現(xiàn)語法錯誤②肩袍，輸出 ERR。
數(shù)據(jù)范圍與提示
1.對于 30%的數(shù)據(jù)：不存在語法錯誤婚惫，數(shù)據(jù)保證小明給出的每個程序的前 L/2 行一定為以 F 開頭的語句氛赐，第L/2+1 行至第 L 行一定為以 E 開頭的語句，L≤10先舷，若 x,y均為整數(shù)艰管，x 一定小于 y，且只有 y 有可能為 n蒋川。
2.對于 50% 的數(shù)據(jù)：不存在語法錯誤牲芋，L≤100，且若 x,y均為整數(shù)捺球，x 一定小于 y缸浦，且只有 y 有可能為 n。
3.對于 70% 的數(shù)據(jù)：不存在語法錯誤氮兵，L≤100裂逐。
4.對于 100% 的數(shù)據(jù)：t≤10,L≤100。
......(話說題目好長真的懶得看)
題解...
題目分析
很明顯這是一道不需要智商但是打起來賊惡心的模擬題
我們先來看一看題發(fā)現(xiàn)它的語言是A++而且只有F循環(huán)結(jié)構(gòu)
根據(jù)我們的常識知道這里多半要壓棧因為我們需要知道當(dāng)前的F循環(huán)是哪一個
然后判斷一下有沒有語法錯誤就好啦Ｆ弧２犯摺！
好了說正經(jīng)的南片，五步寫完
1.數(shù)據(jù)準備
int T,l,on,Fnum,Maxon;//T程序數(shù)篙悯，l程序行數(shù)，on當(dāng)前復(fù)雜度铃绒，F(xiàn)num當(dāng)前程序F-E個數(shù)鸽照，Maxon當(dāng)前程序最大復(fù)雜度
string On,Ans;//輸入，答案
bool isError;//當(dāng)前程序錯誤開關(guān)
const int INF=-99999;//進不去的循環(huán)
2.準備一個函數(shù)颠悬，檢查當(dāng)前復(fù)雜度與期望復(fù)雜度是否一致
注意： 期望 O(1)即為O(n^0)矮燎，w=0
(string) On 為期望復(fù)雜度（輸入）
然后機智的我們可以發(fā)現(xiàn)在
(string) On 中期望復(fù)雜度只需要 取出(On[4]~On[On.length()-1])所表示數(shù)就好了
最后 return r==w;
bool checkRight(int w){// 檢查復(fù)雜度是否一致
if(w==0&&On=="O(1)") return 1;
else {
int r=0;
for(int i=4;i<On.length()-1;i++) {//這個for實際上就是從（string）On里取出數(shù)字來
r*=10;
r+=On[i]-'0';
}
return r==w;
}
}
3.再準備一個函數(shù)，獲取某個F循環(huán)的復(fù)雜度
注意：一個F循環(huán)只有可能存在三種復(fù)雜度：0 , 1 , INF
INF意思看上邊
這里我們簡單記 F(s,e)為從 s一直循環(huán)加1到 e 的復(fù)雜度
設(shè)const_為某常數(shù)（據(jù)題const_<=100）
則
when s=e=n 時 赔癌， 循環(huán)可以進入一次故 F(n,n)=0;
when s=const_,e=n 時 诞外， 循環(huán)需要走n次(因為n遠大于const_) ,F(const_,n)=1
when s=n,e=const_ 時 , 循環(huán)無法進入 (因為const_遠小于n) ,F(n,const_)=INF負無窮大
3個判斷后，s,e均為常數(shù)
when const_1<=const_2 時 灾票，F(xiàn)(const_1,const_2)=0;
when const1>const_2 時 , 循環(huán)無法進入峡谊，F(xiàn)(const_1,const_2)=INF負無窮大
code↓↓↓
同理，兩個for從string中取數(shù)，不詳講
int getOn(string x,string y){//獲取復(fù)雜度
if(x!="n"&&y=="n") return 1;//從 常數(shù) 到 n ：復(fù)雜度為 1
if(x=="n"&&y!="n") return INF;//從 n到常數(shù) ：由于無法進入故認為其復(fù)雜度為負無窮 依據(jù)題目 -99999 已經(jīng)足夠
if(x=="n"&&y=="n") return 0;//從 n到 n相當(dāng)于 常數(shù) 到 常數(shù) 復(fù)雜度為 0
//x y 均為數(shù)字 既们，則只要判斷循環(huán)能否進入即可濒析，能進入 復(fù)雜度為0 ， 不能進入 復(fù)雜度則為 負無窮（INF）
int xx=0,yy=0;
for(int i=0;i<x.length();i++){
xx*=10;
xx+=x[i]-'0';
}
for(int i=0;i<y.length();i++){
yy*=10;
yy+=y[i]-'0';
}
return yy>=xx?0:INF;//yy>=xx 常數(shù)級別
}
4.入讀數(shù)據(jù)
(讀入完后的工作以 work()省略)
map<Object , Object > map_name用法詳細見 link[... ]
scanf("%d",&T);
while(T--){//小明寫了n個 A++ 程序
map<string ,int >map_times;//關(guān)聯(lián)容器 將變量名與次數(shù)關(guān)聯(lián)啥纸，可與下邊胡map_on合并
map<string ,int >map_on;//儲存變量的復(fù)雜度
stack<string >st;// top() 表示當(dāng)前所在胡循環(huán)
isError=false;//錯誤開關(guān)關(guān)閉
Fnum=Maxon=on=0;//F-E記次清零 最大復(fù)雜度号杏，當(dāng)前復(fù)雜的清零
cin>>l>>On;//獲取每個程序初始數(shù)據(jù) 行數(shù)與期望復(fù)雜度
string F,i,x,y;//準備 循環(huán)輸入數(shù)據(jù)
while(l--){//程序行數(shù)
cin>>F;
if(F=="F"){//首字母檢測 F則開始循環(huán) E則退出
cin>>i>>x>>y;
work_1();
}else{//首字母為 E
work_2();
}
}
cout<<Ans<<endl;//輸出答案
}
5.work()
好吧這道題惡心也就在ERR的時候
分析一下 ERR有這么幾種情況（重復(fù)請忽視）
1. 程序行數(shù)L為奇數(shù)，則F斯棒，E肯定不匹配 (F,E個數(shù)不匹配)
2. F盾致，E 出入棧不匹配
3. F，E 個數(shù)不匹配 （用Fnum記錄荣暮，輸入F則++庭惜，輸入E則--）
4. F循環(huán)變量名字重復(fù) （用map<string ,int >map_times 記錄變量的次數(shù)）
注意！題目最后邊還有一句話
全部代碼 (快捷復(fù)制：按住鼠標左鍵選擇你要的代碼然后Ctrl+c)
#include <bits/stdc++.h>
using namespace std;
int T,l,on,Fnum,Maxon;//T程序數(shù)穗酥，l程序行數(shù)蜈块，on當(dāng)前復(fù)雜度，F(xiàn)num當(dāng)前程序F-E個數(shù)迷扇，Maxon當(dāng)前程序最大復(fù)雜度
string On,Ans;//輸入百揭，答案
bool isError;//當(dāng)前程序錯誤開關(guān)
const int INF=-99999;
const bool DEBUG=false;
bool checkRight(int w){// 檢查復(fù)雜度是否一置
if(w==0&&On=="O(1)") return 1;
else {
int r=0;
for(int i=4;i<On.length()-1;i++) {//這個for實際上就是從（string）On里取出數(shù)字來
r*=10;
r+=On[i]-'0';
}
return r==w;
}
}
int getOn(string x,string y){//獲取復(fù)雜度
if(x!="n"&&y=="n") return 1;//從 常數(shù) 到 n ：復(fù)雜度為 1
if(x=="n"&&y!="n") return INF;//從 n到常數(shù) ：由于無法進入故認為其復(fù)雜度為負無窮 依據(jù)題目 -99999 已經(jīng)足夠
if(x=="n"&&y=="n") return 0;//從 n到 n相當(dāng)于 常數(shù) 到 常數(shù) 復(fù)雜度為 0
//x y 均為數(shù)字 ，則只要判斷循環(huán)能否進入即可蜓席，能進入 復(fù)雜度為0 器一， 不能進入 復(fù)雜度則為 負無窮（INF）
int xx=0,yy=0;
for(int i=0;i<x.length();i++){
xx*=10;
xx+=x[i]-'0';
}
for(int i=0;i<y.length();i++){
yy*=10;
yy+=y[i]-'0';
}
return yy>=xx?0:INF;//yy>=xx 常數(shù)級別
}
int main(){
// freopen("complexity.in","r",stdin);
// freopen("complexity.out","w",stdout);
scanf("%d",&T);
while(T--){//小明寫了n個 A++ 程序
map<string ,int >map_times;//關(guān)聯(lián)容器 將變量名與次數(shù)關(guān)聯(lián)，可與下邊胡map_on合并
map<string ,int >map_on;//儲存變量的復(fù)雜度
stack<string >st;// top() 表示當(dāng)前所在胡循環(huán)
isError=false;//錯誤開關(guān)關(guān)閉
Fnum=Maxon=on=0;//F-E記次清零 最大復(fù)雜度厨内，當(dāng)前復(fù)雜的清零
cin>>l>>On;//獲取每個程序初始數(shù)據(jù) 行數(shù)與期望復(fù)雜度
if(l%2) isError=true;//如果程序行數(shù)是個奇數(shù)祈秕，那么F-E一定無法一一對應(yīng)
string F,i,x,y;//準備 循環(huán)輸入數(shù)據(jù)
while(l--){
cin>>F;
if(F=="F"){//首字母檢測 F則開始循環(huán) E則退出
Fnum++;//F 計次
cin>>i>>x>>y;
map_times[i]++;//當(dāng)前程序中的 循環(huán)i的 次數(shù)
st.push(i);//將 i循環(huán) 壓棧 ，棧頂 i即為當(dāng)前所在循環(huán)
if(isError||map_times[i]>1){//如果已經(jīng)error了雏胃，則沒必要計算復(fù)雜度
isError=true;//如果循環(huán)i再次出現(xiàn) >>ERR
continue;
}
map_on[i]=getOn(x,y);//獲取 循環(huán)i 的復(fù)雜度
on+=map_on[i];//復(fù)雜度累加前邊嵌套的
Maxon=max(on,Maxon);//最大值迭代
}else{//首字母為 E 則終止 st.top() 表示的循環(huán)
if(isError)continue;// error 跳過
Fnum--;//F 個數(shù) 減1
if(st.empty())continue;//棧為空 當(dāng)前執(zhí)行已不在任何循環(huán)內(nèi)
on-=map_on[st.top()];//當(dāng)前復(fù)雜度 減去 當(dāng)前循環(huán)st.top() 的復(fù)雜度
map_times[st.top()]--;//循環(huán)i出現(xiàn)的次數(shù) 減1
st.pop();//當(dāng)前循環(huán) 退棧
}
}
if(Fnum!=0||isError){//F-E個數(shù)不相等 请毛， ERR輸出
cout<<"ERR"<<endl;
continue;
}
Ans=checkRight(Maxon)?"Yes":"No";//檢查答案是否正確
cout<<Ans<<endl;//輸出答案
}
return 0;
}
最后更新 2018.10.31 8:51 By HaoDaDaDa
