BZOJ2656 [ZJOI2012]数列(sequence)

2014.12.23 13:11 Tue| 1 visits oi_2015| 2015_刷题日常| Text

Solution

Python 大水题!!!

刚刚知道a={}原来是建立了一个字典,相当于C++的map。真是厉害!

不知道为什么用input()就会WA,而用raw_input()就可以AC。更可怕的是raw_input()在我的电脑上面的Python3.4里面完全没法运行……搞得我还现下载了一个Python2.7……

Code

m={}
def f(n):
    if(n==0): return 0
    if(n==1): return 1
    if(n in m): return m[n]
    if(n&1):
        m[n]=f(n//2)+f(n//2+1)
    else:
        m[n]=f(n//2)
    return m[n];

t=int(raw_input())
while(t):
    n=int(raw_input())
    print(int(f(n)))
    t=t-1