水题，呵呵：
/* ID: qq104801 LANG: C++ TASK: heritage */ #include <iostream> #include <fstream> #include <cstring> #include <vector> #include <queue> #include <stack> #include <algorithm> using namespace std; #define nmax 27 int n,len; char mid[nmax],pre[nmax],post[nmax]; int xindex=0; void getlast(int head,int start,int end) { for(int i=start;i<end;i++) if(mid[i]==pre[head]) { getlast(head+1,start,i); getlast(head+1+i-start,i+1,end); post[xindex]=pre[head]; xindex++; break; } } void test() { freopen("heritage.in","r",stdin); freopen("heritage.out","w",stdout); char str[nmax]; cin>>str; len=strlen(str); for(int i=0;i<len;i++) mid[i]=str[i]; cin>>pre; getlast(0,0,len); post[len]=' '; cout<<post<<endl; } int main () { test(); return 0; }
test data:
USACO Training Grader Results 19 users online ARE/1 AUS/1 BGD/1 CHN/11 IND/2 LTU/1 TWN/1 YUG/1 USER: cn tom [qq104801] TASK: heritage LANG: C++ Compiling... Compile: OK Executing... Test 1: TEST OK [0.011 secs, 3376 KB] Test 2: TEST OK [0.011 secs, 3376 KB] Test 3: TEST OK [0.005 secs, 3376 KB] Test 4: TEST OK [0.008 secs, 3376 KB] Test 5: TEST OK [0.005 secs, 3376 KB] Test 6: TEST OK [0.005 secs, 3376 KB] Test 7: TEST OK [0.005 secs, 3376 KB] Test 8: TEST OK [0.008 secs, 3376 KB] Test 9: TEST OK [0.008 secs, 3376 KB] All tests OK. YOUR PROGRAM ('heritage') WORKED FIRST TIME! That's fantastic -- and a rare thing. Please accept these special automated congratulations. Here are the test data inputs: ------- test 1 ---- ABEDFCHG CBADEFGH ------- test 2 ---- F F ------- test 3 ---- BCAD ABCD ------- test 4 ---- GOLEAFS SFAELOG ------- test 5 ---- GSHBAQTPM ABGHSPQTM ------- test 6 ---- AUBYCVDZEWFXGTH ZYUABVCDXWEFTGH ------- test 7 ---- ABDCJHKILMNPOQFEGRS ABCDEFHJIKLMNOPQGRS ------- test 8 ---- GFDIHKLJMBNESRTPOQAUCWVZYX ABDFGHIJKLMENOPRSTQCUVWXYZ ------- test 9 ---- EHGDIFJLKMBNCOQSPRAWUXZYTV ABDEGHFIJKLMCNOPQSRTUWXYZV Keep up the good work! Thanks for your submission!