题解题解，这是题解

A.新生宿舍分配

题意分析

学校有 $n$ 名新生，最开始大家互不认识。给出 $m$ 组认识关系，如果 $a$ 认识 $b$，$b$ 认识 $c$ ，那么可以推出 $a$ 也认识 $c$，这说明 认识关系具有传递性。

因此所有互相认识的人会形成一个 认识群体（连通块）。

宿舍安排规则是同一个认识群体不能被拆开到不同群体的宿舍中，而一个群体可以占多间宿舍，每间宿舍最多 $4$ 人，宿舍可以不住满

要求最少需要多少间宿舍。

---

核心思路

问题可以转化为两步：

第一步：找出所有认识群体

由于认识关系具有 传递性，本质就是求图中的 连通块。这种问题最经典的做法就是使用 并查集。

初始时每个人是一个集合，去遍历每个认识关系 $(a,b)$，将 $a$ 和 $b$ 合并

最后每个集合就是一个 认识群体。

---

第二步：计算每个群体需要多少宿舍

假设某个群体人数为 k。

每间宿舍最多住 4人，因此需要 $⌈k/4⌉$ ，代码中可以写成 $(k + 3) / 4$。最后把所有群体的宿舍数 累加即可。

代码如下

    #include<bits/stdc++.h>
    using namespace std;
    const int N = 2e5 + 7;
    int f[N]{};

    int find(int x){//找每个节点的根节点
        if(f[x] == x) return x;
        return f[x] = find(f[x]);
    }

    void join(int x,int y){//连接x与y
        int fx = find(x);
        int fy = find(y);
        f[fx] = fy; 
    }

    void init(){//初始化
        for(int i = 0; i < N; ++i) f[i] = i;
    }

    int main(){
        int n,m;
        cin >> n >> m;
        init();
        for(int i = 0; i < m; ++i) {
            int a,b;
            cin >> a >> b;
            join(a,b);
        }

        unordered_map<int,int> mp;
        for(int i = 1; i <= n; ++i) {
            mp[find(i)]++;
        }

        int ans = 0;
        for(auto[a,b] : mp){
            ans += (b + 3) / 4;
        }

        cout << ans << endl;

        return 0;
    }

B.教室温度监控

题意分析

学校有 $n$ 间教室，第 $i$ 间教室初始温度为 $a_i$​。

接下来会进行 $m$ 次操作，每次操作$(l,r,v)$，表示第 $l$ 到 $r$ 间教室，温度 全部增加 v

所有操作结束后如果某间教室温度 严格大于环境温度 X，则该教室为 过热教室。

需要求过热教室数量，最长连续过热教室段长度。

数据范围 ：$n,m≤2×10^5$

如果每次操作都暴力修改区间时间复杂度是 $O(nm)$，显然会 超时。

因此需要使用 差分数组优化区间修改。

---

核心思路

一、差分数组优化区间加法

对于操作$(l,r,v)$

我们使用 差分数组。 定义：dif[i]=a[i]−a[i−1]

那么区间加 v 只需要：

dif[l] += v;  
dif[r+1] -= v;

最后通过前缀和还原：

dif[i] += dif[i-1];

此时： a[i] + dif[i]

就是 最终温度。

这样所有操作复杂度就变为$O(n+m)$

代码如下

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    signed main(){
        int n,m,x;
        cin >> n >> m >> x; 

        vector<int> a(n+1),dif(n+2);
        for(int i = 1; i <= n; ++i) {
            cin >> a[i];
        }

        while(m--){
            int l,r,y;
            cin >> l >> r >> y;
            dif[l] += y;
            dif[r+1] -= y;
        }

        int ans = 0;//有多少温度大于X的教室
        int cnt = 0,mx = 0;//最长连续温度大于X的教室
        for(int i = 1; i <= n; ++i) {
            dif[i] += dif[i-1];
            int t = a[i] + dif[i];
            if(t > x){
                ans++;
                cnt++;
            }else{
                cnt = 0;
            }
            mx = max(mx,cnt); 
        }

        cout << ans << " " << mx;

        return 0;
    }

