HDOJ 2065 “红色病毒”问题

题目地址:

http://acm.hdu.edu.cn/showproblem.php?pid=2065


汗,这题没想到,看了网上的解答。。。直接COPY过来把。

问题分析
Problem Analyse  递推题 

Algorithm Analyse  比起以前做过的递推题,这一题算比较麻烦的了(当然,原因是我没有想到好的方法,如果你有更方便的方法,欢迎提供大家一起学习)。
如果没有任何条件限制,A、B、C、D组成长度为n的字符串,其个数应该为:4n。

因为有了A、C需要出现偶数次的要求,就出现合法和不合法的不同分组。
在不合法的组里,又有
1.A出现奇数次、C出现偶数次;
2.C出现奇数次、A出现偶数次;
3.A出现奇数次、C出现奇数次;
三种情况。

我们用数组
f[n][0]保存长度为n,合法的字符串的个数。
f[n][1]保存长度为n,仅A出现奇数次的字符串的个数。
f[n][2]保存长度为n,仅C出现奇数次的字符串的个数。
f[n][3]保存长度为n,A、C出现奇数次的字符串的个数。

f[n][0]
长度为n-1的合法字符串在末尾加上一个B或者D,都可以变成长度为n的合法字符串。
长度为n-1的仅A出现奇数次的字符串再在末尾加上一个A,也可以变成合法字符串。
长度为n-1的仅C出现奇数次的字符串再在末尾加上一个C,也可以变成合法字符串。
所以,f[n][0] = 2 × f[n-1][0] + f[n-1][1] + f[n-1][2];

f[n][1]
长度为n-1的合法字符串在末尾加上A,都可以变成长度为n的仅A出现奇数次的字符串。
长度为n-1的仅A出现奇数次的字符串再在末尾加上一个B或者D,也可以变成仅A出现奇数次的字符串。
长度为n-1的A、C出现奇数次的字符串再在末尾加上一个C,也可以变成仅A出现奇数次的字符串。
所以,f[n][1] = 2 × f[n-1][1] + f[n-1][0] + f[n-1][3];

f[n][2]
长度为n-1的合法字符串在末尾加上C,都可以变成长度为n的仅C出现奇数次的字符串。
长度为n-1的仅C出现奇数次的字符串再在末尾加上一个B或者D,也可以变成仅C出现奇数次的字符串。
长度为n-1的A、C出现奇数次的字符串再在末尾加上一个A,也可以变成仅C出现奇数次的字符串。
所以,f[n][2] = 2 × f[n-1][2] + f[n-1][0] + f[n-1][3];

f[n][3]
长度为n-1的A、C出现奇数次的字符串在末尾加上一B或者D,都可以变成长度为n的A、C出现奇数次的字符串。
长度为n-1的仅A出现奇数次的字符串再在末尾加上一个C,也可以变成A、C出现奇数次的字符串。
长度为n-1的仅C出现奇数次的字符串再在末尾加上一个A,也可以变成A、C出现奇数次的字符串。
所以,f[n][3] = 2 × f[n-1][3] + f[n-1][1] + f[n-1][2];

综上所述,我们得到:
f[n][0] = 2 × f[n-1][0] + f[n-1][1] + f[n-1][2]; ①
f[n][1] = 2 × f[n-1][1] + f[n-1][0] + f[n-1][3]; ②
f[n][2] = 2 × f[n-1][2] + f[n-1][0] + f[n-1][3]; ③
f[n][3] = 2 × f[n-1][3] + f[n-1][1] + f[n-1][2]; ④

f[1][0] = 2
f[1][1] = 1
f[1][2] = 1
f[1][3] = 0

发现f[1][1]与f[1][2]初始状态相同,而且以后迭代方程也相同,所以f[n][1] = f[n][2]
又有f[n][0] + f[n][3] = f[n][1] + f[n][2]
∵f[n][0] + f[n][1] + f[n][2] + f[n][3] = 4n
∴f[n][0] + f[n][3] = f[n][1] + f[n][2] = 2 × 4n-1
∴f[n-1][1] + f[n-1][2] = 2 × 4n-2
∴f[n][0] = 2 × f[n-1][0] + f[n-1][1] + f[n-1][2] = 2 × f[n-1][0] + 2 × 4n-2

我们得到:
f[n][0] = 2 × f[n-1][0] + 22n-3
f[n-1][0] = 2 × f[n-2][0] + 22n-5

f[n-m][0] = 2 × f[n-m-1][0] + 22n-2m-3

f[2][0] = 2 × f[1][0] + 21
f[1][0] = 2

开始一层层往下迭代:
f[n][0]
= 2 × f[n-1][0] + 22n-3
= 22 × f[n-2][0] + 22n-4 + 22n-3

= 2m × f[n-m][0] + 22(n-m)-1+m-1 + … + 22n-3
= 2n-1 × f[1][0] + 2n-1 + 2n +… + 22n-3
f[1][0] = 2;

∴f[n][0] = 2n + 2n-1 + 2n +… + 22n-3 = 22n-2 + 2n-1

编码建议
Programing  公式得到了:f(n) = 22n-2 + 2n-1
但就这样直接编程那是不可能实现的,因为n的范围1≤N<264
怎么的范围,是不能求出f(n)的。所以还得找其他规律。
因为题目只要求输出最后2位数,我们依次输出2的n的最后两位看看…
20 -> 1
21 -> 2
22 -> 4
23 -> 8
24 -> 16
25 -> 32
26 -> 64
27 -> 28
28 -> 56
29 -> 12
210 -> 24
211 -> 48
212 -> 96
213 -> 92
214 -> 84
215 -> 68
216 -> 36
217 -> 72
218 -> 44
219 -> 88
220 -> 76
221 -> 52
222 -> 4
到了222时,末尾2位又变成4,与22一样,这时候就进入了一个循环了(每20个一次循环)。
所以,结果只能是这22个中的一个。只有n=0 和 n=1是需要特殊考虑的。其他n就等于2(n-2) % 20 + 2的值了。 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
#include <stdio.h>
 
int main(void)
{
        __int64 n;
        int c, t;
        int d[] = {
                 4, 8,16,32,64,28,56,12,24,48,
                96,92,84,68,36,72,44,88,76,52
        };
 
        while (scanf("%d", &t), t)
        {
                for (c = 1; c <= t; c++)
                {
                        scanf("%I64d", &n);
                        printf("Case %d: %d\n", c, n<3?(n<2?2:6):(d[(2*n-4)%20]+d[(n-3)%20])%100);
                }
                putchar('\n');
        }
 
        return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

发表评论

电子邮件地址不会被公开。 必填项已用*标注