这组我们讨论了hdoj2065——“红色病毒”问题
题目链接-http://acm.hdu.edu.cn/showproblem.php?pid=2065
"红色病毒"问题
医学界发现的新病毒因其蔓延速度和Internet上传播的"红色病毒"不相上下,被称为"红色病毒",经研究发现,该病毒及其变种的DNA的一条单链中,胞嘧啶,腺嘧啶均是成对出现的。
现在有一长度为N的字符串,满足一下条件:
(1) 字符串仅由A,B,C,D四个字母组成;
(2) A出现偶数次(也可以不出现);
(3) C出现偶数次(也可以不出现);
计算满足条件的字符串个数.
当N=2时,所有满足条件的字符串有如下6个:BB,BD,DB,DD,AA,CC.
由于这个数据肯能非常庞大,你只要给出最后两位数字即可.
Input
每组输入的第一行是一个整数T,表示测试实例的个数,下面是T行数据,每行一个整数N(1<=N<2^64),当T=0时结束.
Output
对于每个测试实例,输出字符串个数的最后两位,每组输出后跟一个空行.
Sample Input
4
1
4
20
11
3
14
24
6
0
Sample Output
Case 1: 2
Case 2: 72
Case 3: 32
Case 4: 0
Case 1: 56
Case 2: 72
Case 3: 56
一开始我们就觉得这应该跟递推公式有关，即a[n]=x*a[n-1]+y*a[n-2] , 然后想办法找到系数x,y。
通过计算前几种情况：
1 = 2 （种）；
2 = 2*2+2 = 6 ；
3 = 2*2*2 + 3*2*2 = 20 ；
4 = 2*2*2*2 + 6*2*2*2 +（6+2）=72；
然后终于总结出数学公式：f(n) = 2^(2n-2) + 2^(n-1);
显然这并不是我们想要的递推公式，但通过测试，答案是对的，就先用这个进行。
设计函数：
int pow1(long long x)
{
int r=1;
while (x--)
{
r = r * 2 % 100;
}
return r;
}
用a=pow1(2*n-2),b=pow1(n-1)计算结果，再以sum=(a+b)%100得到答案;
测试结果和答案相比正确，然后由于题目给的数可以很大(1<=n<2^64),
就产生时间问题：当数据很大时，时间用了很久，我们随便输入个几百万，或者几千万，居然要等上一两秒。
试着提交，果不其然Time Limit Exceeded。
然后我们想到题目给的数这么大，又只保留后两位，说不定这两位数到一定程度会开始循环。
果不其然，测试了前50个答案，3和23答案相同，然后就开始循环了，周期为20，只有1，2是特殊的。
那就提前用数组把答案记录下来，在查看n是周期内的哪个数就ok了。
ac代码：
#include <iostream>
#include<algorithm>
using namespace std;
int pow1(int x) //计算公式
{
int r=1;
while (x--)
{
r = r * 2 % 100;
}
return r;
}
int main()
{
int a;
long long x = 0;
int n[30] = { 0 };
for (int i = 1; i < 30; i++) //记录答案
{
int t1 = 0;
int t2 = 0;
t1 = pow1(2 * i - 2);
t2 = pow1(i - 1);
n[i] = t1 + t2;
}
while (cin >> a)
{
if (a == 0) return 0;
int i = 1;
while (a--)
{
int sum = 0;
cin >> x;
if(x<=22)
cout <<"Case "<<i++<<": "<< n[x] % 100<<endl;
else {
x = (x-3) % 20+3 ; //求位置
cout << "Case " << i++ << ": " << n[x] % 100 << endl;
}
}
cout << endl;
}
return 0;
}
总结：
说到底还是一道数学题，往往难在找到其中的规律。
然后还是在网上找到了这道题的递推公式：a[n] = 6*a[n-1]-8*a[n-2]。
还有构造母函数的解题过程（不太懂）
很多时候做题不是解决一种问题，而是学习一种新的知识，或者说发现自己不足的地方。
这道题告诉我们，虽然递推的概念懂了，但真正做起题来，找不到规律，没有扎实的数学功底。就还是很难受。
ps：小组成员进度不太一样，所以讨论笔记一般会一起选择一道比较难的题来攻关。然后因为一开始都卡住了，都不知道要说什么，感觉笔记写的跟我个人来做题差不多了（心塞。。。）
不过有机会还是要多一起做题，一来知道小组的水平，二来也可以清楚组员的进度
