这是一个功能完善的C++数据生成器。它集成了标准DP解题代码（用于生成.out文件）和分级数据生成策略（用于生成.in文件），能够自动生成 1 到 10 号测试点，完全覆盖题目要求的三个子任务及各种边界情况。

🛠️ 功能特点

1. 自动化生成：一键生成 1.in/1.out ~ 10.in/10.out。
2. 覆盖子任务：
   • Points 1-2：Subtask 1 ($p_i=1, c_i=1$, 小数据)。
   • Points 3-4：Subtask 2 ($c_i=1, Q=2$)，贪心策略特例。
   • Points 5-10：Subtask 3 (通用情况)，包含小数据、大容量、大价值、极限边界等多种场景。
3. 合法性保证：所有生成的数据均严格遵守 $N \le 100, P,Q \le 50000$ 等题目约束。

📄 Generator 代码 (C++14)

/**
 * P11377 [GESP202412 七级] 武器购买 - 数据生成器
 * 
 * 包含：
 * 1. Solver: 标准 DP 解法，用于生成 .out
 * 2. Generator: 针对不同 Subtask 的数据构造逻辑
 * 
 * 使用方法：
 * 编译并运行该程序，当前目录下会自动生成 1.in/1.out 到 10.in/10.out
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <fstream>
#include <random>
#include <ctime>
#include <string>

using namespace std;

// ==========================================
// Part 1: 标准解题 Solver (用于生成 .out)
// ==========================================

namespace Solver {
    const int MAXQ = 50005;
    int dp[MAXQ]; // dp[j]: 花费不超过 j 时的最大强度

    // 单组数据求解
    int solve_one_case(int n, int P, int Q, const vector<pair<int,int>>& items) {
        // 清空 DP 数组
        memset(dp, 0, sizeof(dp));
        
        // 0/1 背包 DP
        for (const auto& item : items) {
            int p_val = item.first;
            int c_cost = item.second;
            // 逆序遍历
            for (int j = Q; j >= c_cost; --j) {
                dp[j] = max(dp[j], dp[j - c_cost] + p_val);
            }
        }
        
        // 寻找满足条件的最小花费
        for (int j = 0; j <= Q; ++j) {
            if (dp[j] >= P) {
                return j;
            }
        }
        return -1;
    }
}

// ==========================================
// Part 2: 数据生成器 Generator
// ==========================================

mt19937 rng(time(0));

int random_int(int l, int r) {
    if (l > r) return l;
    return uniform_int_distribution<int>(l, r)(rng);
}

struct TestCase {
    int n, P, Q;
    vector<pair<int, int>> items; // {p, c}
};

// 生成一个测试点的具体数据
void generate_file(int file_id) {
    string in_name = to_string(file_id) + ".in";
    string out_name = to_string(file_id) + ".out";
    ofstream fin(in_name);
    ofstream fout(out_name);
    
    // 确定该文件包含多少组测试数据 T
    int T = 10; 
    // 对于计算量较大的点，适当减少 T，虽然 N=100 很小，跑满也没问题
    // 为了生成速度和文件大小平衡，大部分设为 5-10
    if (file_id >= 8) T = 5; 
    
    fin << T << "\n";
    
    cout << "Generating Case " << file_id << " (" << T << " tests)..." << endl;

    for (int t = 0; t < T; ++t) {
        int n, P, Q;
        vector<pair<int, int>> items;
        
        // =================================
        // 策略路由：根据 file_id 决定数据特征
        // =================================
        
        // --- Subtask 1: n<=10, p=1, c=1, P,Q<=10 ---
        if (file_id == 1) { // 极小数据
            n = random_int(1, 5);
            items.resize(n, {1, 1});
            P = random_int(1, n + 2); // 有概率买不起
            Q = random_int(1, n);
        }
        else if (file_id == 2) { // 稍微多一点
            n = 10;
            items.resize(n, {1, 1});
            // 50% 概率 P <= n (有解), 50% 概率 P > n (无解)
            if (random_int(0, 1)) P = random_int(1, n);
            else P = random_int(n + 1, 20);
            Q = random_int(1, 10);
        }
        
        // --- Subtask 2: n<=100, c=1, Q=2 ---
        else if (file_id == 3) { // n=50, 随机强度
            n = 50;
            Q = 2;
            for(int i=0; i<n; ++i) items.push_back({random_int(1, 100), 1});
            // 计算一下所有物品最大可能的2个之和，构造 P
            vector<int> vals;
            for(auto p : items) vals.push_back(p.first);
            sort(vals.rbegin(), vals.rend());
            int max_2 = vals[0] + vals[1];
            
            // P 在 max_2 附近波动，测试边界
            P = max_2 - random_int(-10, 10);
            if (P <= 0) P = 1;
        }
        else if (file_id == 4) { // n=100, 大强度
            n = 100;
            Q = 2;
            for(int i=0; i<n; ++i) items.push_back({random_int(10000, 50000), 1});
            P = random_int(20000, 80000); 
        }
        
        // --- Subtask 3: n<=100, 通用情况 ---
        else if (file_id == 5) { // 小规模通用
            n = 20;
            P = random_int(50, 200);
            Q = random_int(50, 200);
            for(int i=0; i<n; ++i) {
                items.push_back({random_int(1, 20), random_int(1, 20)});
            }
        }
        else if (file_id == 6) { // 大 Q (也就是几乎可以随便买)，考验 P
            n = 50;
            Q = 50000; // 即使 c_i 很大也能买很多
            int sum_p = 0;
            for(int i=0; i<n; ++i) {
                int p = random_int(100, 1000);
                int c = random_int(1, 1000); // c 较小
                items.push_back({p, c});
                sum_p += p;
            }
            P = random_int(sum_p / 2, sum_p + 100); // 也是在总和附近波动
        }
        else if (file_id == 7) { // 大 P，小 Q (很容易无解)
            n = 50;
            Q = random_int(10, 100);
            P = 50000; 
            for(int i=0; i<n; ++i) {
                items.push_back({random_int(1, 100), random_int(1, 50)});
            }
        }
        else if (file_id == 8) { // 随机中等规模
            n = 80;
            P = random_int(1000, 10000);
            Q = random_int(1000, 10000);
            for(int i=0; i<n; ++i) {
                items.push_back({random_int(1, 500), random_int(1, 500)});
            }
        }
        else if (file_id == 9) { // 强度和花费都很大
            n = 100;
            // 构造大背包，P 和 Q 都接近上限
            Q = random_int(40000, 50000);
            // 预估总价值
            long long sum_possible = 0;
            for(int i=0; i<n; ++i) {
                int c = random_int(100, 1000);
                int p = random_int(100, 1000);
                items.push_back({p, c});
                if (c <= Q) sum_possible += p; // 粗略估计
            }
            // P 设置为可能达到的值
            P = random_int(10000, 40000); 
        }
        else if (file_id == 10) { // 极限数据
            n = 100;
            Q = 50000;
            P = 50000;
            // 物品也很大，让背包容量显得比较紧缺
            for(int i=0; i<n; ++i) {
                items.push_back({random_int(1000, 5000), random_int(1000, 5000)});
            }
        }
        
        // 写入输入文件
        fin << n << " " << P << " " << Q << "\n";
        for (auto& item : items) {
            fin << item.first << " " << item.second << "\n";
        }
        
        // 计算并写入输出文件
        int ans = Solver::solve_one_case(n, P, Q, items);
        fout << ans << "\n";
    }
    
    fin.close();
    fout.close();
}

int main() {
    // 优化 IO
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    // 生成 1 到 10 号测试点
    for (int i = 1; i <= 10; ++i) {
        generate_file(i);
    }
    
    cout << "All test cases generated successfully!" << endl;
    return 0;
}

🎯 数据策略详解

1. Test Case 1-2 (Subtask 1):

   • 特点：$p_i=1, c_i=1$。
   • 逻辑：这实际上变成了“能否选 $k$ 个物品，使得 $k \le Q$ 且 $k \ge P$”。
   • 边界：覆盖了 $P > n$（无解）、$Q < P$（买不起）以及正常有解的情况。

2. Test Case 3-4 (Subtask 2):

   • 特点：$c_i=1, Q=2$。
   • 逻辑：相当于只能买最多 2 个武器。算法应该去选强度最大的两个。
   • 构造：我特意计算了前两大强度之和 max_2，让 $P$ 在其附近波动，确保既有“刚好买到”、“轻松买到”，也有“差一点买不到”的情况。

3. Test Case 5-7 (常规测试):

   • Case 5：小规模随机，用于验证基础正确性。
   • Case 6：$Q$ 很大。这测试的是当预算充足时，算法是否能正确计算最小花费（虽然题目是求最小花费，但在 Q 很大时，任何组合都买得起，关键是看谁最便宜能凑够 P，或者是否需要全买）。
   • Case 7：$Q$ 很小，$P$ 很大。主要测试返回 -1 的逻辑。

4. Test Case 8-10 (压力与边界):

   • Case 9：数据数值较大，$P, Q$ 接近 40000。测试 DP 数组在高下标时的正确性。
   • Case 10：满数据。$N=100, P=50000, Q=50000$。物品的价值和花费也都很大（几千），使得背包装不了太多东西，强制 DP 进行复杂的取舍决策。

⏱️ 复杂度与耗时

• 生成耗时：Solver 的复杂度是 $O(N \cdot Q)$。
  • 最大单次计算量：$100 \times 50000 = 5 \times 10^6$。
  • Case 10 有 5 组数据，约 $2.5 \times 10^7$ 次运算，耗时约 0.1~0.2 秒。
  • 所有 10 个文件生成完毕，总耗时通常在 1秒以内。
• 安全性：完全在本地机器的可承受范围内，不会超时。

这是一份符合 NOIP C++14 竞赛标准的题解代码。

👨‍🏫 教练的解题分析

1. 核心思路：0/1 背包问题

这道题是非常典型的0/1 背包问题变形。

• 物品：武器。
• 重量（限制）：武器的花费 $c_i$（对应背包的容量）。
• 价值（目标）：武器的强度 $p_i$。
• 目标：在总重量不超过 $Q$ 的前提下，能否使总价值达到 $P$？如果能，求最小的“背包容量”是多少。

状态定义： 由于我们需要控制花费并最大化强度，且花费 $Q$ 的范围（$5 \times 10^4$）在可接受的数组大小内，我们定义： $dp[j]$ 表示总花费不超过 $j$ 时，能拼凑出的最大总强度。

2. 状态转移方程

对于每一个武器（花费 $c$，强度 $p$），我们有两种选择：选或不选。

• 注意：为了保证每个物品只选一次（0/1 背包特性），在使用一维数组优化时，内层循环必须**从大到小（$Q \to c$）**遍历。

3. 答案求解

计算完所有物品后，$dp[j]$ 存储了花费为 $j$ 时的最大强度。我们只需从 $0$ 到 $Q$ 遍历 $j$，找到第一个满足 $dp[j] \ge P$ 的 $j$，即为最小花费。如果遍历完都没有满足条件的，输出 -1。

💻 标准题解代码 (C++14)

/**
 * P11377 [GESP202412 七级] 武器购买
 * 知识点：动态规划 (DP)、0/1 背包
 * 
 * 复杂度分析：
 * 时间复杂度：O(t * n * Q)。代入数据约为 10 * 100 * 50000 = 5*10^7 次运算。
 *            C++ 1秒通常能处理 10^8 次运算，所以该算法是安全的。
 * 空间复杂度：O(Q)。使用一维滚动数组优化，仅需约 50000 个 int 的空间。
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // 用于 memset

using namespace std;

// 最大花费限制 Q 为 50000，开稍微大一点防止越界
const int MAXQ = 50005;

// dp[j] 表示：在总花费不超过 j 的情况下，能获得的最大总强度。
// 这里的空间优化技巧叫“滚动数组”，将二维 dp[i][j] 压缩为一维 dp[j]。
int dp[MAXQ];

void solve() {
    int n, P, Q;
    // 使用 cin 读取，建议配合 main 中的 sync_with_stdio(false) 加速
    cin >> n >> P >> Q;

    // 【易错点1】多组数据 (t 组) 必须每次清空 DP 数组
    // 0 表示花费为 j 时初始强度为 0
    memset(dp, 0, sizeof(dp));

    // 逐个处理物品
    for (int i = 0; i < n; ++i) {
        int p_val, c_cost;
        cin >> p_val >> c_cost;

        // 【关键点】0/1 背包的一维遍历顺序必须是“从大到小”
        // 也就是从背包容量上限 Q 遍历到当前物品花费 c_cost
        // 如果从小到大遍历，意味着同一个物品可能被多次累加（变成了完全背包）
        for (int j = Q; j >= c_cost; --j) {
            dp[j] = max(dp[j], dp[j - c_cost] + p_val);
        }
    }

    // 寻找答案：找到满足总强度 >= P 的最小花费
    int ans = -1;
    // 从小到大枚举花费限制
    for (int j = 0; j <= Q; ++j) {
        // dp[j] 代表花费不超过 j 能达到的最大强度
        // 如果这个最大强度已经达标，那当前的 j 就是最小成本
        if (dp[j] >= P) {
            ans = j;
            break; // 找到最小的就可以退出了
        }
    }

    cout << ans << endl;
}

int main() {
    // 【优化建议】关闭同步流，提高输入输出效率
    // 在数据量较大（如本题可能的 10*100 行输入）时非常有用
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    if (cin >> t) {
        while (t--) {
            solve();
        }
    }
    return 0;
}

🔍 代码细节与易错点注释

1. 数组大小与类型：

   • 题目中 $P, Q \le 50000$，最大总强度约为 $100 \times 50000 = 5 \times 10^6$，int 类型（最大 $2 \times 10^9$）完全足够，不需要 long long。
   • 数组大小开到 50005 即可。

2. 初始化 memset：

   • memset(dp, 0, sizeof(dp)) 是必须的。因为 DP 的本质是利用之前的状态推导现在的状态，上一组测试数据的残留数据会严重干扰计算。

3. 内层循环方向：

   • for (int j = Q; j >= c_cost; --j)：一定要逆序。
   • 原理：计算 dp[j] 时需要用到 dp[j - c_cost]。如果是顺序遍历，dp[j - c_cost] 已经是“放入了当前物品”后的状态，再次利用它会导致当前物品被重复放入。逆序遍历则保证 dp[j - c_cost] 还是“上一轮（没放当前物品）”的状态。

4. 答案判定：

   • dp[j] 的定义虽然是“花费不超过 j”，但在 0/1 背包的转移过程中，它自然通过 max 保留了该容量下的最优解。从小到大扫描 j，第一个满足 dp[j] >= P 的 j 即为最优解。

⏱ 时间复杂度优化思考

虽然本题 $O(T \cdot n \cdot Q)$ 已经可以通过，但在更极端的情况下（例如 $Q$ 很大但 $n$ 很小，或者实际总花费远小于 $Q$），可以做微小优化：

• 优化思路：记录当前所有物品花费的总和 sum_c。内层循环的上界可以是 min(Q, sum_c)。
  • 解释：如果你手上只有总价为 100 块的物品，去计算容量为 50000 的背包状态是没必要的，超过 100 的部分状态值肯定和 100 一样。
  • 代码体现：

    int current_max_cost = 0;
    for(int i=0; i<n; ++i) {
        // ... 读入 p, c
        current_max_cost += c;
        int bound = min(Q, current_max_cost); // 动态上界
        for(int j = bound; j >= c; --j) { ... }
    }
    

  • 本题情况：由于 $n$ 较大且物品花费可能较均匀，这个优化在本题收益不明显，标准写法最稳妥。

你好！很高兴继续以教练的身份带你攻克这道题。这是一道非常经典的**背包 DP（Knapsack Problem）**变种题目。

我们不要急着写代码，先拿出草稿纸，像在集训队上课一样，把题目拆解开来。

一、 核心关键词与题意解码

在读题时，请圈出以下几个关键点，它们决定了 DP 的方向：

1. “$n$ 个武器，每个有强度 $p_i$ 和花费 $c_i$”
   • 隐含意义：物品有“价值”和“体积”两个属性，这是背包问题的典型特征。
2. “总花费不超过 $Q$”
   • 隐含意义：这是一个硬性的上限。在背包模型中，通常把有上限的那个属性作为背包的容量（Capacity）。这里 $Q$ 就是背包容量，花费 $c_i$ 就是物品的体积（重量）。
3. “总强度不小于 $P$”
   • 隐含意义：这是我们需要达到的目标。在背包模型中，强度 $p_i$ 对应物品的价值（Value）。
4. “最少花费”
   • 隐含意义：我们需要在满足“容量 $\le Q$”和“价值 $\ge P$”的所有方案中，找到容量（花费）最小的那个。

二、 预备知识点

解决这道题，你需要掌握：

1. 0/1 背包问题：最基础的模型，每个物品只能选 1 次或 0 次。
2. DP 状态定义的转化：如何根据题目限制（$P, Q$ 的范围）选择是将“花费”作为数组下标，还是将“强度”作为数组下标。
3. 一维数组优化（滚动数组）：节省空间，并简化代码。

三、 启发式教学：草稿纸上的推理演练

假设我们在白板前，我会这样引导你思考：

1. 尝试定义状态

我们有两个选择来定义 $dp$ 数组：

• 方案 A：$dp[i]$ 表示凑出强度为 $i$ 时所需的最小花费。
  • 范围分析：最大强度可能是 $N \times \max(p_i) \approx 100 \times 50000 = 5 \times 10^6$。这个数组有点太大了，可能会超时/超内存。虽然可以截断在 $P$，但处理起来稍微麻烦点。
• 方案 B：$dp[j]$ 表示花费为 $j$ 时能获得的最大强度。
  • 范围分析：最大花费限制是 $Q = 50000$。这个数组大小完全可以接受！
  • 决策：采用方案 B。这是一个标准的“容量为 $Q$ 的 0/1 背包问题”。

2. 状态转移方程推导

• 定义：$dp[j]$ 表示预算（花费）恰好为 $j$ 时，我们能买到的最大武器总强度。
• 初始化：
  • $dp[0] = 0$（花 0 元，强度为 0）。
  • $dp[1 \dots Q] = -1$ 或一个小负数（表示初始状态不可达，或者初始化为 0 也可以，因为强度是非负的，初始化 0 表示没买东西强度就是 0）。为了严谨，初始化为 0 即可。
• 转移：对于第 $i$ 个武器（强度 $p$, 花费 $c$）：
  • 我们要决定“买”还是“不买”。
  • 如果要买，花费 $j$ 必须 $\ge c$。
  • 方程：$dp[j] = \max(dp[j], \quad dp[j - c] + p)$
  • 注意：使用一维数组时，内层循环 $j$ 需要从大到小遍历（从 $Q$ 到 $c$），这是 0/1 背包的铁律，为了防止一个物品被买多次。

3. 寻找答案

• 我们算出了 $dp[0], dp[1], \dots, dp[Q]$。
• 现在题目要求：总强度不小于 $P$ 的最少花费。
• 操作：从小到大枚举花费 $j$（从 $0$ 到 $Q$）。
  • 检查 $dp[j]$ 是否 $\ge P$。
  • 第一个满足条件的 $j$ 就是答案。
• 如果遍历完 $0 \dots Q$ 都没有满足条件的，说明在这个预算 $Q$ 下买不到强度 $P$ 的组合，输出 -1。

4. 复杂度分析

• 时间复杂度：
  • 外层循环枚举物品 $n$ 次。
  • 内层循环枚举花费 $Q$ 次。
  • 总计：$O(T \times n \times Q)$。
  • 代入数据：$10 \times 100 \times 50000 = 5 \times 10^7$。计算机一秒大概能跑 $10^8$ 次运算，这个复杂度是安全的，可以通过。
• 空间复杂度：
  • 一维数组 $dp[50005]$，非常小，完全没问题。

四、 总结与读题技巧

1. 关键词“最少花费”配上“花费限制 $Q$”：
   • 这通常暗示我们将“花费”作为 DP 的下标（状态），去计算对应的“最大收益”。然后通过扫描 DP 数组来找到满足收益条件的最小下标。
2. 数据范围敏感度：
   • 看到 $n=100$，而 $P, Q$ 较大（50000），基本确定是背包类 DP，且复杂度包含 $O(nQ)$ 或 $O(nP)$。
3. 多组数据：
   • 千万别忘了在每组数据开始前清空（重置）$dp$ 数组！这是最容易犯的错误。

现在，请你试着在草稿纸上写出核心的循环结构，然后开始编码吧！