Gym - 100162G 2012-2013 Petrozavodsk Winter Training Camp G. Lyndon Words 暴力枚举

Love The Way You Lie 2022-01-09 07:27 84阅读 0赞

[题面][Link 1]

题意:如果一个字符串的最小表示法是他自己,他就是一个Lyndon Word.

例如  aabcb 他的循环串有 abcba  bcbaa cbaab baabc 其中字典序最小的是他自己

现在给你n,m表示用前m个字符(从a开始),拼成长度不超过n的字符串中,输出字典序排列的的  l->r 的串

l<=r<=1e7   r-l<=1e5

题解:我们根据样例 n=4 m=3可以看出,一共32个:a, aaab, aaac, aab, aabb, aabc, aac, aacb, aacc,

ab, abac, abb,abbb, abbc, abc, abcb, abcc, ac, acb, acbb, acbc, acc, accb, accc,

b, bbbc, bbc,bbcc, bc, bcc, bccc, c.

不难看出,我们每次从a开始,写到长度n,然后会后退1位,从b开始,继续写到长度n,又退回一位写c,

退一位的完了,就继续退两位.

于是模拟这个过程输出就好了. 每一次复杂度就是O(26\*r)的

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 int T,n,m,l,r;
     4 char s[40];
     5 int main()
     6 {
     7     while (scanf("%d%d%d%d",&n,&m,&l,&r)!=EOF)
     8     {
     9         T++;
    10         printf("Case %d:\n",T);
    11         s[0]='a';
    12         int i=0,tot=1;
    13         while (i<r)
    14         {
    15             i++;
    16             if (i>=l) 
    17             {
    18                 for (int k=0;k<tot;k++) printf("%c",s[k]);
    19                 printf("\n");
    20             }
    21             int x=tot;
    22             while (tot<n) 
    23             {
    24                 s[tot]=s[tot%x];
    25                 tot++;
    26             } 
    27             while (tot>0) if (s[tot-1]-'a'+1==m) tot--;else break;
    28             s[tot-1]=char(s[tot-1]+1);
    29         }
    30     }    
    31 }

转载于:https://www.cnblogs.com/qywhy/p/10681361.html

[Link 1]: http://codeforces.com/gym/100162/problem/G