题解：P13872 [蓝桥杯 2024 省 Java/Python A] 砍柴

· · 题解

拿到题目，我们首先注意到这是一个“公平组合游戏”，即可以进行的选择与角色无关（与之相对应的如常见的棋类，因为你不能动别人的棋）。

于是我们可以设一个一维布尔数组 dp，其中 dp[i] 表示当还剩 i 米的木头，先手玩家必输还是必胜（因为进行的策略最优，结局也是一定的）。

这个时候，我们再考虑对于一个元素 dp[i]。如果可以锯掉 p (2 \le p \le i) 米的木头，使得接下来的先手（也就是当前的“对方”）处于必败的局面（dp[i-p]=0），那么当前的局面就是必胜的（dp[i]=1），因为你可以找到一种移动使得对手处于必败的局面。反之，如果不存在这样的 p，那么当前局面就是必败的（dp[i]=0），因为你不管怎么走对手都是必胜的局面。

由这个结论，我们可以考虑转移方程：

dp[i]=\max(dp[i],1-dp[i-p])

其中 p 是枚举得的每一个满足 2 \le p \le i 的质数。

边界是 dp[0]=0 和 dp[1]=0。

答案是 dp[n]。

然后我们来考虑这种做法的时间复杂度。我们可以使用如下公式来估算 1 \sim i 范围内的质数个数：

\frac{i}{\ln i}

由于外层枚举 2 \sim n 的每一个数字 i，内层要处理约 \frac{i}{\ln i} 个质数，所以总的执行次数约为：

\sum_{i=2}^{n} \frac{i}{\ln i}

再加上 O(n) 的质数筛，时间复杂度为 O(\frac{n^2}{\ln n})，可以通过本题。

接下来是代码（C++）:

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+7;
bool inp[N+10];//标记每个数字是否不是质数。
vector<int> prime;//质数表
int dp[N+10];//递推数组
int main(){
    for(int i=2;i<=N;i++){
        if(!inp[i]) prime.push_back(i);//如果不是非质数（是质数）
        for(int j=0;j<prime.size()&&i*prime[j]<=N;j++){//用以筛掉非质数（线性筛）
            inp[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
    for(int i=2;i<=N;i++){//递推
        for(auto j:prime){
            if(j>i) break;//判断是否在范围内
            dp[i]=dp[i] || (!dp[i-j]);//只要有一个操作让对手必败就行，否则就是不行。
        }
    }
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        cout<<dp[n]<<'\n';//每次读入然后输出。
    }
}

然后是 python 版（需要 pypy3 提交）:

N=(10**5)+7
inp=[False for i in range(N+10)]
prime=[]
dp=[False,False]
for i in range(2,N+1):
    if not inp[i]:
        prime.append(i)
    for j in range(0,len(prime)):
        if i*prime[j]>N:
            break
        inp[i*prime[j]]=True
        if i%prime[j]==0:
            break
for i in range(2,N+1):
    dp.append(False)
    if not inp[i] or not inp[i-1]:#一点小优化，不然过不了。python常数太大了
        dp[i]=1
    else:
        for j in prime:
            if j>i:
                break
            dp[i]=dp[i] or (not dp[i-j])

t=int(input())
for i in range(t):
    p=int(input())
    print(int(dp[p]))