【題目描述】
最近小K大牛經過調查發現，在WZland的最南方——WZ Antarctica 出現了奇怪
的磁場反應。為了弄清楚這一現象，小K 大牛親自出馬，來到了WZ Antarctica。
小K大牛發現WZ Antarctica 出現了一道神秘的大門。人總有好奇心，小K大牛想打開
這扇神秘大門，看門的后面究竟是什么東西，但用盡什么辦法也不能打開這扇門。
突然，門上出現了一些奇怪的字符。憑著敏銳的直覺，小K 認為這些符號就是打
開這扇門的關鍵， 于是小K 抓緊時間開始研究這些符號。
經過一些時間的研究，小K 大牛發現這些符號其實是一串密碼，只有破解了
這個密碼， 才能打開那扇神秘大門。這個密碼十分簡單，他給出了兩個很長的字
符串A 和B，你只需要判斷B 是否在A 中出現過就可以了，當然如果B 在A
中出現，那么你還需要輸出B 的字符在A 中依次出現的位置。
這里解釋一下B 在A 中出現的概念，設A=S1S2…SN，B= T1T2…TM，如果存
在一組數K：K1<K2<…<KM，使得B=SK1SK2…SKM，那么就可以認為B 在A 出現
過。比如說A=sdfesad， B=sfsad，那么B 在A 中出現過，因為B 中的字符在A
中依次出現的位置為1 3 5 6 7。
這個解密過程實在太簡單了，于是小K 大牛就將這個任務交給了你。由于小K
大牛十分著急，他只給了你1s 的時間。
【輸入】
輸入數據包含2 行，分別包含一個字符串，第一行輸入的是字符串A，第二
行輸入的是字符串B。
【輸出】
第一行輸出一個字符串“Yes”或“No”，如果B 在A 中出現，那么輸出“Yes”，
否則輸出“No”。
如果你的第一行輸出“Yes”，那么在第接下來若干行你需要輸出一組數K，使
得B=SK1SK2…SKM，每行一個數；否則第二行為空。如果存在多組數據滿足條件，
你需要輸出字典序最大的一組。
【輸入輸出樣例1】
door.in ? ? door.out
sdfesad ? ?Yes
sfsad ? ? ? ?1

? ? ? ? ? ? ? ?3

? ? ? ? ? ? ? ?5

? ? ? ? ? ? ? ?6

? ? ? ? ? ? ? ?7?
【輸入輸出樣例2】
door.in ? ? ?door.out
abcdef ? ? ? No
acdefg

【數據范圍】

字符串長度1≤n≤1e6

?

倒著找，向前貪心，一定得到字典序最大或-1。

1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 using namespace std; 6 const int maxn=1e6+7; 7 char a[maxn],b[maxn]; 8 int q[maxn];int temp3=0; 9 int temp1,temp2; 10 int main() 11 { 12 freopen("door.in","r",stdin); 13 freopen("door.out","w",stdout); 14 scanf("%s",a); 15 scanf("%s",b); 16 temp1=strlen(a)-1; 17 temp2=strlen(b)-1; 18 while(temp2>=0) 19 { 20 while(a[temp1]!=b[temp2]) 21 { 22 temp1--; 23 if(temp1<temp2) 24 { 25 printf("No"); 26 exit(0); 27 } 28 } 29 q[++temp3]=temp1; 30 temp2--;temp1--; 31 } 32 printf("Yes\n"); 33 for(int i=temp3;i>=1;i--) 34 printf("%d\n",q[i]+1); 35 return 0; 36 }

?

轉載于:https://www.cnblogs.com/937337156Zhang/p/6025953.html

總結

以上是生活随笔為你收集整理的NOIP模拟题——神秘大门的全部內容，希望文章能夠幫你解決所遇到的問題。

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