原题地址：http://codeforces.com/contest/379/problem/D
题目大意：给出一种生成字符串的方法 s[k] = s[k - 2] + s[k - 1]，其中加法意为将左右两个字符串直接相连，要求构造两个长度分别为n、m的字串s[1]、s[2]，使得按照这种方法得出的s[k]中恰好含有 x 个 “AC”（意思大家都懂的……）如果无解，输出“Happy new year!”
数据范围：3 ≤ k ≤ 50; 0 ≤ x ≤ 109; 1 ≤ n, m ≤ 100
题目分析：
这道题算法很明确。
先将问题反过来思考：假设给定两个串s[1]、s[2]，用题目中的方法生成s[k]，求出s[k]含有几个“AC”，显然可以用动态规划解决
定义f[k]表示第k个串中含有“AC”的个数，Suf[k]为第 k 个串的结尾字母，Pre[k]为第k个串的开头字母，三个数组的1、2两位都是已知的
显然可以得到动态规划方程 f[k] = f[k - 2] + f[k - 1] + (Suf[k - 2] == 'A') && (Pre[k - 1] == 'C'); Suf[k] = Suf[k - 1]; Pre[k] = Pre[k - 2]
然后搞一搞就得到答案了。那么我们回归这道题，发现可以通过枚举f[1]、f[2]、Suf[1]、Suf[2]、Pre[1]、Pre[2]来DP计算所有可能的f[k],如果找到一组f[1]、f[2]、Suf[1]、Suf[2]、Pre[1]、Pre[2]使得f[k] == x，就按照它们构造两个字符串输出就好了
复杂度分析：每次枚举Pre[1]等等都是三种情况（是A、是C、不是A也不是C），一共枚举4轮，枚举f[1]时不可能超过二分之n，枚举f[2]时也同理，所以枚举的总复杂度是O(3 * 3 * （m / 2） * 3 * 3 * （n / 2）)大约为202500，每次DP都是线性的所以复杂度是O（k）所以总复杂度可以约归为O（nmk)大概在10^7左右勉强不会超时。
剩下的就是细节了，这道题一大堆特殊情况需要判断(比如n , m <= 2啦什么的)，详见代码～
//date 20140120
#include <cstdio>
#include <cstring> inline int min(int a, int b){return a < b ? a : b;}
inline int max(int a, int b){return a > b ? a : b;} int k, n, m;
long long x;
long long f[];
int suf[], pre[]; void dp(int w)
{
if(w <= )return;
if(f[w - ] == -)dp(w - );
if(f[w - ] == -)dp(w - );
f[w] = f[w - ] + f[w - ] + ((suf[w - ] == ) && (pre[w - ] == ));
suf[w] = suf[w - ]; pre[w] = pre[w - ];
} inline void output(int S1, int S2, int P1, int P2, int i, int j)
{
// printf("%d %d %d %d %d %d\n", S1, P1, i, S2, P2, j);
char ans1[], ans2[];
memset(ans1, , sizeof ans1);
memset(ans2, , sizeof ans2);
ans1[] = P1 + 'A' - ;
ans2[] = P2 + 'A' - ;
ans1[n] = S1 + 'A' - ;
ans2[m] = S2 + 'A' - ;
// printf("%s\n%s\n", ans1 + 1, ans2 + 1); int a1 = , a2 = ;
if(i > && ans1[] == 'A')
{
ans1[] = 'C';a1 = ;
for(int q = ; q < i; ++q){ans1[q * + ] = 'A'; ans1[q * + ] = 'C'; a1 = q * + ;}
for(int q = a1; q < n; ++q)ans1[q] = 'B';
}
else
{
a1 = ;
for(int q = ; q <= i; ++q){ans1[q * ] = 'A'; ans1[q * + ] = 'C'; a1 = q * + ;}
for(int q = a1; q < n; ++q)ans1[q] = 'B';
}
if(j > && ans2[] == 'A')
{
ans2[] = 'C'; a2 = ;
for(int q = ; q < j; ++q){ans2[q * + ] = 'A'; ans2[q * + ] = 'C'; a2 = q * + ;}
for(int q = a2; q < m; ++q)ans2[q] = 'B';
}
else
{
a2 = ;
for(int q = ; q <= j; ++q){ans2[q * ] = 'A'; ans2[q * + ] = 'C'; a2 = q * + ;}
for(int q = a2; q < m; ++q)ans2[q] = 'B';
}
printf("%s\n%s\n", ans1 + , ans2 + );
} int main()
{
// freopen("d.in", "r", stdin); scanf("%d%I64d%d%d", &k, &x, &n, &m); for(int P1 = ; P1 <= ; ++P1)
for(int S1 = ; S1 <= ; ++S1)
for(int P2 = ; P2 <= ; ++P2)
for(int S2 = ; S2 <= ; ++S2)
{
if(n == && S1 != P1)continue;
if(m == && S2 != P2)continue;
int uLim1 = , uLim2 = , dLim1 = , dLim2 = ;
uLim1 = max(n / - , ); if((n >= ) && ((S1 == && P1 == ) || ((n & ) && (S1 == || P1 == ))))++uLim1;
uLim2 = max(m / - , ); if((m >= ) && ((S2 == && P2 == ) || ((m & ) && (S2 == || P2 == ))))++uLim2;
if(n == && S1 == && P1 == )dLim1 = uLim1 = ;
if(m == && S2 == && P2 == )dLim2 = uLim2 = ;
// printf("%d %d %d %d\n", dLim1, uLim1, dLim2, uLim2);
for(int i = dLim1; i <= uLim1; ++i)
for(int j = dLim2; j <= uLim2; ++j)
{
memset(suf, , sizeof suf);
memset(pre, , sizeof pre);
suf[] = S1; suf[] = S2;
pre[] = P1; pre[] = P2;
memset(f, 0xFF, sizeof f);
f[] = i; f[] = j;
dp(k);
// printf("%d %d %d %d %d %d %d\n", P1, S1, P2, S2, i, j, f[k]);
if(f[k] == x){output(S1, S2, P1, P2, i, j); return ;}
}
} printf("Happy new year!\n");
return ;
}
小注：希望通过这道题能给我和大家带来更多的新年AC～