字符串題

• 考慮找到一種方法，能夠對一個 lyndon 串 A ，直接求出 A 的下一個 lyndon 串。
• 考慮不斷復制 A ，得 AAA…A
• 因為 lyndon 串是自身循環移位得到的串中字典序嚴格最小的，所以 AAA…A 非lyndon 串。
• 考慮微調：將 AAA…A 的末尾稍變大一些。具體方法如下：
  1.若 AAA…A 的最后一位不為 ‘a’+m-1，讓 AAA…A 的最后一個字符變為這個字符在字符集中的后繼（如a變成b，b變成c）
  2.若 AAA…A 的最后一位為 ‘a’+m-1，刪去最后一位，一直刪到最后一位不為 ′a′+m?1 為止，然后按1.的情況處理
  （ps.其實就是找字典序比A大一的字符串A’，這樣得到的串 AA…AA’ 字典序剛好比 AAA…A 大一）
• 可以證明 AA…AA’ 為 lyndon 串 ：

若循環移位后的串以A開頭：
則必有A…AA’A…A>AAA…AA’。

若循環移位后的串不以A開頭：
設 $A=a_1{a}_2?a_{|A|}$ 。
由于 A 為 lyndon 串，所以對 $?1<i\le |A|$ ，有 $a_i{a}_{i+1}?a_{|A|}{a}_1{a}_2...a_{i?1}>a_1{a}_2?a_{|A|}$ 。所以得到的串字典序必大于 AA…AA’

• 考慮怎么讓 AA…AA’ 與 A 之間無其它 lyndon 串：
  設 T 為 A 與 AA…AA’ 之間的一個 lyndon 串。因為 A<T<AA…AA’，所以有T=AA…AT’，其中T’ 的前 |A| 位不等于 A。

若 T 中A循環部分的長度 <= AA…AA’ 中A循環部分的長度：
因為 AA…AT’<AA…AA’，所以 T’<=A ，則以 T′ 開頭的循環移位小于等于 T ，與 T 是 lyndon 串矛盾

若 T 中A循環部分的長度 > AA…AA’ 中A循環部分的長度：
必有 A<T<AA…AA’，且根據之前的結論，只要令 T’>A，T 必為 lyndon 串

• 也就是說我們必須令 T中A循環部分的長度 > AA…AA’ 中A循環部分的長度 的T 不符合條件，即|T|>n
• 那么 AA…AA’ 必須盡可能地長，我們考慮不斷復制 A，然后取 AAA… 的前n位，記為 S，再找到字典序比 S 大一的字符串即可（如上文所述）。
• 可以證明這樣得到的串是符合條件的
  證明

#include<iostream> #include<cstdio> #include<algorithm> using namespace std; struct Que{int x,id; }que[200010]; int n,m,q,len; char ans[200010][31],ch[31]; bool cmp(Que a,Que b){return a.x<b.x; } int main(){scanf("%d%d%d",&n,&m,&q);for(int i=1;i<=q;i++){scanf("%d",&que[i].x);que[i].id=i;}sort(que+1,que+q+1,cmp);ch[len=1]='a';int p=1;for(int i=1;i<=q;i++){while(p<que[i].x){for(int j=len+1;j<=n;j++) ch[j]=ch[j-len];len=n;while(ch[len]=='a'+m-1) ch[len--]=0;ch[len]++;p++; }for(int j=1;j<=len;j++) ans[que[i].id][j]=ch[j];}for(int i=1;i<=q;i++){for(int j=1;ans[i][j];j++) putchar(ans[i][j]);puts("");}return 0; }

總結

以上是生活随笔為你收集整理的[XSY] 字符串题（字符串，构造）的全部內容，希望文章能夠幫你解決所遇到的問題。

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