这题很有趣,一开始我总是WA,最后发现其实是我对于cin.getline()的使用不熟练导致的。
原题链接
当然,尴尬的是到今天ACM训练结束我都没有优化完,这个代码到16个点就超时了。
#include<bits\stdc++.h> char seq[200004]; char seq_c[200004]; int n,ans; using namespace std; int main() { memset(seq,0,sizeof(seq)); memset(seq_c,0,sizeof(seq_c)); //scanf("%s",seq); //scanf("%s",seq_c); cin.getline(seq,200000,'\n'); cin.getline(seq_c,200000,'\n'); cin >> n; int k; for(k=strlen(seq_c);k>=1;k--) { ans=0; seq_c[k]=0; for(int i=0;i<strlen(seq);i++) { if(seq[i]==seq_c[0]) { int j; for(j=1;j<strlen(seq_c);j++) { if(seq[i+j]!=seq_c[j])break; } if(j==strlen(seq_c))ans++; } } if(ans>=n)break; } if(k) { for(int i=0;i<strlen(seq_c);i++)cout << seq_c[i]; } else cout << "IMPOSSIBLE"; cout << endl; return 0; }
于是今天早上我加了一个优化开关,然并卵。
if(strlen(seq_c) > strlen(seq)-i) break;
随后我把序列反过来,用一个数组存储前一次的满足值,并去查找。
#include<bits\stdc++.h> char seq[200004]; char seq_c[200004]; int init_seq[200004]; int n,ans,flag; using namespace std; int main() { memset(seq,0,sizeof(seq)); memset(seq_c,0,sizeof(seq_c)); memset(init_seq,0,sizeof(init_seq)); cin.getline(seq,200000,'\n'); cin.getline(seq_c,200000,'\n'); for(int i=0;i<strlen(seq);i++)init_seq[i]=i; cin >> n; int k,init_seq_len=strlen(seq); for(k=1;k<=strlen(seq_c);k++) { ans=0; flag=0; for(int i=0;i<init_seq_len;i++) { if(k > strlen(seq)-init_seq[i]) break; if(seq[init_seq[i]]==seq_c[0]) { init_seq[flag]=init_seq[i]; flag++; //上面先更新下init_seq,下面再执行对比 int j; for(j=1;j<k;j++) { if(seq[init_seq[i]+j]!=seq_c[j])break; } if(j==k)ans++; } } if(ans<n) { k--; break; } init_seq_len=flag; } if(k==strlen(seq_c)+1)k--; if(k) { for(int i=0;i<k;i++)cout << seq_c[i]; } else cout << "IMPOSSIBLE"; cout << endl; return 0; }
然而还是在第16个点炸了。
我的最新思路是用二分的方法去查找,原理类似猜数字,先用一半去试,如果大了就是4/3,否则1/4,如此操作。
值得注意的是,得到一个相等并不能得出答案,还需到找出最长的一个相等的。
因此二分查找的第一个小于的,而不是第一个等于的。