当前位置：首页 > article >正文

蓝桥杯砍柴

article 2025/3/11 0:06:03

题目

链接

思路

动态规划思想
核心就是从确定的东西推出确定的东西，并且使用空间换时间
详细题解见代码注释

代码

def is_zs(x):
    for i in range(2, int(x / 2 + 1)):
        if x % i == 0:
            return False
    return True


# 柴火数量
t = int(input())
# 柴火长度
n = []
for i in range(t):
    n.append(int(input()))
# 最长的柴火
n_max = max(n)
# 统计2~n_max之间所有的质数
zs=set()
for i in range(2,n_max+1):
    if is_zs(i):
        zs.add(i)
# 构建长度为n_max+1的数组a，a[i]表示木柴长度为i时，当前砍柴者是赢还是输
a = [0] * (n_max + 1)
for i in range(0, n_max + 1):
    # 如果当前砍柴者面临柴火长度i时一定会输，那么当其面临柴火长度i+p质数时，他一定会赢，因为他可以砍掉p，然后让对方输
    if a[i]==0:
        for j in zs:
            if i+j<=n_max:
                a[i+j]=1

for i in n:
    print(a[i])