【HDOJ5559】Frog and String（构造）

题意：给定n,m,k，要求构造出一个长度为n，最多使用前k个大写字母，有m个不同回文子串的字符串

1<=n,m<=1e5，1<=k<=26

思路：打表找规律

本质上是要找到不让循环节之间出现新回文子串的方案

n<m：无解

n=m：全A

n>m：k=1：无解

　　 k=2：用m-8个A + ABAABB（循环节）

　　　k>2：用m-3个A + ABC（循环节）

特判n=8，m=7，k=2：AABABBAA

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 typedef long long ll;

 using namespace std;

 #define N   110000

 #define oo  10000000

 #define MOD 100000073

 const char r[][]={"A","ABC","ABAABB"};

 const int len[]={,,}; 

 void print(int k,int n)

 {

     for(int i=;i<n;i++) printf("%c",r[k][i%len[k]]);

 }

 int main()

 {

     int cas;

     scanf("%d",&cas);

     for(int v=;v<=cas;v++)

     {

         int n,m,k;

         scanf("%d%d%d",&n,&m,&k);

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

         if(n<m)

         {

           printf("Impossible\n");

           continue;

         }

         if(n==m)

         {

             print(,n);

             printf("\n");

             continue;

         }

         if(n==&&m==&&k==)

         {

             printf("AABABBAA\n");

             continue;

         }

         if(k==)

         {

             printf("Impossible\n");

             continue;

         }

         if(k==)

         {

             if(m<)

             {

                 printf("Impossible\n");

                 continue;

             }

             print(,m-);

             print(,n-m+);

             printf("\n");

             continue;

         }

         if(k>)

         {

             if(m<)

             {

                 printf("Impossible\n");

                 continue;

             }

             print(,m-);

             print(,n-m+);

             printf("\n");

             continue;

         }

     }

     return ;

 }

巴特西

【HDOJ5559】Frog and String（构造）

最新文章

热门文章