题解 P4461 【[CQOI2018]九连环】
另外两篇题解中都给出了此题的通项公式,但对公式的分析过程稍略.这里我就简要说一下其中的思路与过程.(毕竟我只是个初三蒟蒻啊)
首先我们是可以通过分析题面中解四连环的思路来得到启示的.
初始状态为1111,每步的操作如下:
1.1101 (根据规则2,卸下第2 个环)
2.1100 (根据规则1,卸下第1 个环)
3.0100 (根据规则2,卸下第4 个环)
4.0101 (根据规则1,装上第1 个环)
5.0111 (根据规则2,装上第2 个环)
6.0110 (根据规则1,卸下第1 个环)
7.0010 (根据规则2,卸下第3 个环)
8.0011 (根据规则1,装上第1 个环)
9.0001 (根据规则2,卸下第2 个环)
10.0000 (根据规则1,卸下第1 个环)
这里我们可以看到,从第1步到第5步,实际上最终效果就变成了去解3连环.因为将最后一个环卸下后,前面的环卸下/装上都只取决于在它前面环的状态,与最后一个环无关.所以我们就可以不管最后一个环了,问题从解4连环转化成了解3连环.
至此,我们已容易想到,将解N连环的问题转化为解N-1连环,递归处理得出答案.可是,从N连环到N-1连环,需要多少步呢?我们只要解决了这个问题,整个问题也就解决了.
接下来我们解决从N环到N-1连环需要的步数.
此时,我们再去看题面中四连环的解决过程,仍看第一步至第五步.由规则2易知,为了取下第n个环,我们需要在保持第n-1个环不变的情况下(因为你动它对前面n-2个环没有影响),将前面的n-2个环全部取下.,即题面中第2步后的效果.
等等!
什么叫做将前面的n-2个环全部取下?这不就是解n-2连环吗? 我们再来看解掉前面n-2连环之后应该如何操作.此时已经符合了规则2的要求,我们用1步卸下第n个环,至此状态变成仅有第n-1个环在剑上,即题面中第3步后的效果.我们再看题面,可以得知接下来应该将后面的n-2连环全部装上去,就达到了卸下了第n个环,转移到n-1连环的目的.
此时整个过程已经明晰,即要解n连环,先解n-2连环,再下第n个环,再上n-2连环,再解n-1连环,是一个递归的过程.
那么我们只剩下最后一个问题,如何装上n-2连环?
要装上n-2连环,就先将第n-3个环装上,即装上n-3连环后,装上第n-2个环,又卸下n-4连环,再上n-3连环. 等等,这过程是不是有些眼熟?我们前面卸环的操作"要解n连环,先解n-2连环,再下第n个环,再上n-2连环,再解n-1连环" 跟这个上环的操作一一对应,且恰好相反!又因为上1连环和解1连环是互逆的,都只需一步,所以我们得到了一个十分关键的性质:上n-2连环的过程与解n-2连环的过程是互逆的!
至此,整个问题已经解决.前面说的"再上n-2连环"的步数就等于解n-2连环的步数.再回到
"要解n连环,先解n-2连环,再下第n个环,再上n-2连环,再解n-1连环".的思路.
我们用f(n)来表示解n连环所需的步数,初始易得有f(1)=1,f(2)=2,递推式有f(n)=f(n-2)+1+f(n-2)+f(n-1)=2f(n-2)+f(n-1)+1.学过线代的同学在这里适加操作就可以得到f(n)的通项公式,而如果不知道通项公式的求法,自己打表找一下规律(或许)就可以得出.
f(n)=1/6 (-3 + (-1)^(1 + n) + 2^(2 + n)).
简要写出来就是floor(2^(n+1)/3),接下来是高精度的实现这里就不再展开说明了.
(PS:因为要用高精度,没有试过直接基于递推公式来做的方法,可能要炸空间,况且为了卡进时间还要用到矩阵加速,组合起来代码十分复杂)
Conclusion:此题来源于我国古代的一个益智游戏,不仅是最后的答案是递归的方式,解题过程中的分析也是通过递归思想,逐步解决问题(古人的智慧).
PS:python大法好
import sys
f=[0 for x in range(100010)]
if True :
f[1]=1
f[2]=2
for i in range(3,100010):
f[i]=2*f[i-2]+f[i-1]+1
for i in range(int(input())):
print(f[input()])