C.小希想要的完全平方数

这道题的目标是让数组所有数的乘积变成完全平方数，求需要乘的最小值。

一个常用的思路是：完全平方数的质因子分解中，每个质因子的指数都是偶数。因此，我们只需要统计数组中所有数乘积的质因子，找出指数为奇数的因子，它们的乘积就是答案。

具体做法如下：

1. 分解质因数：将数组中每个数分解为质因数的乘积。例如，21 = 3 × 7。

2. 统计奇数次因子：记录每个质因子出现的总次数，只保留出现次数为奇数的质因子。

3. 整合结果：将所有出现奇数次的质因子乘起来，得到的最小值就是要添加的数。

这样既保证了乘积为完全平方数，又使添加的数最小。

（我的代码是用了素数筛，因为最小的不可再分的因子肯定是素数，不过不用素数筛也可以过，直接分解因式就好）

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
vector<bool> is_primes(N+1,true);
vector<int> primes;
void find_primes(){
     int n = N;
    for(int i=2;i<=n;i++)
    {
        if(is_primes[i])
        primes.push_back(i);
        for(int j=0;j<is_primes.size()&&i*primes[j]<=n;++j)
        {
            is_primes[i*primes[j]]=false;
            if(i%primes[j]==0)
            break;
        }
    }
}
map<int,int> mp;
void quyu(int x){
    map<int,int> mp1;
    int i=0;
    while(x > 1){
        if(x % primes[i] == 0){
            mp1[primes[i]]++;
            x /= primes[i];
            continue;
        }
        i++;
    }
    for(auto [a,b] : mp1){
        if(b % 2 == 1){
            mp[a]++;
        }
    }
}
int main(){
    find_primes();
    int n;
    cin >> n;
    vector<int> arr(n);
    for(int i=0;i<n;i++){
        cin >> arr[i];
        quyu(arr[i]);
    }
    int ans = 0;
    for(auto [a,b] : mp){
        if(b % 2 == 1)
        ans += a;
    }
    cout << ans << endl;
    return 0;
}

D.奇偶迷宫

题意分析

给定一个 n×m 的迷宫 $.$表示空地，可以走， # 表示墙壁，不可走

小红从起点 $(x1​,y1​)$ 出发，要到达终点 $(x2​,y2​)$。

移动规则由 当前位置的奇偶性决定：

1. 当 (x+y) 为偶数

只能 四方向移动 ：上下左右

即只能从 $(0,0)$ 移动到 $(-1,0),(1,0),(0,-1),(0,1)$。

---

2. 当 (x+y) 为奇数

可以 八方向移动 ：上下左右以及四个对角线

