【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

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 typedef long long ll;
 6 using namespace std;
 7 #define N   110000 
 8 #define oo  10000000
 9 #define MOD 100000073
10 
11 const char r[3][10]={"A","ABC","ABAABB"};
12 const int len[3]={1,3,6}; 
13 
14 
15 void print(int k,int n)
16 {
17     for(int i=0;i<n;i++) printf("%c",r[k][i%len[k]]);
18 }
19 
20 int main()
21 { 
22     int cas; 
23     scanf("%d",&cas);
24     for(int v=1;v<=cas;v++)
25     {
26         int n,m,k;
27         scanf("%d%d%d",&n,&m,&k); 
28         printf("Case #%d:
",v);
29         if(n<m)
30         {
31           printf("Impossible
");
32           continue;
33         }
34         if(n==m)
35         {
36             print(0,n);
37             printf("
");
38             continue;
39         } 
40         if(n==8&&m==7&&k==2)
41         {
42             printf("AABABBAA
");
43             continue;
44         }
45         if(k==1)
46         {
47             printf("Impossible
");
48             continue;
49         }
50         if(k==2)
51         {
52             if(m<8)
53             {
54                 printf("Impossible
");
55                 continue;
56             }
57             print(0,m-8);
58             print(2,n-m+8);
59             printf("
");
60             continue;
61         }
62         if(k>2)
63         {
64             if(m<3)
65             {
66                 printf("Impossible
");
67                 continue;
68             }
69             print(0,m-3);
70             print(1,n-m+3);
71             printf("
");
72             continue;
73         }
74         
75     }
76     return 0;
77 }
78