hdu1438——钥匙计数

小灰灰 2021-10-26 11:58 361阅读 0赞

# 钥匙计数之一 #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 2136    Accepted Submission(s): 1018**

Problem Description

一把锁匙有N个槽，槽深为1，2，3，4。每锁匙至少有3个不同的深度且至少有1对相连的槽其深度之差为3。求这样的锁匙的总数。

Input

本题无输入

Output

对N>=2且N<=31，输出满足要求的锁匙的总数。

Sample Output

N=2: 0 N=3: 8 N=4: 64 N=5: 360 .. .. .. .. .. .. .. N=31: ... 注：根据Pku Judge Online 1351 Number of Locks或 Xi'an 2002 改编,在那里N<=16

Author

ecjtu\_zhousc

题目链接：

[http://acm.hdu.edu.cn/showproblem.php?pid=1438][http_acm.hdu.edu.cn_showproblem.php_pid_1438]

解题思路：

一道经典的递归思路题。

1.在填入i槽孔前已经是钥匙，那么第i位无论是哪个深度的槽孔都是钥匙。

2.在填入i槽孔前不是钥匙。

(1)i槽孔填入2/3成为钥匙，那么之前i-1个槽孔由1/4组成并且不为仅有1或者仅有4.

(2)i槽孔填入1/4成为钥匙，那么第i-1槽孔为4/1。

那么我们将这些加起来是不是就是答案呢？清楚这样一个思路后，我们就要进行计算。

a\[i\]+=a\[i-1\]\*4;//填入槽孔前已经是钥匙

a\[i\]+=\[2^(i-1)-2\]\*2;//填入2/3成为钥匙

temp=\[4^(i-2)-2^(i-2)\]\*2-b\[i-1\];//填入1/4成为钥匙

a\[i\]+=temp;

b\[i\]=a\[i-1\]\*2+temp;

可能你会有这样的想法：在计算temp时4^(i-2)，因为是4个数字随机，会出现例如这样的情况：

i=8。当前i-1为2314231，而现在该填入第i位4。而在填入前，i=7时已经是钥匙了。

temp计算时会减去b\[i-1\]，b\[i-1\]=a\[i-2\]\*2+填入1/4成为钥匙。

仔细思考一下，刚刚举过的例子在这里是被减去了的。

转载于:https://www.cnblogs.com/noback-go/p/11138028.html

[http_acm.hdu.edu.cn_showproblem.php_pid_1438]: http://acm.hdu.edu.cn/showproblem.php?pid=1438

发表评论取消回复

表情：

评论列表（有 0 条评论，361人围观）

还没有评论，来说两句吧...

相关阅读

相关 HDU 5701 中位数计数（数论）

题目链接：http://acm.hdu.edu.cn/viewcode.php?rid=17615323 位数定义为所有值从小到大排序后排在正中间的那个数，如果值有偶数个，通

曾经终败给现在/ 2022年09月23日 12:49/ 0 赞/ 186 阅读

相关万能钥匙-中间层

最近小菜刀重读《程序员的自我修养》，里面提到过一句名言：计算机科学领域的任何问题都可以通过增加一个间接的中间层来解决。上述名言概括了计算机系统软件体系结构的设计要点，

╰+哭是因爲堅強的太久メ/ 2022年09月03日 09:26/ 0 赞/ 407 阅读

相关计数dp hdu 4055 Number String

嗯，什么是计数dp我也不知道，这是第一次遇见类似的题目。题意：给一个只含‘I','D','?'三种字符的字符串，I表示当前数字大于前面的数字，D表示当前的数字小于前

红太狼/ 2022年08月19日 04:49/ 0 赞/ 262 阅读

相关公共钥匙盒

问题描述　　有一个学校的老师共用 N个教室，按照规定，所有的钥匙都必须放在公共钥匙盒里，老师不能带钥匙回家。每次老师上课前，都从公共钥匙盒里找到自己上课的教室的钥匙去开门，

偏执的太偏执、/ 2022年05月31日 05:13/ 0 赞/ 299 阅读

相关 HDU 4408 最小生成树计数

[传送门][Link 1] 思路：首先需要了解Matrix\_Tree定理 1.设 G是无向图的邻接表，D是无向图各个点的度数 2.令M=D-G，则M的任意n-1阶余子式

男娘i/ 2022年05月11日 08:10/ 0 赞/ 244 阅读

相关【5701 HDU】中位数计数（思维）

题目：[点击打开题目链接][Link 1] Problem Description：中位数定义为所有值从小到大排序后排在正中间的那个数，如果值有偶数个，通常取最中间的两个

太过爱你忘了你带给我的痛/ 2022年05月03日 06:28/ 0 赞/ 228 阅读

相关 P1438 无聊的数列

题目背景无聊的YYB总喜欢搞出一些正常人无法搞出的东西。有一天，无聊的YYB想出了一道无聊的题：无聊的数列。。。（K峰：这题不是傻X题吗）题目描述维护一个数

梦里梦外;/ 2022年01月12日 09:47/ 0 赞/ 336 阅读

相关 hdu1438——钥匙计数

钥匙计数之一 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Ot

小灰灰/ 2021年10月26日 11:58/ 0 赞/ 362 阅读

相关 1438C - Engineer Artem （构造）

[题目][Link 1] 思路：如横纵坐标相加为奇数则将对应位置的数变为奇数+1或不加，如横纵坐标相加为偶则将对应位置数变为偶数。这题我觉得要培养一种感觉，看到一

Love The Way You Lie/ 2021年07月17日 00:48/ 0 赞/ 322 阅读

相关 CCF 公共钥匙盒

一、试题问题描述　　有一个学校的老师共用N个教室，按照规定，所有的钥匙都必须放在公共钥匙盒里，老师不能带钥匙回家。每次老师上课前，都从公共钥匙盒里找到自己上课的教

爱被打了一巴掌/ 2021年06月24日 15:57/ 0 赞/ 334 阅读