題目鏈接

?

題意：

給出僅表示循環結構的簡化語句，指出編譯錯誤和時間復雜度。

?

程序1（100pt）：

字符串處理，字母數字夾雜，上$scanf$來做。注意到有復數種情況，各種空格空行要分類討論清楚。

考慮同時查錯和做復雜度，思考一下發現不行：出現不執行的循環體，查錯要求進入，做復雜度要求跳過，不適合硬生生糅合在一起。

考慮先查錯，再做復雜度。考慮到之后有跳過循環體的情況，查錯時把同一對循環首尾做一個鏈接。

實現時，用棧來維護“層層深入，逐步退出”的數據關系。

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define IL inline using namespace std; const int N=100;int L,w;bool num(char ch){return '0'<=ch&&ch<='9';}struct Txt{bool f,f1,f2; //f:'F' f1:x==n f2:y==nchar ch;int x,y;}str[N+3];struct Stk{char ch;int id;}stk[N+3];bool vis['z'+3];bool mrk[N+3];int top,ans;int jmp[N+3];int main(){int T; char ch;scanf("%d\n",&T);while(T--){scanf("%d O(%c",&L,&ch);if(ch=='1')w=0;else scanf("^%d",&w);scanf(")\n");for(int i=1;i<=L;i++){scanf("%c",&ch);if(ch=='E'){str[i].f=false;scanf("\n");continue;}str[i].f=true;scanf(" %c %c",&str[i].ch,&ch);if(ch=='n'){str[i].f1=true;scanf("%c",&ch);}else {str[i].x=ch-'0';str[i].f1=false;scanf("%c",&ch);while(num(ch)){str[i].x=str[i].x*10+ch-'0';scanf("%c",&ch);}}scanf("%c",&ch);if(ch=='n'){str[i].f2=true;scanf("\n");}else {str[i].y=ch-'0';str[i].f2=false;scanf("%c",&ch);while(num(ch)){str[i].y=str[i].y*10+ch-'0';scanf("%c",&ch);}}}bool flag=false; top=0;memset(vis,0,sizeof vis);for(int i=1;i<=L;i++)if(str[i].f){if(vis[(int)str[i].ch]){flag=true;break;}vis[(int)str[i].ch]=true;top++;stk[top].ch=str[i].ch;stk[top].id=i;}else {if(top==0){flag=true;break;}vis[(int)str[stk[top].id].ch]=false;jmp[stk[top].id]=i;jmp[i]=stk[top].id;top--;}if(!flag&&top>0)flag=true;if(flag){printf("ERR\n");continue;}top=ans=0;memset(mrk,0,sizeof mrk);for(int i=1;i<=L;i++)if(str[i].f){if(((!str[i].f1)&&(!str[i].f2)&&(str[i].x>str[i].y))||((str[i].f1)&&(!str[i].f2))){i=jmp[i];continue;}if((!str[i].f1)&&str[i].f2){top++;mrk[i]=true;ans=max(ans,top);}}elseif(mrk[jmp[i]])top--;if(ans==w)printf("Yes\n");else printf("No\n");}return 0;}

?

小結：

$scanf$處理字符串熟練度$++$！

一個真實的故事：當年考聯賽同隊有人把$ERR$寫成了$Err$結果怒爆$0$。

轉載于:https://www.cnblogs.com/Hansue/p/11018758.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

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

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