63分求助

P3952 [NOIP2017 提高组] 时间复杂度

@[Fitzwilliam_Darcy](/space/show?uid=26800) @[牛的传说](/space/show?uid=40985) @[U41485](/space/show?uid=41485)
by AK_Automata @ 2018-11-08 15:38:44


都不在吗。。。
by AK_Automata @ 2018-11-08 15:45:29


在啊
by iwprc @ 2018-11-08 15:47:37


你不是讲你过了吗
by Binary_Search_Tree @ 2018-11-08 16:07:17


@[AK_Automata](/space/show?uid=36881) ```cpp #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int inf=10005; int t,n; char s[105][105]; char k[105]; int tt[35],tot; int BJ[105]; char CHAR[105]; bool err1(){ int f1=0,f2=0; for(int i=1;i<=n;i++){ if (s[i][1]=='F') f1++; if (s[i][1]=='E') f2++; } return f1==f2; } bool err2(){ memset(tt,0,sizeof(tt)); int f1=0; for (int i=1;i<=n;i++){ if (s[i][1]=='E') {tt[CHAR[f1]]--;f1--;continue;} f1++; if (tt[(int)s[i][3]-'a']) return false; tt[(int)s[i][3]-'a']++; CHAR[f1]=(int)s[i][3]-'a'; } return true; } int getshu(int i,int from){ int k1[5]={0}; tot=0; for (int j=from;;j++){ if (s[i][j]>'9'||s[i][j]<'0') break; k1[++tot]=s[i][j]-48; } if (tot==1) return k1[tot]; if (tot==2) return k1[1]*10+k1[2]; } int getshu2(int from){ int k1[5]={0}; tot=0; for (int j=from;;j++){ if (k[j]>'9'||k[j]<'0') break; k1[++tot]=k[j]-48; } if (tot==1) return k1[tot]; if (tot==2) return k1[1]*10+k1[2]; } int getans(){ int maxn=0,now=0,s1,s2; int f1=0; BJ[0]=true; for (int i=1;i<=n;i++){ if(BJ[f1]) maxn=max(maxn,now); if (s[i][1]=='E'){ if(BJ[f1]==2) now--; f1--; } if (s[i][1]=='F') { f1++; if(!BJ[f1-1]){ BJ[f1]=false; continue; } if (s[i][5]=='n') s1=inf,tot=1; else s1=getshu(i,5),s2; if (s[i][6+tot]=='n') s2=inf; else s2=getshu(i,6+tot); //cout<<s1<<" "<<s2<<endl; if (s1>s2) {BJ[f1]=false;continue;} if (s2-s1>100){ BJ[f1]=2,now++; } else BJ[f1]=1; } //cout<<f1<<" "<<f2<<" "<<now<<endl; } //if (f1==f2) maxn=max(maxn,now); return maxn; } int main() { cin>>t; while (t--){ memset(k,' ',sizeof(k)); memset(s,' ',sizeof(s)); cin>>n; gets(k); for (int i=1;i<=n;i++) gets(s[i]+1); if (!err1()) {cout<<"ERR"<<endl;continue;} if (!err2()) {cout<<"ERR"<<endl;continue;} int ans=getans(); if (k[3]=='1') { if (ans==0) cout<<"Yes"<<endl; else cout<<"No"<<endl; } else { int ss=getshu2(5); //printf("%d %d\n",ans,ss); if (ans==ss) cout<<"Yes"<<endl; else cout<<"No"<<endl; //cout<<ss<<endl; } } //system("pause"); return 0; } ```
by iwprc @ 2018-11-08 16:15:17


我都要调吐了
by iwprc @ 2018-11-08 16:17:07


多谢大佬%%%@[U41485](/space/show?uid=41485)
by AK_Automata @ 2018-11-08 17:08:17


|