Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
求解为何O(n)枚举会炸,讨论版的数据都A了……暴力枚举 #include<string> #include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; string s1,s2,s3; int i,j,k,l,n,v; bool f; int main(){ std::ios::sync_with_stdio(false); scanf("%d",&n); for(v=1;v<=n;v++){ i=0;j=0;l=0;f=1; cin>>s1>>s2>>s3; for(k=0;k<s3.length();k++){ if(s3[k]==s1[i]&&s3[k]==s2[j]){ if(i!=s1.length())i++; if(j!=s1.length())j++; if(i==s1.length()&&j==s2.length()) break; l++; continue; } else{ if(l) if(s3[k]==s1[i]&&s3[k]!=s2[j]){ i++; j-=l; l=0; continue; } else if(s3[k]==s2[j]&&s3[k]!=s1[i]){ j++; i-=l; l=0; continue; } if(s1[i-l]==s3[k]){ i=i-l+1; l=0; continue; } if(s2[j-l]==s3[k]){ j=j-l+1; l=0; continue; } if(s3[k]!=s1[i]&&s3[k]!=s2[j]){ f=0; break; } } } if(f)printf("Data set %d: yes\n",v); else printf("Data set %d: no\n",v); } } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator