15届蓝桥杯省赛Java A 组Q6：砍柴

题目链接蓝桥云课砍柴洛谷P13872 [蓝桥杯 2024 省 Java/Python A] 砍柴算法原理错误解法贪心参照第 487 场周赛Q2——3828. 删除子数组后的最终元素的思路我们可以思考一下有没有让其中一方尽量稳赢的情况那就贪心的每次都砍最多的因此我们采用埃氏筛快速找到小于当前木头长度的最大质数快速降到0或1然后看最后剩下的是谁谁就输错误原因①3828题贪心正确的原因无论双方怎么操作最终剩下的元素只能是原数组的nums[0]或nums[n-1]先手玩家有绝对控制权局部最优全局最优因此贪心是正确的②真博弈论与伪博弈论3828题看似两个玩家间的博弈本质上是“找数组首尾最大值”并非真正的博弈而此题的局部最优≠全局最优拿n15举例贪心时小蓝选最大质数13剩15-132小乔选2→小蓝选了最大质数13小蓝却输了不贪心时小蓝选质数5剩15-510小乔选2剩8小蓝选7小蓝一开始选质数5小蓝赢了小乔选3剩7小蓝选7小蓝一开始选质数5小蓝赢了小乔选5剩5小蓝选5小蓝一开始选质数5小蓝赢了小乔选7剩3小蓝选3小蓝一开始选质数5小蓝赢了因此贪心在此题是错误的正确解法动态规划时间复杂度O(MAX_N T)①状态表示dp[x] 1先手必胜dp[x] 0先手必败②状态转移方程只要存在一个质数 p让对手面对x-p时处于必败态此玩家就可以选这个p来赢→dp[x]1如果所有质数 p 都会让对手进入必胜态当前玩家无论怎么选都输→dp[x]0③初始化dp[0]0dp[1]0当长度为 0 或 1 时无法进行任何砍柴操作当前玩家直接输 → 必败态④填表顺序从左往右⑤返回值对于输入的木头长度n直接返回预处理好的dp[n]若 dp[n] 1 → 小蓝先手赢若 dp[n] 0 → 小乔后手赢欧拉筛(线性筛)算法思路①初始化用布尔数组 isprime[] 标记每个数是否为质数初始时全部设为 true再将 0 和 1 标记为 false用列表 primes 存储所有筛出的质数②遍历每个数 i从 2 到 MAX_N若 isprime[i] 为 true说明 i 是质数将其扔进 primes遍历已筛出的所有质数 p若 i * p 超过 MAX_N直接终止循环避免溢出标记 isprime[i*p] falsep的 i 倍都不是质数这一点类似埃氏筛以前涉及到埃氏筛的题第 479 场周赛Q2——3770. 可表示为连续质数和的最大质数16届蓝桥杯省赛Java B 组的Q4优化保证线性复杂度O(N)若 i % p 0立即终止循环避免重复筛除比如 i4时primes[2,3]p3时我们会把4×312标记为非质数当 i6时primes[2,3,5]p2时我们会再次把6×212标记一次非质数此时我们会发现12被重复筛选了两次标记了两次但如果我们加上判断 i%p0 breaki4时primes[2,3]p2时我们会把4×28标记为非质数4%20直接break根本不会标记到12i6时primes[2,3,5]p2时才把6×212标记一次非质数这种“每个合数只被最小质因子标记一次”保证了不会有重复筛选从而保证了线性复杂度O(N)Java代码import java.util.*; public class Main{ //错误解法贪心 public static void main(String[] args){ Scanner scnew Scanner(System.in); int nsc.nextInt(); int[] anew int[n]; int[] retnew int[n]; for(int i0;in;i){ a[i]sc.nextInt(); int cnt0; while(a[i]2){ a[i]-prime(a[i]); cnt; } if(cnt%2!0) ret[i]1; } for(int i0;in;i) System.out.println(ret[i]); sc.close(); } //获取n内的最大质数 private static int prime(int n){ //埃氏筛 boolean[] isprimenew boolean[n1]; for(int i2;in;i) isprime[i]true; for(int i2;in;i){ if(isprime[i]){//若i是质数 for(int ji*i;jn;ji) //则i平方后的所有倍数全不是质数 isprime[j]false; } } for(int in;i2;i--) if(isprime[i]) return i; //照顾编译器 return -1; } }import java.util.*; public class Main{ //正确解法动态规划 private static final int MAX_N100_000; private static boolean[] isprime; //存储欧拉筛的结果 private static ListInteger primes; //dp[x]1数为x时先手必胜 //dp[x]0数为x时先手必败 private static int[] dp; static{ isprimenew boolean[MAX_N1]; primesnew ArrayList(); Arrays.fill(isprime,true); isprime[0]isprime[1]false; //欧拉筛核心逻辑保证每个合数只被其最小质因子筛除时间复杂度O(N) for(int i2;iMAX_N;i){ if(isprime[i]) primes.add(i); //遍历已找到的质数筛除i*p的合数 for(int p:primes){ //防止整数溢出i*p超过MAX_N时无需继续筛除 if(1L*i*pMAX_N) break; //标记i*p为非质数 isprime[i*p]false; //避免同一个合数被多个因子重复筛除保证线性复杂度 if(i%p0) break; } } //动态规划计算胜负状态 dpnew int[MAX_N1]; //dp[0]0、dp[1]0数为0或1时无法操作先手必败 dp[0]0; dp[1]0; for(int x2;xMAX_N;x){ //初始化为必败 boolean winfalse; //遍历所有质数尝试减去一个质数p看是否能让对手必败 for(int p:primes){ if(px) break; //如果减p后能让对手必败则当前x为必胜态 if(dp[x-p]0){ wintrue; break;//找到一种必胜策略即可 } } dp[x]win?1:0; } } public static void main(String[] args){ Scanner scnew Scanner(System.in); int Tsc.nextInt(); while(T--0){ int nsc.nextInt(); //直接输出预处理的结果 System.out.println(dp[n]); } sc.close(); } }