[hdoj5559]Frog and String

Frog and String

题意

给定一个字符串的长度和他里面子回文串的个数。

  • 子回文串是连续子串,并且相同的回文串不重复计数
  • 字符串由前$K$个字符构成

题解

构造题嘛,最重要的就是规律啦。

对于构造题,我们就要一步一步来,把题目分段。

  1. 首先对于$K=1$来说,如果$n !=m$的话,无解。
  2. 对于$K=2$来说,这时候爆搜就起作用了,我怎么想也不肯能根据我那只有6长度的字符串想到会存在一个长度为8但是只有7个自回文串的字符串。他就是$AABABBAA$.估计只有搜才能发现这个玩意,之后就会发现只有两个字符,你也能构造一个长度很长,但只有很少的子回文串。$AABABB$这个玩意可以无限重复,但是只有$A,B,AA,BB,ABA,BAB,ABBA,BAAB$这四种玩意。
  3. 对于$K \ge 3$,最好想,就是$ABC$来重复计数,$m-3$个前导$A$

我真是蠢,真的,没有去用爆搜找一下答案,就凭自己的直觉在那里搞来搞去。

+1 $m=2$的时候少考虑了

+1 当$k>m$的时候

+1 单独测试用例 没有print case

+1 特判m==n没有加else if

+1 $k=2,n=m$的时候出现了错误。应该特判的。

ac代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=(a);i<(n);i++)
#define per(i,a,n) for(int i=(n-1);i>=(a);i--)
#define fi first
#define se second
typedef pair <int,int> pII;
typedef long long ll;
const int INF = 0x3f3f3f3f;
//head
const int maxn = 1e5+10;
const int maxk = 30;
int n,k,m;
char magic[10] = "ABAABB";
int main(){
#ifdef LOCAL
freopen("1.in","r",stdin);
#endif
int T; scanf("%d",&T);
rep(test_case,1,T+1){
scanf("%d%d%d",&n,&m,&k);
bool flag = false;
if(n!=m){
if(k==1) flag = true;
if(k==2 && m<8) flag = true;
if(k>=3 && m<=2) flag = true;
if(n<m) flag = true;
if(m==7 && n==8 && k==2){
printf("Case #%d:\n",test_case);
puts("AABABBAA");
continue;
}
}
printf("Case #%d:\n",test_case);
if(flag) puts("Impossible");
else if(n==m){
rep(i,0,n) printf("A");
puts("");
}else if(k==2){
int cnt = m-8;
rep(i,0,cnt) printf("A");
rep(i,0,n-cnt) printf("%c",magic[i%6]);
puts("");
}else{
vector<char> ve;
rep(i,0,m-3) printf("A");
rep(i,0,3) ve.push_back('A'+i);
rep(i,0,n-m+3){
printf("%c",ve[i%3]);
}
puts("");
}
}
return 0;
}