Codeforces 379D - New Year Letter

原题地址: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啦什么的),详见代码~

Codeforces 379D -  New Year Letter
 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 }
Codeforces 379D -  New Year Letter

小注:希望通过这道题能给我和大家带来更多的新年AC~

Codeforces 379D - New Year Letter

上一篇:J2EE简介


下一篇:android:inputType参数类型说明