Hdu1480钥匙计数之二解题报告.doc

Hdu1480钥匙计数之二解题报告/* Name: hdu1480 Copyright: ecjtu_acm训练基地 Author: yimao Date: 17-06-10 20:59 Description: 解题报告*/一、题目Problem Description一把钥匙有N个槽，2N26槽深为1，2，3，4,5,6。每钥匙至少有3个不同的深度且相连的槽其深度之差不得为5。求这样的钥匙的总数。 Input本题无输入Output对2N26，输出满足要求的钥匙的总数。Sample OutputN=3: 104N=4: 904N=5: 5880.N=25: 8310566473196300280二、题目分析提交完本题后，颇觉有递推的味道。出发点：构造结果ansn=num1+num6;其中numi表示以i为最后一个槽的高度；计算出numi，从而得出结果。首先进行初始化分析，即n=3时。“相连的槽其深度之差不得为5”1，6这两个高度不能相邻；而2，3，4，5这四个高度等价，且之后n=4，5，25的计算过程中均有此规律。即num1=num6，num2=num3=num4=num5，在写代码时注意到这点便可以不需要用到数组；num1=num6=16;num2,3,4,5=18;ans3=104;（下面是重点）再由n-1递推分析n的情况：1、 当前面n-1个排列是钥匙的排列，则A、 对2，3，4，5作为第n个高度来说都能满足题意，有num2,3,4,5=ansn-1;B、 对1，6（1，6等价，记号不同而已）来说，第n-1个高度不能为6，1，即要去掉几个不符合题意的组合；num1=ansn-1-num_6(前n-1个中最后一个为6的个数，实际写代码时要用另一个数组保存)。同理 num6=ansn-1-num_1()。也即num1,6=ansn-1-num_6();2、 当前面n-1个排列不是钥匙的排列，则A、对i（i=2，3，4，5）作为第n个高度来说能满足钥匙的要求，则说明前面n-1个排列里仅有两类高度，且与i不同，加上i就刚好3类高度满足题意。那么前面两类高度的选法总数是从其余5类高度里选出两类，即C（5，2），但1，6不能同时选，故组合数为C（5，2）-1。 再看排列数，n-1个位置，每个位置可任选两类，但不能全部是同一类高度，故排列数2(n-1)-2。B、对i=1，6，同上面分析。因为1，6等价，所以我这里举i=1来说，前面两类高度里我有两种取法，选6和不选6。对于选6，组合数是C（4，1）（剩下2，3，4，5任意选一）；再看排列数，每个位置可任选两类，但不能全部是同一高度，且最后一个也即第n-1个位置处不能为6，也可换个说法，最后一个位置放i（i=2，3，4，5），前面n-2个位置任选6和i放，排列数42(n-2)。对于不选6，组合数是C（4，2）；再看排列数，每个位置可任选两类，且不能全部是同一类高度，排列数2(n-1)-2。把上面的组合数与排列数相乘便得到一种情况下的numi的值，所有情况的值相加便得到结果。三、代码（从简）/*Accepted 1480 0MS 192K 743B G+ */ t6=16;ans3=104; for(i=4;i26;i+) /前n-1是钥匙的情况； num1=ansi-1-t6; num2=ansi-1; /前n-1不是钥匙的情况； num1+=c42*(mult(2,i-1)-2); /不含有6；mult()算阶乘； num1+=4*(mult(2,i-2)-1); /含有6； num2+=(c52-1)*(mult(2,i-1)-2); ansi=2*num1+4*num2; t6=num1; /*以上代码可以不写mult函数，在数据量大的情况下能省很多时间，请读者自己思考，以上代码可以不写数组，在数据量大的情况下能省内存占用。希望读者完善之*/四、总结(略)刚开始接触这题，有点恐惧，尽管自己手动分析了n=3，4的情况，感觉情况似乎很多种，不敢往下接着想，和以前做这类题一样，以为会有什么很高深的数学公式可以用，就没有继续下去。AC完后就会有似曾相识的感觉，类似于/showproblem.php?pid=3284这类由n-1递推到n的题，其实还有好几道，只是一时没找不到，发现这类题的共同点就是选定某个位置作为结果的一部分，用数组保存，n-1到n之间由这个数组来递推。本题hdu1480网上还有一个十分详细的解题报告（/blog/article.asp?id=45140），本人未看，不知是否大体相同，若看不懂本解题报告，可参考之。 hdu 1480 钥匙计数之二 一把钥匙有N个槽，2N26槽深为1，2，3，4,5,6。每钥匙至少有3个不同 的深度且相连的槽其深度之差不得为5。求这样的钥匙的总数。解题分析 keyn是有n个槽的钥匙的总数，numi是最后一个槽的高度为i的钥匙总数 n=3时 abc 是 钥匙且c=1, 则 b！=6，b=2,3,4,5有4种，a是除c，b 外的4种，因此有 3个槽且最后一个槽高为1的 钥匙有 16种,记为 num1=16; 如果 abc是 钥匙, 则 (7-a)(7-b)(7-c) 也是 例如 1234是 钥匙 则 6543 也是 这说明 numi=num7-i,num1=num6; abc 是 钥匙且c=2, 则 a,b 是 1,3,4,5,6中挑2个但不挑(1,6)，有c(5,2)-1=9种，因此有 3个槽且最后一个槽高为2的 钥匙有 9*2=18种, num2=18; 易知 num2=num3=num4=num5; n=3, key3=num1+.+num6=104;设numi和tempi分别是n-1和n个槽的最后槽高为i的钥匙总数1、设 * 是n-1个槽的钥匙，则 *d是 n个槽的钥匙，d=2,3,4,5. 即tempd=keyn-1+s; 设 * 不是n-1个槽的钥匙， *d是 n个槽的钥匙，d=2,3,4,5. 则 *是除d外的两个数字构成且这两个数字不能是(1,6) ，有 s=（c(5,2)-1）*（2(n-1)-2）=9*（2(n-1)-2）种 即 tempd=keyn-1+ 9*（2(n-1)-2）; 2 设 * 是n-1个槽的钥匙且最后槽高不为6，则 *1是 n个槽的钥匙。 即 temp1=keyn-1-num6+s; 设 * 不是n-1个槽的钥匙， *1是 n个槽的钥匙 则 * 由2,3,4，5中的两个构成 有c(4,2)*(2(n-1)-2)种，再加 *由2,3,4，5中的