Somnia1337

用户名：dotcpp0729277

访问量：1306

签　名：

等　　级
排　　名	12774
经　　验	955
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

吊坠 - Kruskal 算法
浏览：281

砍柴 - 预处理 & 记忆化搜索
浏览：310

你可能喜欢

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

砍柴 - 预处理 & 记忆化搜索

　　作者: Somnia1337　　　　发表时间：2024-04-18 09:40:12 浏览：310　|　评论：0　

原题链接：蓝桥杯2024年第十五届省赛真题-砍柴

#### 解题思路

博弈问题，预处理范围内的质数集，`boolean win(int x)` 用 DFS 判断当前剩余长度能否获胜，递归交换对手。

对 `win(x)`，二分质数集查询 $$\leqslant$$ `x` 的最大位置，倒序遍历，更快接近 DFS 基态，否则 $$10^5$$ 容易栈溢出。

#### 答案

![AC](/image_editor_upload/20240418/20240418093817_26616.png "AC")

```java
import java.util.*;
import java.io.*;

public class Main {
    private static int[] primes;
    private static int[] memo;
    
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        
        int n = Integer.parseInt(in.readLine());
        int[] arr = new int[n];
        
        // 取输入的最大值
        int max = 0;
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(in.readLine());
            max = Math.max(arr[i], max);
        }
        
        // 预处理质数
        getPrimes(max);
        memo = new int[max + 1];
        for (int x : arr) {
            out.println(win(x) ? 1 : 0);
        }
        
        out.flush();
        out.close();
    }
    
    // 筛法预处理得到范围内所有质数
    private static void getPrimes(int max) {
        boolean[] v = new boolean[max + 1];
        Arrays.fill(v, true);
        for (int x = 2; x <= max; x++) {
            if (!v[x]) continue;
            for (int y = x * 2; y <= max; y += x) {
                v[y] = false;
            }
        }
        int n = 0;
        for (int x = 2; x <= max; x++) {
            if (v[x]) n++;
        }
        primes = new int[n];
        int i = 0;
        for (int x = 2; x <= max; x++) {
            if (v[x]) primes[i++] = x;
        }
    }
    
    // DFS 博弈
    private static boolean win(int x) {
        if (memo[x] != 0) return memo[x] == 1;
        if (x <= 1) return false;
        // 剪枝: 倒序遍历质数集, 更快接近 DFS 基态
        for (int i = bis(x); i >= 0; i--) {
            if (!win(x - primes[i])) {
                memo[x] = 1;
                return true;
            }
        }
        memo[x] = -1;
        return false;
    }
    
    // 二分, 从质数集中查找 <= x 的最大位置
    private static int bis(int x) {
        int l = 0;
        int r = primes.length - 1;
        while (l <= r) {
            int m = l + r >> 1;
            if (primes[m] <= x) l++;
            else r--;
        }
        return r;
    }
}
```

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

Somnia1337

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

砍柴 - 预处理 & 记忆化搜索

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

【绝对值排序】（C语言代码）

printf基础练习2 （C++代码）（受教了，，%#o和%#x的用途）三人行，必有我师，，多看题解会有收获

C二级辅导-求偶数和（C语言代码）

C语言训练-邮票组合问题* （C语言代码）......

C二级辅导-等差数列（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

校门外的树（C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

Somnia1337

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

A+B for Input-Output Practice (VI) （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

砍柴 - 预处理 & 记忆化搜索

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

【绝对值排序】 （C语言代码）

printf基础练习2 （C++代码）（受教了，，%#o和%#x的用途）三人行，必有我师，，多看题解会有收获

C二级辅导-求偶数和 （C语言代码）

C语言训练-邮票组合问题* （C语言代码）......

C二级辅导-等差数列 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

校门外的树 （C语言代码）

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

　　评论区

【绝对值排序】（C语言代码）

C二级辅导-求偶数和（C语言代码）

C二级辅导-等差数列（C语言代码）

校门外的树（C语言代码）