计算机变换(Computer Transformations,ACM,ICPC SEERC 2005,UVa1647)

找规律的题目,首先要列举几个,以发现规律

第一次展开:01

有1个0,1个1,1个01

第二次展开:1001

有2个0,2个1,1个00,1个01,1个10

第三次展开:01101001

有4个0,4个1,1个00,3个01,2个10,1个11

这时可以发现这道题好像存在递推规律,且第i次展开可能只与第i-1次字符串的状态有关

那么该如何思考?

我们发现如下规律:

对于某个序列

1,序列中00这个串只能由上一次01经过展开后得到

01 -> 1(00)1

2,01这个串,要么由上一次的1直接展开得到,要么由上一次的00展开得到

00 -> 1(01)0

3,10这个串,要么由上一次的0直接展开得到,要么由上一次的11展开得到

11 -> 0(10)1

4,11这个串,只能由上一次10展开得到

10 -> 0(11)0

那么,现在,

我们设第i个串中出现0的次数为f[i][0],出现1的次数为f[i][1],出现00的次数为f[i][2],出现01的次数为f[i][3],出现10的次数为f[i][4],出现11的次数为f[i][5]

求得递推式如下:

由于本题要高精度,所以我写了个python的代码懒的写高精度

f=[[0 for i in range(0,7)] for j in range(0,1010)]

if __name__=="__main__":
    f[1][3]=1;f[1][0]=1;f[1][1]=1
    for i in range(2,1005):
        f[i][0]=f[i-1][0]+f[i-1][1]
        f[i][1]=f[i-1][1]+f[i-1][0]
        f[i][2]=f[i-1][3]
        f[i][3]=f[i-1][1]+f[i-1][2]
        f[i][4]=f[i-1][0]+f[i-1][5]
        f[i][5]=f[i-1][4]
    try:
        while True:
            n=eval(input())
            print(f[n][2])
    except EOFError:
        pass
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 13:15
点赞 评论 收藏
分享
Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务