即可以从$(0,0)$移动到$(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(-1,1),(1,-1),(1,1)$

题目要求判断是否能到达终点，如果可以，输出 最少步数。

---

核心思路

这是一个典型的 最短路问题：每次移动代价 = 1，图是 无权图。

因此最适合使用：BFS（广度优先搜索）

BFS天然保证 第一次到达就是最短路。

---

BFS状态设计

我们需要记录 $vis[x][y]$ 表示到达 $(x,y)$ 的最短步数

初始化 $vis[x1][y1] = 0$

队列存储 $(x,y)$

每次取出当前点，根据 $(x+y)$的奇偶性 决定 4方向还是8方向扩展新的点

---

合法移动条件

新位置 $(nx,ny)$ 必须满足

1.在迷宫内部 $1 ≤ nx ≤ n ，1 ≤ ny ≤ m$

2.不是墙 $grid[nx][ny] !=$'#'

3.没访问过 $vis[nx][ny] == -1$

---

复杂度分析

网格大小 $n×m≤10^6$ 因为每个点最多访问一次，

所以时间复杂度 $O(nm)$

空间复杂度 $O(nm)$

---

代码如下

    #include<bits/stdc++.h>
    using namespace std;
    #define pll pair<int,int>
    int ddx[] = {-1,1,0,0,1,1,-1,-1};
    int ddy[] = {0,0,1,-1,1,-1,1,-1};

    int main(){
        int n,m,x1,y1,x2,y2;
        cin >> n >> m >> x1 >> y1 >> x2 >> y2;
        vector<vector<char>> v(n+1,vector<char>(m+1));
        vector<vector<int>> vis(n+1,vector<int>(m+1,-1));

        for(int i = 1; i <= n; ++i) {
            for(int j = 1; j <= m; ++j) {
                cin >> v[i][j];
            }
        }

        if(x1 == x2 && y1 == y2){
            cout << "YES" << endl;
            cout << 0 << endl;
            return ;
        }

        queue<pll> q;
        q.push({x1,y1});
        vis[x1][y1] = 0;
        while(!q.empty()) {
            auto [x,y] = q.front();
            q.pop();
            if((x + y) & 1){
                for(int i = 0; i < 8; ++i) {
                    int dx = ddx[i] + x;
                    int dy = ddy[i] + y;
                    if(dx <= 0 || dy <= 0 || dx > n || dy > m || vis[dx][dy] != -1 || v[dx][dy] == '#') continue;
                    vis[dx][dy] = vis[x][y] + 1;
                    q.push({dx,dy});
                }
            }else{
                for(int i = 0; i < 4; ++i){
                    int dx = ddx[i] + x;
                    int dy = ddy[i] + y;
                    if(dx <= 0 || dy <= 0 || dx > n || dy > m || vis[dx][dy] != -1 || v[dx][dy] == '#') continue;
                    vis[dx][dy] = vis[x][y] + 1;
                    q.push({dx,dy});
                }
            }

        }

        if(vis[x2][y2] > 0){
            cout << "YES" << endl;
            cout << vis[x2][y2] << endl;
        }else{
            cout << "NO" << endl;
        }

        return 0;
    }

E.密文与苹果

题意已经很清楚了，每一段密文中都包含单词 "apple"。我们只需要找出密钥 k，即字母移动的距离。

有两种可行的思路：

1. 枚举密文中每一个长度为 5 的连续子串，找到某个子串，使其与 "apple" 对应字符的差值均相同，该差值即为密钥 k。

2. 枚举密钥 k（范围为 0 到 25），当存在某个 k 使得解密后的字符串中出现 "apple" 时，该 k 即为所求。

最后注意处理循环移位，确保字母始终在 'a' 到 'z' 之间。

    #include<bits/stdc++.h>
    using namespace std;
    char jiafa(char c,int x){
        return 'a' + (c - 'a' + 26 + x) % 26;
    }
    int jianfa(char a,char b){
        return (a - b + 26) % 26;
    }
    void solve(int n,string s){
        // int n;
        // cin >> n;
        // string s;
        // cin >> s;
        string s1 = "apple";
        int key = -1;
        for(int i=0;i<n-4;i++){
            bool ok = true;
            key = jianfa(s1[0],s[i]);
            // cout << key << endl;
            for(int j=1;j<5;j++){
                if(jianfa(s1[j],s[i+j]) != key){
                    ok = false;
                    key = -1;
                    break;
                }
            }
            if(ok) {
                break;
            }
        }
        string ans = "";
        for(int i=0;i<n;i++){ 
            ans += jiafa(s[i],key);
        }
        cout << ans << endl;
    }
    char a[] = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
    void solve1(int n,string s){
        // int n;
        // cin >> n;
        // string s;
        // cin >> s;
        vector<int> res;
        for(int k = 0; k < 26; ++k) {
            string ss;
            for(int i = 0; i < n; ++i){
                ss += a[(k + s[i] - 'a') % 26];
            }
            for(int i = 0 ;i < n - 4; ++i) {
                string f = ss.substr(i,5);
                if(f == "apple"){
                    res.push_back(k);
                    break;
                }
            }
        }

        if(res.size() > 1){
            cout << "NO";
            return ;
        }
        cout << res[0] << endl;
        string ss;              
        for(int i = 0; i < n; ++i){
            ss += (a[(res[0] + s[i] - 'a') % 26]);
        }
        cout << ss << endl;
    }
    int main(){
        int t=1;
        while(t--){
            int n;
            cin >> n;
            string s;
            cin >> s;
            //法一
            solve(n,s);
            //法二
            solve1(n,s);
        }
    }

F.害羞的人

这是一道思维题，想通一个关键点就能轻松解决。

考虑一个简单情况：

当前：pq

一秒后：qp

根据题意，是两个人转身交换了位置。但我们可以换一个思路：把他们理解为互相穿过对方继续前进。因为转身和向前走都需要一秒，两种理解方式下，每个人到达对岸的时间是完全相同的。

这样一来，问题就简化为：找到所有人中，走到自己原本朝向的对岸所需的最长时间。

向左走的人（p），需要的时间等于当前位置

向右走的人（q），需要的时间等于到右端的距离

遍历一遍，取最大值即可。

    #include<bits/stdc++.h>
    using namespace std;
    int main(){
        int n;
        cin >> n;
        string s;
        cin >> s;
        int ans = 0;
        for(int i=0;i<n;i++){
            int t;
            if(s[i] == 'q') t = i+1;
            else t = n - i;
            ans = max(ans,t);
        }
        cout << ans << endl;
        return 0;
    }

G.糖果游戏

这是一道 Nim 游戏的博弈题。先给出结论：若所有数的异或和为 0，则先手必败；否则先手必胜。

---

概念定义

• 平衡态：数列中所有数的异或和为 0。

• 非平衡态：数列中所有数的异或和不为 0。

显然，全 0 数列的异或和为 0，属于平衡态，且此时已无棋可走，为必败态。

---

证明过程

我们证明以下两点：

1. 从非平衡态出发，总存在一步操作，使其变为平衡态。

2. 从平衡态出发，无论怎么操作，结果一定是非平衡态。

1. 非平衡态 → 平衡态

设当前数列异或和为 $S \neq 0$。取 $S$ 的二进制表示中最高位的 1（设为第 $k$ 位），则至少有一堆石子 $a_i$ 在第 $k$ 位上也為 1。

令 $a_i' = a_i \oplus S$，由于第 $k$ 位从 1 变为 0，所以 $a_i' < a_i$。从第 $i$ 堆中取出 $a_i - a_i'$ 个石子，此时新数列的异或和为：

$$(a_i \oplus S) \oplus \bigoplus_{j \neq i} a_j = (a_i \oplus S) \oplus (S \oplus a_i) = 0$$

成功从非平衡态变为平衡态。

---

2. 平衡态 → 非平衡态

设当前异或和为 0，即：

$$a_1 \oplus a_2 \oplus \dots \oplus a_n = 0$$

假设从第 $i$ 堆中取出石子后，该堆变为 $a_i'$（$a_i' < a_i$），则新异或和为：

$$a_i' \oplus \bigoplus_{j \neq i} a_j = a_i' \oplus (0 \oplus a_i) = a_i' \oplus a_i$$

由于 $a_i' \neq a_i$，所以 $a_i' \oplus a_i \neq 0$，即新状态为非平衡态。

AC代码

#include<bits/stdc++.h>
using namespace std;
void solve(){
    int n;
    cin >> n;
    vector<int> arr(n);
    int sum = 0;
    for(int i=0;i<n;i++){
        cin >> arr[i];
        sum = sum ^ arr[i];
    }
    if(sum  == 0){
        cout << "NO" << endl;
    }
    else{
        cout << "YES" << endl;
    }
}
int main(){
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

H.鱼鱼越龙门

题意分析

有 $n$ 座龙门，第 $i$ 座龙门高度为 $a_i$​。鱼鱼需要 按顺序跳过所有龙门。

第一次跳跃时可以选择一个 初始跳跃高度 x。

跳过龙门后的高度变化规则为如果 $x=a_i$​，那么下一次跳跃高度$x=x−k$。如果$x>ai$​ 那么下一次跳跃高度 $x=x−1$。 如果某一步 $x<ai$​则无法跳过该龙门。

---

目标：

求 最小初始跳跃高度 x，使得鱼鱼能够跳过所有龙门。

---

核心思路

关键观察：

如果某个初始高度 $x$ 可以成功跳过所有龙门，那么更大的 $x$ 也一定可以

因为更高的初始高度只会 更容易跳过去。因此答案具有 单调性。

这种结构非常适合二分答案

---

二分框架

我们二分 初始跳跃高度 x 区间 [0 , 1e18]

每次检查 $mid$ 是否可以跳完所有龙门，如果可以则右移左端点继续往更小的答案找，否则左移右端点增大 $x$

---

check函数设计

check(x) 表示初始跳跃高度为 x 时 能否跳过所有龙门，我们模拟整个过程：

对于每座龙门，如果$x < a_i$就说明跳不过去 $return$ $false$

否则如果 $x == a_i$ $x -= k$否则 $x--$

最后如果全部跳完 $return$ $true$

代码如下

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 7;
vector<int> a(N);
int n,k;

bool check(int x){
    for(int i = 1; i <= n; ++i){
        if(a[i] > x) return false;
        if(a[i] == x) x-=k;
        else x--;
    }
    return true;
}

signed main(){
    cin >> n >> k;
    for(int i = 1; i <= n; ++i) {
        cin >> a[i];
    }

    int ans = 0;
    int l = 0, r = 1e18;

    while(l <= r){
        int mid = l + (r - l) / 2;
        if(check(mid)){
            ans = mid;
            r = mid - 1;
        }else{ 
            l = mid + 1;
        }
    }

    cout << ans << endl;

    return 0;
}

I.小赵选礼物

题目描述

给定一个由 $n$ 个正整数组成的数组 $a$ 。请你计算最长上升子序列的长度。对于一条子序列，要求保留原数组中的相对顺序，并满足子序列中的元素依次大于前一个元素。

解题思路

这是一个经典的动态规划问题，可以使用贪心算法结合二分查找进行优化。我们将维护一个数组 $d$ ，其中 $d[i]$ 表示长度为 $i+1$ 的所有上升子序列中，结尾元素的最小值。显然，数组 $d$ 是单调上升的。

我们遍历输入的数组 $a$ 中的每个元素 $x$ ：

1.如果 $x$ 大于 $d$ 数组的最后一个元素，说明 $x$ 可以接在当前最长的上升子序列后面，形成一个更长的新序列，即将 $x$ 添加到 $d$ 数组的末尾。

2.如果 $x$ 小于或等于 $d$ 数组的最后一个元素，我们就在 $d$ 数组中查找第一个严格大于 $x$ 的元素，并用 $x$ 替换它。这样做是因为，我们找到了一个长度与被替换元素所在位置对应的子序列，但其结尾更小（为 $x$ ）。这个更小的结尾为后续元素提供了更多成为上升子序列一部分的可能性，这里体现出了贪心的思想。

由于数组 $d$ 始终单调递增，上述查找过程可以使用二分查找来完成。遍历完整个输入数组 $a$ 后，$d$ 数组的长度就是原数组最长上升子序列的长度。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    vector<int> d;
    for (int i = 1; i <= n;i++){
        int x;
        cin >> x;
        auto it = upper_bound(d.begin(), d.end(), x);
        if(it==d.end())
            d.push_back(x);
        else
            *it = x;
    }
    cout << d.size();
    return 0;
}

J.小袁的序列函数

解题思路

吸收律：$a$ | ($a$ & $b$)= $a$ ；

& 相当于取交集，| 相当于取并集，

根据吸收律可知：

$f(a_1)$ = ($a_1$ & $a_1$) | ($a_1$ & $a_2$) | ($a_1$ & $a_3$) |...| ($a_1$ & $a_n$)

= $a_1$ | ($a_1$ & $a_2$) | ($a_1$ & $a_3$) |...| ($a_1$ & $a_n$)

= $a_1$

故原式：$f(a_1)$ ^ $f(a_2)$ ^ $f(a_3)$ ^ ... ^ $f(a_n)$ = $a_1$ ^ $a_2$ ^ $a_3$ ^...^ $a_n$ ，即答案为所有数的异或和。

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n;
        cin >> n;
        vector<int> a(n);
        for (auto &x : a)
        {
            cin >> x;
        }
        int ans = a[0];
        for (int i = 1; i < n; i++)
        {
            ans ^= a[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

K.小袁的世界(Easy)

前备知识

二位费用背包，01背包，完全背包

题目描述

小袁有护甲初始耐久度 $X$ 和武器初始耐久度 $Y$，共有 $n$ 种怪物。击杀第 i 种怪物会消耗护甲 $a_i$​ 点耐久、武器 $b_i$ 点耐久，并获得价值 vi​。每种怪物有两种出现方式：

• $s_i = 1$：只会出现一次（01 背包）

• $s_i ​= 2$：可以无限次出现（完全背包）

要求在整个过程中不能损失任何一件装备，即击杀怪物时，护甲和武器的当前耐久度必须分别不少于 $a_i$ 和 $b_i$​，且击杀后剩余耐久度可以为 $0$（装备进入休眠，但本次击杀已完成）。求能获得的最大总价值。

解题思路

这是一个二维代价、二维容量的背包问题，每种怪物要么只能选一次，要么可以选无限次。

动态规划定义:

设 $dp[j][k]$ 表示护甲消耗不超过 $j$ 、武器消耗不超过 $k$ 时能获得的最大价值。初始 $dp[0][0]=0$，其余为 $0$ 。

状态转移:

对于第 i 种怪物（消耗 $a$ , $b$ ，价值 $v$ ，类型 $s$ ）：

• **若 $s=1$（01 背包）**必须从大到小枚举护甲和武器的消耗，确保每个怪物只被考虑一次：$dp[j][k]=max(dp[j][k],dp[j−a][k−b]+v)$ $(j≥a,k≥b)$使用逆序循环 $j$ 和 $k$ 。

• **若 $s=2$（完全背包）**需要从小到大枚举，允许同一怪物被多次选取：$dp[j][k]=max(dp[j][k],dp[j−a][k−b]+v)$ $(j≥a,k≥b)$使用正序循环 $j$ 和 $k$ 。

最终答案：

遍历所有怪物后，$dp[X][Y]$ 即为所求。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, X, Y;
    cin >> n >> X >> Y;
    vector<vector<int>> dp(X + 1, vector<int>(Y + 1, 0));
    for (int i = 1; i <= n; i++)
    {
        int a, b, v, s;
        cin >> a >> b >> v >> s;
        if (s == 1)
        {
            for (int j = X; j >= a; j--)
            {
                for (int k = Y; k >= b; k--)
                {
                    dp[j][k] = max(dp[j][k], dp[j - a][k - b] + v);
                }
            }
        }
        else
        {
            for (int j = a; j <= X; j++)
            {
                for (int k = b; k <= Y; k++)
                {
                    dp[j][k] = max(dp[j][k], dp[j - a][k - b] + v);
                }
            }
        }
    }
    cout << dp[X][Y];
}

L.小袁的世界(Hard)

前备知识

二位费用背包，多重背包，混合背包

题目描述

小袁有护甲初始耐久度 $X$ 和武器初始耐久度 $Y$，共有 $n$ 种怪物。击杀第 i 种怪物会消耗护甲 $a_i$ 点耐久、武器 $b_i$​ 点耐久，并获得价值 $v_i$ ​。每种怪物有一定的出现次数 $s_i$ ：

• 若 $s_i​=0$，表示可以无限次出现；

• 若 $s_i​=1$，表示只出现一次；

• 若 $si​≥2$，表示恰好出现 $s_i$​ 次。

在整个过程中不能损失任何一件装备，即每次击杀时，护甲和武器的当前耐久度必须分别不少于 $a_i$ 和 $b_i$ ​，且击杀后剩余耐久度可以为 $0$（装备进入休眠，但本次击杀已完成）。求能获得的最大总价值。

这是一个二维代价（护甲耐久、武器耐久）、二维容量的背包问题，且物品有三种数量类型：01背包（si​=1）、完全背包（si​=0）、多重背包（si​≥2）。

解题思路

动态规划定义：

设 $dp[j][k]$ 表示护甲消耗不超过 $j$ 、武器消耗不超过 $k$ 时能获得的最大价值。初始 $dp[0][0]=0$ ，其余为 $0$ 。

状态转移:

对于第 i 种怪物，消耗为 $(a_i​,b_i​)$，价值为 $v_i$​，数量为 $s_i$​：

1. **$s_i​=1$（01 背包）**从大到小枚举护甲和武器消耗，确保每个怪物只被考虑一次：$dp[j][k]=max(dp[j][k],dp[j−a_i​][k−b_i​]+v_i​)$ $(j≥a_i​,k≥b_i​$)使用逆序循环 $j$ 和 $k$ 。

2. **$s_i​=0$（完全背包）**从小到大枚举，允许同一怪物被多次选取：$dp[j][k]=max(dp[j][k],dp[j−a_i​][k−b_i​]+v_i​)$ $(j≥a_i​,k≥b_i​)$使用正序循环 $j$ 和 $k$ 。

3. **$s_i​≥2$（多重背包）**采用二进制优化，二进制优化的核心思想是将数量 $s_i$ 分解成若干个 $2$ 的幂次之和，使得这些幂次可以组合出 $0$ 到 $s$ 之间的任意整数。例如，$s=13$ 可以拆成 $1,2,4,6$（因为 $1+2+4=7$，剩余 $6$ ），这样用这些组可以表示 $0~13$ 的任何数。 具体拆分方法：

   • 从 $t=1$ 开始，每次取 $t$ 个原物品作为一组，然后 $s$ 减去 $t$，$t$ 翻倍，直到剩余 $s$ 小于 $t$ 。

   • 最后将剩余的 $s$ 作为一组（如果剩余不为 $0$ ）。

   这样拆分后，原来的 $s$ 个相同物品就变成了 $⌊log2​s⌋+1$ 组，每组视为一个新的物品，其代价为原代价乘以组内物品个数，价值也为原价值乘以个数。然后对这组新物品依次进行 01 背包处理。本题中每个怪物有护甲消耗 $a_i$ 、武器消耗 $b_i$ 、价值 $v_i$ 。对于拆分出的某一组，若该组包含 $t$ 个原怪物，则这组的消耗为：$护甲消耗=a×t,武器消耗=b×t,价值=v×t$.然后将这组作为一个物品，按照 01 背包的方式更新 DP 数组。由于是 01 背包，必须逆序枚举护甲和武器的消耗，以保证每组物品最多选一次。

最终答案:

遍历所有怪物后，$dp[X][Y]$ 即为所求。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int n, X, Y;
    cin >> n >> X >> Y;
    vector<vector<int>> dp(X + 1, vector<int>(Y + 1, 0)), g(X + 1, vector<int>(Y + 1, 0));
    for (int i = 1; i <= n; i++)
    {
        int a, b, v, s;
        cin >> a >> b >> v >> s;
        if (s == 1)
        {
            for (int j = X; j >= a; j--)
            {
                for (int k = Y; k >= b; k--)
                {
                    dp[j][k] = max(dp[j][k], dp[j - a][k - b] + v);
                }
            }
        }
        else if (s == 0)
        {
            for (int j = a; j <= X; j++)
            {
                for (int k = b; k <= Y; k++)
                {
                    dp[j][k] = max(dp[j][k], dp[j - a][k - b] + v);
                }
            }
        }
        else
        {
            int t = 1, cnt = 0;
            vector<int> x(s + 1), y(s + 1), z(s + 1);
            while (s >= t)
            {
                x[++cnt] = a * t;
                y[cnt] = b * t;
                z[cnt] = v * t;
                s -= t;
                t *= 2;
            }
            x[++cnt] = a * s;
            y[cnt] = b * s;
            z[cnt] = v * s;
            for (int j = 1; j <= cnt; j++)
            {
                for (int k = X; k >= x[j]; k--)
                {
                    for (int l = Y; l >= y[j]; l--)
                    {
                        dp[k][l] = max(dp[k][l], dp[k - x[j]][l - y[j]] + z[j]);
                    }
                }
            }
        }
    }
    cout << dp[X][Y];
}