钥匙计数之一
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0 Problem Description
一把锁匙有N个槽，槽深为1，2，3，4。每锁匙至少有3个不同的深度且至少有1对相连的槽其深度之差为3。求这样的锁匙的总数。
Input
本题无输入
Output
对N>=2且N<=31，输出满足要求的锁匙的总数。
Sample Output
N=2: 0N=3: 8N=4: 64N=5: 360..............N=31: ...注：根据Pku Judge Online 1351 Number of Locks或 Xi'an 2002 改编,在那里N<=16
Author
ecjtu_zhousc
递推方程式如下
1：如果X是钥匙， 则X1/2/3/4也是， 所以a[I]=a[I-1]*4
2: 如果X不是， X2/3是则X由1/4组成， 但要除去全1和全4， 所以a[I]+=(2^(I-1)-2)*2
后缀2或者3加上就成为钥匙的话，必然是没满足需要3个不同深度槽这一项，故X必然由1/4组成
3 如果X不是 X1/4是。则X=Y（1/4） M=X1/4=Y（4/1）（1/4）
前I-2位可以是1234，但要除去全为1/4的情况 还有就是X是钥匙且X是以1/4结尾
的情况。我们用b[I]数组表示i位时以1/4结尾的的数量
temp=（4^(i-2)-2^(i-2)）* 2 - b[i-1];
则 b[i]=a[i-1]*2+temp;
#include<stdio.h> #include<math.h>
int main () {
int i;
__int64 temp, a[32], b[32]; //b[i]记录以1 4结尾的数
a[2] = 0;
a[3] = 8; b[2] = 0; b[3] = 4;
printf ("N=2: 0\\nN=3: 8\\n"); for (i = 4; i <= 31; i++) {
a[i] = a[i - 1] * 4;
a[i] += (__int64) pow (2,i) - 4; //以2 3 结尾的
temp = ((__int64) pow (4,i-2) - (__int64) pow (2, i - 2)) * 2 - b[i - 1]; a[i] += temp;
b[i] = a[i - 1] * 2 + temp;
printf ("N=%d: %I64d\\n", i, a[i]); }
return 0; }
钥匙计数之二
Time Limit : 2000/1000ms (Java/Other) Memory Limit : 65536/32768K (Java/Other)
Total Submission(s) : 0 Accepted Submission(s) : 0 Problem Description
一把钥匙有N个槽，2<N<26槽深为1，2，3，4,5,6。每钥匙至少有3个不同的深度且相连的槽其深度之差不得为5。求这样的钥匙的总数。
Input
本题无输入
Output
对2<N<26，输出满足要求的钥匙的总数。
Sample Output
N=3: 104N=4: 904N=5: 5880.....N=25: 8310566473196300280
张志坚，华东交通大学ACM退役队员
设lock[i]表示：有 i个槽的钥匙的个数
设one[i]表示：有 i个槽且左边第一个槽深度为1的钥匙的个数 设two[i]表示：有 i个槽且左边第一个槽深度为2的钥匙的个数 .. ..
设six[i]表示：有 i个槽且左边第一个槽深度为6的钥匙的个数
则显然：lock[i]=one[i]+two[i]+ three[i]+four[i]+five[i]+six[i]
由于易知：one[i]=six[i],two[i]=three[i]=four[i]=five[i] 则可以得到：lock[i]=one[i]*2+two[i]*4
其中：
one[i]=one[i-1]+two[i-1]+three[i-1]+four[i-1]+five[i-1]+a[i]; =one[i-1]+two[i-1]*4 +a[i]
two[i]=one[i-1]*2+two[i-1]*4 +b[i]
其中，a[i] 和b[i]的含义分别是： a[i]表示“有 i个槽且左边第一个槽深度为1，同时这种钥匙在除掉第一个槽后不再是钥匙”的钥匙的个数。
例如 123,124,125,134,135,145,126,136,146,156 就属于这种情况。
b[i]表示“有 i个槽且左边第一个槽深度为2，同时这种钥匙在除掉第一个槽后不再是钥匙” 的钥匙的个数。
分析到这里，可以知道，关键的是求a[i]和b[i]，我们可以得到如下表达式： a[i]=(2^(i-1)-2)*6+(2^(i-2)-1)*4
b[i]=(2^(i-1)-2)*9
其中，a[i] 的各部分的含义如下： (2^(i-1)-2)*6： 当去掉第一位，后面i-1位只有 (2,3)或者 (2,4) 或者(2,5) 或者(3,4) 或者(3,5) 或者(4,5)两种数字的时候，显然是不合法的钥匙（不满足至少有3个不同的深度），加上第一位的1则显然是一个合格的钥匙。所以后面的数字可以为一个组合中两个数字的任意一个，根据乘法原理i-1位一共有2^(i-1)种组合，当然还需要去掉两种特殊情况，就是后面i-1位完全相同的情况。满足这种条件的一共有上面六种组合，所以得到(2^(i-1)-2)*6。 (2^(i-2)-1)*4：
当去掉第一位，后面i-1位只有 (2,6)或者 (3,6) 或者(4,6) 或者(5，6)两种数字的时候，显然是不合法的钥匙（不满足至少有3个
不同的深度），加上第一位的1则“可能”是一个合格的钥匙。因为要注意满足“相连的槽其深度之差不得为5”这个条件，所以，紧跟着1的绝对不能是6，这样，相对于上面的分析，后面i-2位可以是每组中的任意一个，所以有2^(i-2)，还要减去1是因为同样要排除后面全部是和第2位一样的数字这样的情况。满足这种条件的一共有上面的四种组合，所以得到(2^(i-2)-1)*4。
b[i] 的含义如下： (2^(i-1)-2)*9： 当去掉第一位，后面i-1位只有 (1,3)或者 (1,4) 或者(1,5) 或者(3,4) 或者(3,5) 或者(3,6) 或者(4,5) 或者(4,6) 或者(5,6) 两种数字的时候，显然是不合法的钥匙（不满足至少有3个不同的深度），加上第一位的1则显然是一个合格的钥匙。所以后面的数字可以为一个组合中两个数字的任意一个，根据乘法原理i-1位一共有2^(i-1)种组合，当然还需要去掉两种特殊情况，就是后面i-1位完全相同的情况。满足这种条件的一共有上面9种组合，所以得到(2^(i-1)-2)*9。
目前为止，我们可以求出所有的a[i]和b[i]，而且知道了递推关系，只要再做一点简单的工作就可以了，那就是还需要初始值，当然，很容易枚举出最简单的情况
one[3]=16; two[3]=18;
这样，整个问题就解决了。 特别说明：
这种递推的题目，就是从f(i-1) 加一个元素，然后枚举出所有可能的情况，推导到f(i),当然这个题目有点麻烦，但是套路是一样的，大家也可以参考一下以前的special number课件,里面对于hdoj_1133 Buy the Ticket这个题目的分析，里面的思路和这个完全一样。
#include<stdio.h> #include<limits.h> #include<math.h> #include<float.h> _int64 t1[27],t2[27]; _int64 a,b; int main() { int i; t1[3]=16; t2[3]=18;
printf("N=3: 104\\n"); for(i=4;i<=25;i++) {
a=((__int64)pow(2,i-1)-2)*6+((__int64)pow(2,i-2)-1)*4; b=((__int64)pow(2,i-1)-2)*9; t1[i]=t1[i-1]+t2[i-1]*4+a; t2[i]=t1[i-1]*2+t2[i-1]*4+b;
printf("N=%d: %I64d\\n",i,t1[i]*2+t2[i]*4); }
return 0; }