首页 > 试题广场 >

买彩票

[编程题]买彩票

热度指数：66 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小明热衷于买足球彩票多年而苦苦不能中奖。经过他近日的潜心研究，小明发现了一个提高中奖几率的方法。已知足球比赛有胜、负、平三种结果，小明的方法是，如果买一张含有n场比赛的彩票，那么相邻两场比赛的结果不能相同，且第一场比赛和最后一场比赛的结果也不能相同。请你帮小明算算，符合条件的彩票有多少种

输入描述:

输入一个整数N（0<=N<=50)，表示比赛的场数

输出描述:

输出一个整数M，表示满足条件的情况数

示例1

输入

输出

算法知识视频讲解

zxcv0112358

def func(n):
    if n&1:
      return 2
    else :
      return  -2 

n=int(input())
if n==0 :
    print(0)
elif n==1 :
    print(3)
else :
    print((2**n)-func(n))

这题建模的话，建个图就出来了。

邻接矩阵{{0,1,1},{1,0,1},{1,1,0}}

比如说，胜-负对应于图里长度为2的路径0-1-0

胜-负-平对应于图里长度为3的路径0-1-2-0

建完图后用矩阵幂算出图中长度为n的cycle个数

这也是邻接矩阵特征值的平方和

看https://www.cnblogs.com/yhm138/p/13358773.html也行

编辑于 2021-04-08 17:44:27 回复(0)

牛客7587184号

 def solve(n):
    """
    :param n:
    :return:
    """
    if n <= 1:
        return n * 3
    dp = [0]*n
    for i in range(1,n):
        dp[i] = 2**i - dp[i-1]
    res = dp[-1]*3
    # print(dp)
    # print(res)
    return res
 
 
def main():
    n = int(input())
    print(solve(n))
 
 
main()

发表于 2019-05-21 21:06:59 回复(0)