原题地址：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啦什么的)，详见代码～
1 //date 20140120 2 #include <cstdio> 3 #include <cstring> 4 5 inline int min(int a, int b){return a < b ? a : b;} 6 inline int max(int a, int b){return a > b ? a : b;} 7 8 int k, n, m; 9 long long x; 10 long long f[100]; 11 int suf[100], pre[100]; 12 13 void dp(int w) 14 { 15 if(w <= 2)return; 16 if(f[w - 1] == -1)dp(w - 1); 17 if(f[w - 2] == -1)dp(w - 2); 18 f[w] = f[w - 1] + f[w - 2] + ((suf[w - 2] == 1) && (pre[w - 1] == 3)); 19 suf[w] = suf[w - 1]; pre[w] = pre[w - 2]; 20 } 21 22 inline void output(int S1, int S2, int P1, int P2, int i, int j) 23 { 24 // printf("%d %d %d %d %d %d\n", S1, P1, i, S2, P2, j); 25 char ans1[120], ans2[120]; 26 memset(ans1, 0, sizeof ans1); 27 memset(ans2, 0, sizeof ans2); 28 ans1[1] = P1 + ‘A‘ - 1; 29 ans2[1] = P2 + ‘A‘ - 1; 30 ans1[n] = S1 + ‘A‘ - 1; 31 ans2[m] = S2 + ‘A‘ - 1; 32 // printf("%s\n%s\n", ans1 + 1, ans2 + 1); 33 34 int a1 = 110, a2 = 110; 35 if(i > 0 && ans1[1] == ‘A‘) 36 { 37 ans1[2] = ‘C‘;a1 = 3; 38 for(int q = 1; q < i; ++q){ans1[q * 2 + 1] = ‘A‘; ans1[q * 2 + 2] = ‘C‘; a1 = q * 2 + 3;} 39 for(int q = a1; q < n; ++q)ans1[q] = ‘B‘; 40 } 41 else 42 { 43 a1 = 2; 44 for(int q = 1; q <= i; ++q){ans1[q * 2] = ‘A‘; ans1[q * 2 + 1] = ‘C‘; a1 = q * 2 + 2;} 45 for(int q = a1; q < n; ++q)ans1[q] = ‘B‘; 46 } 47 if(j > 0 && ans2[1] == ‘A‘) 48 { 49 ans2[2] = ‘C‘; a2 = 3; 50 for(int q = 1; q < j; ++q){ans2[q * 2 + 1] = ‘A‘; ans2[q * 2 + 2] = ‘C‘; a2 = q * 2 + 3;} 51 for(int q = a2; q < m; ++q)ans2[q] = ‘B‘; 52 } 53 else 54 { 55 a2 = 2; 56 for(int q = 1; q <= j; ++q){ans2[q * 2] = ‘A‘; ans2[q * 2 + 1] = ‘C‘; a2 = q * 2 + 2;} 57 for(int q = a2; q < m; ++q)ans2[q] = ‘B‘; 58 } 59 printf("%s\n%s\n", ans1 + 1, ans2 + 1); 60 } 61 62 int main() 63 { 64 // freopen("d.in", "r", stdin); 65 66 scanf("%d%I64d%d%d", &k, &x, &n, &m); 67 68 for(int P1 = 1; P1 <= 3; ++P1) 69 for(int S1 = 1; S1 <= 3; ++S1) 70 for(int P2 = 1; P2 <= 3; ++P2) 71 for(int S2 = 1; S2 <= 3; ++S2) 72 { 73 if(n == 1 && S1 != P1)continue; 74 if(m == 1 && S2 != P2)continue; 75 int uLim1 = 0, uLim2 = 0, dLim1 = 0, dLim2 = 0; 76 uLim1 = max(n / 2 - 1, 0); if((n >= 3) && ((S1 == 3 && P1 == 1) || ((n & 1) && (S1 == 3 || P1 == 1))))++uLim1; 77 uLim2 = max(m / 2 - 1, 0); if((m >= 3) && ((S2 == 3 && P2 == 1) || ((m & 1) && (S2 == 3 || P2 == 1))))++uLim2; 78 if(n == 2 && S1 == 3 && P1 == 1)dLim1 = uLim1 = 1; 79 if(m == 2 && S2 == 3 && P2 == 1)dLim2 = uLim2 = 1; 80 // printf("%d %d %d %d\n", dLim1, uLim1, dLim2, uLim2); 81 for(int i = dLim1; i <= uLim1; ++i) 82 for(int j = dLim2; j <= uLim2; ++j) 83 { 84 memset(suf, 0, sizeof suf); 85 memset(pre, 0, sizeof pre); 86 suf[1] = S1; suf[2] = S2; 87 pre[1] = P1; pre[2] = P2; 88 memset(f, 0xFF, sizeof f); 89 f[1] = i; f[2] = j; 90 dp(k); 91 // printf("%d %d %d %d %d %d %d\n", P1, S1, P2, S2, i, j, f[k]); 92 if(f[k] == x){output(S1, S2, P1, P2, i, j); return 0;} 93 } 94 } 95 96 printf("Happy new year!\n"); 97 return 0; 98 }
小注：希望通过这道题能给我和大家带来更多的新年AC～