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

题面

题意:如果一个字符串的最小表示法是他自己,他就是一个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)的

 #include<bits/stdc++.h>

 using namespace std;

 int T,n,m,l,r;

 char s[];

 int main()

 {

     while (scanf("%d%d%d%d",&n,&m,&l,&r)!=EOF)

     {

         T++;

         printf("Case %d:\n",T);

         s[]='a';

         int i=,tot=;

         while (i<r)

         {

             i++;

             if (i>=l)

             {

                 for (int k=;k<tot;k++) printf("%c",s[k]);

                 printf("\n");

             }

             int x=tot;

             while (tot<n)

             {

                 s[tot]=s[tot%x];

                 tot++;

             }

             while (tot>) if (s[tot-]-'a'+==m) tot--;else break;

             s[tot-]=char(s[tot-]+);

         }

     }

 }

巴特西

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

最新文章

热门文章