首页 > 代码库 > HDU-1438 钥匙计数之一
HDU-1438 钥匙计数之一
http://acm.hdu.edu.cn/showproblem.php?pid=1438 钥匙计数之一
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 1328 Accepted Submission(s): 552
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
分析:若x是钥匙,则x加1,2,3,4.都是钥匙则a[i]=a[i-1]*4;
若x不是钥匙,加上2,3。就是钥匙了,这x是由1和4组成。但是要减去x是全1或者全4。a[i]+=(2^i-1-2)*2;
若x不是钥匙,加上1,4就是钥匙但是要减去x是由1和4组成。还要除去b[i-1],表示以1和4为结尾的个数,因为i的位置是1和4,i-1的位置就必修是4和1来配对,但是前面的计算,可能会造成i-2的位置有1和4,这样就不符合x不是钥匙,而且什么当x是钥匙的时候,已经算了一次,所以要除去i-1位置以1和4结尾的。
temp=(4^i-2-2^i-2)*2-b[i-1].
而此时,b[i]=a[i-1]*2+temp,a[i-1]*2是i-1是钥匙,然后加上1和4,temp上面本来就是结尾加上1和4.
#include<iostream>#include<cstdio>#include<cmath>using namespace std;__int64 pow(int x,int y){ int i; __int64 sum=1; for(i=1;i<=y;i++) sum*=x; return sum;}int main(){ __int64 temp,a[40],b[40]; int i; a[2]=b[2]=0; a[3]=8;b[3]=4; for(i=4;i<=31;i++) { a[i]=a[i-1]*4; a[i]+=pow(2,i)-4; temp=(pow(4,i-2)-pow(2,i-2))*2-b[i-1]; a[i]+=temp; b[i]=a[i-1]*2+temp; } for(i=2;i<=31;i++) printf("N=%d: %I64d\n",i,a[i]); return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。