官方题解 | 巅峰赛#39题解

Yuilice

2026-10-14 10:23:20

发布于：浙江

690阅读

0回复

0点赞

导语

久违的巅峰赛，这次巅峰赛是以Dp和状压作为压轴的，毕竟许多朋友的状压熟练度还有待提升 ~~(笑)~~ 。

以下为题解

题目编号	题目标题	难度
T1	Yuilice 的手工套装	入门
T2	Yuilice 的相册整理	普及-
T3	Yuilice 的分批冲印	普及/提高-
T4	Yuilice 的打印店	普及+/提高
T5	Yuilice 的小区接送	普及+/提高
T6	Yuilice 的共用设备	普及+/提高

Yuilice 的手工套装

题意简述

有 $a$ 张大卡纸和 $b$ 张小卡纸，每套手工套装需要一张大卡纸和一张小卡纸。可以把一张大卡纸剪成两张小卡纸，剪过的卡纸不能再当大卡纸使用。求最多能制作多少套。

样例 1 中输入为 $5,0$ 。剪开两张大卡纸后，还剩 $3$ 张大卡纸和 $4$ 张小卡纸，因此可以制作 $3$ 套。样例 2 中小卡纸已经足够，直接使用 $2$ 张大卡纸即可。

解题思路

解题方法

设剪开 $x$ 张大卡纸，其中 $0\le x\le a$ 。操作结束后：

大卡纸有 $a-x$ 张；
小卡纸有 $b+2x$ 张。

每套需要两种卡纸各一张，所以固定 $x$ 时最多制作

$\min(a-x,b+2x)$

套。枚举全部合法的 $x$ ，取最大值即可。

读入 $a,b$ ，答案初始为 $0$ 。
枚举 $x=0,1,\ldots,a$ 。
计算当前值 $\min(a-x,b+2x)$ ，更新答案。

任意一种制作方案都会剪开某个合法数量 $x$ 的大卡纸，因此一定会被程序枚举。固定 $x$ 后，套数不能超过剩余大卡纸数量，也不能超过小卡纸数量，所以最多是 $\min(a-x,b+2x)$ ；取出这么多张两种卡纸后可以逐套配对，说明这个上限能够达到。

程序枚举了所有可能的 $x$ ，并取其中最大值，所以得到的正是最优答案。

时间复杂度为 $O(a)$ ，额外空间复杂度为 $O(1)$ 。因为 $a,b\le10^6$ ，中间数量不超过 $3\times10^6$ ，使用 int 足够。

剪纸后要同时减少大卡纸、增加小卡纸。
可以一次都不剪， $x=0$ 必须被枚举。
不能直接输出 $\min(a,b)$ ，因为剪纸可能增加可制作套数。

部分分

测试点 1~10（无额外限制）：枚举裁剪数量即可获得满分。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int a, b;
    cin >> a >> b;
    int ans = 0;
    for (int x = 0; x <= a; x++) {
        // 剪开 x 张后，两种卡纸中较少的一种决定套数。
        int now = min(a - x, b + 2 * x);
        ans = max(ans, now);
    }
    cout << ans << '\n';
    return 0;
}

Yuilice 的相册整理

题意简述

有 $n$ 张照片，日期为 $a_1,a_2,\ldots,a_n$ 。如果 $a_i>a_{i+1}$ ，则位置 $i$ 有一处日期回退。可以不操作，也可以选择一段恰好包含 $k$ 张照片的连续区间反转一次，求最少回退数。

反转只改变顺序，不改变日期；日期相等不算回退。

解题思路

解题方法

先记原序列的回退总数为 $B$ ，考虑反转区间 $[l,r]$ ，其中 $r=l+k-1$ 。

区间内部的相邻关系会全部反向：原来严格上升的关系会变成回退，原来的回退会消失，相等关系仍然不计数。设区间内部严格上升数为 $U$ 、回退数为 $D$ ，内部部分反转后对答案的贡献就是 $U-D$ 。

区间外的关系都不变，只需要检查最多两条连接边：

如果 $l>1$ ，原来的 $(a_{l-1},a_l)$ 变成 $(a_{l-1},a_r)$ ；
如果 $r<n$ ，原来的 $(a_r,a_{r+1})$ 变成 $(a_l,a_{r+1})$ 。

这样，每个区间都能在 $O(1)$ 时间内算出答案。区间右移一格时，内部关系只删除最左边一对、加入最右边一对，因此 $U,D$ 可以滑动维护。

统计原序列的回退数 $B$ ，并令答案初始为 $B$ ，表示可以不操作。
统计第一个长度为 $k$ 的区间内部的上升数 $U$ 和回退数 $D$ 。
枚举区间左端点，用 $B+U-D$ 加上两侧连接的变化量得到当前答案。
窗口右移时删除离开窗口的相邻关系，加入新进入窗口的相邻关系。
输出所有方案中的最小值。

把原序列的相邻关系分为三类：反转区间内部、区间左侧连接、区间右侧连接。内部关系反转后方向全部交换，因此贡献从 $D$ 变成 $U$ ；两侧连接按反转后的端点重新计算；其他关系完全不变。三类关系覆盖了所有相邻位置且互不重复，所以公式准确计算了该区间的回退数。

滑动窗口每次只删除一条内部关系并加入一条新关系，故维护的 $U,D$ 始终正确。算法枚举了所有长度为 $k$ 的区间，同时保留了不操作方案，取最小值后就是全局最优解。

时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。比较关系必须使用严格不等号，日期相等时不计回退。

只处理两侧连接，忘记区间内部的方向会全部反转。
把相等关系算进上升或回退。
忘记不操作方案，或漏掉贴着首端、末端的区间。
这里统计的是相邻回退，不是任意两张照片组成的逆序对。

部分分

测试点 1~4（ $n\le2000$ ，20 分）：可以实际反转每个区间，再重新统计回退数。
测试点 5~20（无额外限制，80 分）：使用滑动窗口维护区间内部贡献，并处理两侧连接。

参考代码

#include <bits/stdc++.h>
using namespace std;
int a[200005];
int main() {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int base = 0;
    for (int i = 1; i < n; i++) base += (a[i] > a[i + 1]);
    int ans = base;
    if (k == 1) {
        cout << ans << '\n';
        return 0;
    }
    int up = 0, down = 0;
    for (int i = 1; i < k; i++) {
        up += (a[i] < a[i + 1]);
        down += (a[i] > a[i + 1]);
    }
    for (int l = 1; l + k - 1 <= n; l++) {
        int r = l + k - 1;
        int now = base + up - down;
        // 区间内部改变方向，两侧连接使用反转后的端点。
        if (l > 1) now += (a[l - 1] > a[r]) - (a[l - 1] > a[l]);
        if (r < n) now += (a[l] > a[r + 1]) - (a[r] > a[r + 1]);
        ans = min(ans, now);
        if (r < n) {
            up -= (a[l] < a[l + 1]);
            down -= (a[l] > a[l + 1]);
            up += (a[r] < a[r + 1]);
            down += (a[r] > a[r + 1]);
        }
    }
    cout << ans << '\n';
    return 0;
}

Yuilice 的分批冲印

题意简述

按顺序处理 $n$ 张照片。第 $i$ 张照片的打印时间为 $t_i$ ，准备参数为 $s_i$ 。要把照片分成至多 $k$ 个连续、非空批次。

一个批次的耗时是该批次所有 $t_i$ 的总和，加上其中最大的 $s_i$ 。目标是让所有批次中最大的耗时尽可能小。

解题思路

解题方法

二分答案。假设限制每个批次的耗时不能超过 $X$ ，从左到右尽可能多地把照片放入当前批次：

当前批次维护打印时间和 sum、准备参数最大值 mx。如果加入下一张照片后满足

$\text{sum}+t_i+\max(\text{mx},s_i)\le X,$

就继续加入；否则从这张照片开始新批次。

“尽可能长”必然合法，因为删去一个批次的前缀后，打印时间总和不会增加，准备参数最大值也不会增加。因此，贪心得到的批次数最少。

当 $X$ 增大时，原来可行的分批方案仍然可行，所以可行性具有单调性，可以二分最小的 $X$ 。

二分下界取 $\max_i(t_i+s_i)$ ，上界取 $\sum t_i+\max_i s_i$ 。
在 check(X) 中从左到右维护当前批次的 sum 和 mx。
如果单张照片都超过 $X$ ，直接判定失败。
超过上限时新开批次，并清空当前批次的统计量。
统计最少批次数是否不超过 $k$ ，据此继续二分。

对于固定的 $X$ ，设贪心算法第一批覆盖到位置 $r$ 。由于它取的是最长可行前缀，任何合法方案的第一批都不能超过 $r$ 。把贪心覆盖的前缀从任意合法方案中删去时，至多有一个批次被删去一部分前缀；剩余部分仍然合法，而且剩余批次数不会增加。

对剩余照片重复这个论证，得到贪心使用的批次数不超过任意合法方案，因此它得到的就是最少批次数。于是 check(X) 正确。又因为可行性随 $X$ 增大而单调，二分找到的最小可行值就是答案。

一次 check 为 $O(n)$ ，二分次数为 $O(\log U)$ ，其中 $U=\sum t_i+\max s_i$ ，总复杂度为 $O(n\log U)$ ，空间复杂度为 $O(n)$ 。答案和中间和必须使用 long long。

准备参数取批次最大值，不是把所有 $s_i$ 相加。
新开批次时要同时清空 sum 和 mx。
判断条件使用“加入后是否超过 $X$ ”，等于 $X$ 时仍然合法。
需要先检查单张照片的 $t_i+s_i$ 是否超过 $X$ 。

部分分

测试点 1~2（ $k=1$ 或 $k=n$ ，10 分）：直接计算整段或每张照片单独成批的答案。
测试点 3~6（ $n\le16$ ，20 分）：枚举相邻位置是否切分。
测试点 7~20（无额外限制，70 分）：二分答案，使用最长可行前缀贪心。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
int n, k;
long long t[N], s[N];

bool check(long long x) {
    int cnt = 1;
    long long sum = 0, mx = 0;
    for (int i = 1; i <= n; i++) {
        if (t[i] + s[i] > x) return false;
        if (sum + t[i] + max(mx, s[i]) > x) {
            cnt++;
            sum = 0;
            mx = 0;
        }
        sum += t[i];
        mx = max(mx, s[i]);
    }
    return cnt <= k;
}

int main() {
    scanf("%d%d", &n, &k);
    long long l = 0, r = 0, mx = 0;
    for (int i = 1; i <= n; i++) {
        scanf("%lld%lld", &t[i], &s[i]);
        l = max(l, t[i] + s[i]);
        r += t[i];
        mx = max(mx, s[i]);
    }
    r += mx;
    while (l < r) {
        long long mid = l + (r - l) / 2;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    printf("%lld\n", l);
    return 0;
}

Yuilice 的打印店

题意简述

有 $p$ 台打印机，共用一个先进先出等待队列。提交订单、取消等待订单、暂停打印机接单和恢复打印机接单都发生在给定时刻。

同一时刻必须按三步处理：先结算所有完成订单，再按输入顺序处理这一时刻的全部操作，最后按打印机编号从小到大统一接单。正在打印的订单不会因为暂停或取消而中断。

输出每个订单的完成时刻；被取消输出 $-1$ ；最终一直等待、没有开始打印输出 $-2$ 。

解题思路

解题方法

不能按时间单位逐秒模拟，因为时刻最多达到 $10^9$ ，订单完成时间还可能更大。系统状态只会在两类时刻发生变化：

下一条外部操作发生的时刻；
某台打印机完成当前订单的时刻。

每次跳到这两类时刻的最小值即可。维护每台打印机的状态、当前订单和完成时刻，维护每个订单的状态以及等待队列。

到达时刻 now 后严格执行：

把所有完成时刻等于 now 的订单标记为完成，并释放打印机；
按输入顺序执行 now 时刻的所有操作；
按打印机编号扫描空闲且允许接单的机器，从队首跳过已取消订单后派单。

最后一条外部操作结束后仍要继续处理打印完成事件。若没有外部操作、也没有正在打印的订单，队列中的订单就不可能再开始，答案保持为 $-2$ 。

读入全部操作，保存操作顺序。
用 state 区分等待、打印中、完成和取消。
每轮找到下一外部操作时刻与最早完成时刻的较小值。
依次完成结算、批量处理操作、按机器编号派单。
记录完成时刻、取消结果和最终等待结果。

相邻两个事件时刻之间没有新操作，也没有订单完成，所以跳过中间时间不会遗漏状态变化。每轮第一步结算所有完成订单，第二步按照原输入顺序处理全部操作，第三步按题目规定的打印机编号和队列顺序派单，因此这一轮得到的状态与真实过程完全一致。

由初始状态正确，按事件时刻归纳可知整个模拟正确。每个订单只会在完成时被记录一次；取消只会对仍在等待的订单生效。模拟结束时，仍等待的订单已经没有可接单的打印机，所以输出 $-2$ 正确。

设提交订单数为 $n$ 。事件时刻数量不超过 $q+n$ ，每轮最多扫描 $p$ 台打印机，因此时间复杂度为 $O(p(q+n))$ ，空间复杂度为 $O(p+q+n)$ 。完成时刻使用 long long。

同一时刻的多条操作之间不能派单。
暂停只影响接收新订单，不会打断正在打印的订单。
取消正在打印、已经完成或已经取消的订单都没有额外效果。
最后一条操作之后还要继续结算完成事件。
等待队列里的取消订单可以延迟到队首时跳过。

部分分

测试点 1~2（ $p=1$ ，只有提交操作，10 分）：维护单台打印机的结束时间。
测试点 3~6（只有提交操作，20 分）：模拟多台打印机和共享队列。
测试点 7~10（只有提交、取消操作，20 分）：增加等待订单取消和状态判断。
测试点 11~20（无额外限制，50 分）：完整处理完成、操作、派单的时序。

参考代码

#include <bits/stdc++.h>
using namespace std;

struct Event {
    long long t;
    int op, x;
};
struct Printer {
    long long speed, finish = 0;
    int job = 0;
    bool online = true;
};

int main() {
    int p, q;
    scanf("%d%d", &p, &q);
    vector<Printer> machine(p);
    for (int j = 0; j < p; j++) scanf("%lld", &machine[j].speed);
    vector<Event> events(q);
    for (int i = 0; i < q; i++) {
        scanf("%lld%d%d", &events[i].t, &events[i].op, &events[i].x);
    }
    vector<int> state(q + 1, 0), pages(q + 1, 0);
    // state: 0 等待，1 打印中，2 完成，3 取消。
    vector<long long> ans(q + 1, -2);
    queue<int> waiting;
    int pos = 0, jobs = 0;
    const long long INF = (1LL << 62);
    while (true) {
        long long now = pos < q ? events[pos].t : INF;
        for (int j = 0; j < p; j++) {
            if (machine[j].job) now = min(now, machine[j].finish);
        }
        if (now == INF) break;
        // 同一时刻：先结算全部完成事件。
        for (int j = 0; j < p; j++) {
            if (machine[j].job && machine[j].finish == now) {
                int id = machine[j].job;
                state[id] = 2;
                ans[id] = now;
                machine[j].job = 0;
            }
        }
        // 再处理该时刻全部操作，操作之间不接单。
        while (pos < q && events[pos].t == now) {
            int op = events[pos].op, x = events[pos].x;
            if (op == 1) {
                ++jobs;
                pages[jobs] = x;
                waiting.push(jobs);
            } else if (op == 2) {
                if (state[x] == 0) {
                    state[x] = 3;
                    ans[x] = -1;
                }
            } else if (op == 3) {
                machine[x - 1].online = false;
            } else {
                machine[x - 1].online = true;
            }
            pos++;
        }
        // 最后按打印机编号接单。
        for (int j = 0; j < p; j++) {
            if (!machine[j].online || machine[j].job) continue;
            while (!waiting.empty() && state[waiting.front()] == 3) waiting.pop();
            if (waiting.empty()) break;
            int id = waiting.front();
            waiting.pop();
            state[id] = 1;
            machine[j].job = id;
            machine[j].finish = now + machine[j].speed * pages[id];
        }
    }
    for (int id = 1; id <= jobs; id++) printf("%lld\n", ans[id]);
}

Yuilice 的小区接送

题意简述

给定一棵树，每个站点有端点服务费 $p_i$ ，每条道路有行驶费用 $w$ ，每条路线还要支付一次固定派车费 $C$ 。要把所有站点划分成互不相交的简单路径，单个站点也可以单独成路。

多站路径只收两个端点的服务费，内部站点不收费；单站路径只收该站点一次服务费。求总费用最小值。

解题思路

解题方法

在树上保留一部分道路。只要每个站点被保留的道路数不超过 $2$ ，保留下来的每个连通块就是一条合法路径；反过来，每种路径划分也对应这样一组保留道路。

设保留边集合为 $F$ ，则路径数量为 $n-|F|$ ，所有路径固定费用为 $(n-|F|)C$ 。每条保留边贡献道路费用 $w$ ，同时让两个连通块合并，减少一份派车费 $C$ 。端点和单站服务费统一写成“度数不超过 $1$ 的点付一次”：

$\text{总费用}=nC+\sum_{e\in F}(w_e-C)+\sum_{\deg(v)\le1}p_v.$

把树定根，定义 $dp[u][0]$ 表示父边不保留时， $u$ 子树的最小变形费用； $dp[u][1]$ 表示父边保留时的最小变形费用。

假设所有子边都不保留，基准为 $B$ 。保留连接儿子 $v$ 的边后，新增代价为

$d_v=dp[v][1]+w_{uv}-C-dp[v][0].$

父边不保留时， $u$ 最多选两条子边；父边保留时，最多再选一条子边。只需维护最小的两个 $d_v$ 。注意不能只选负增量：两条正增量也可能一起省下当前点的端点服务费。

迭代遍历树，记录每个点的父亲和遍历顺序。
按逆序处理节点，保证儿子状态已知。
计算所有子边不选的基准值，并维护最小的两个增量。
根据父边是否保留，枚举允许选取的子边数量，得到两个 DP 状态。
根节点没有父边，输出 $nC+dp[1][0]$ 。

费用公式逐项对应原题： $nC$ 是假设每个站点单独成路的固定费用，保留一条边会减少一份派车费并增加 $w$ ，度数不超过 $1$ 的点恰好是路径端点或单站点，因此最后一项正好表示服务费。

固定 $u$ 的父边状态后，各个儿子子树之间没有其他连接，子树贡献可以独立相加。 $u$ 的总度数最多为 $2$ ，所以父边不保留时最多选两条子边，父边保留时最多选一条子边。程序枚举这些全部可能，并在固定选择数量时取最小增量，因此两个状态都取得最优值。

由叶子向根归纳，根状态覆盖所有合法路径划分，最终答案正确。

每条边只被处理常数次，时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。费用和增量使用 long long；迭代遍历可以处理最长链。

单站路径的服务费只收一次。
一个点最多连接两条保留边，不能让它成为三条路径的交汇点。
不能只保留负增量边。
所有站点都必须被覆盖，不能只求一条最便宜路径。

部分分

测试点 1~2（特殊性质 S，10 分）：树是星形，最多保留两条边，枚举选择数量即可。
测试点 3~6（ $n\le18$ ，20 分）：枚举边子集，检查每点度数并直接计算费用。
测试点 7~20（无额外限制，70 分）：使用父边状态的树形 DP。

参考代码

#include <bits/stdc++.h>
using namespace std;
struct Edge { int v; long long w; };
int main() {
    int n;
    long long c;
    scanf("%d%lld", &n, &c);
    vector<long long> fee(n);
    for (int i = 0; i < n; i++) scanf("%lld", &fee[i]);
    vector<vector<Edge>> g(n);
    for (int i = 1; i < n; i++) {
        int u, v;
        long long w;
        scanf("%d%d%lld", &u, &v, &w);
        --u; --v;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }
    vector<int> parent(n, -1), order(1, 0);
    for (int i = 0; i < n; i++) {
        int u = order[i];
        for (Edge e : g[u]) if (e.v != parent[u]) {
            parent[e.v] = u;
            order.push_back(e.v);
        }
    }
    vector<long long> dp0(n), dp1(n);
    const long long INF = (1LL << 62);
    for (int i = n - 1; i >= 0; i--) {
        int u = order[i], children = 0;
        long long base = 0, a = INF, b = INF;
        for (Edge e : g[u]) if (parent[e.v] == u) {
            ++children;
            base += dp0[e.v];
            long long d = dp1[e.v] + e.w - c - dp0[e.v];
            if (d < a) { b = a; a = d; }
            else if (d < b) b = d;
        }
        // 父边不选：可选 0、1、2 条子边。
        dp0[u] = base + fee[u];
        if (children >= 1) dp0[u] = min(dp0[u], base + a + fee[u]);
        if (children >= 2) dp0[u] = min(dp0[u], base + a + b);
        // 父边已选：选一条子边后该点成为内部点。
        dp1[u] = base + fee[u];
        if (children >= 1) dp1[u] = min(dp1[u], base + a);
    }
    printf("%lld\n", n * c + dp0[0]);
}

Yuilice 的共用设备

题意简述

有 $n$ 个任务，第 $i$ 个任务耗时 $t_i$ 。每一批可以同时执行 $1$ 到 $3$ 个任务，批次耗时为其中最大的任务耗时。给出 $m$ 对冲突关系，同批任务中的任意两项都不能冲突。每个任务必须恰好执行一次，求总完成时间最小值。

解题思路

解题方法

批次之间只能顺序执行，所以总时间就是每个批次最大耗时的总和。任务的具体批次顺序不重要，只需要划分集合。

用二进制集合 mask 表示还没有安排的任务，令 dp[mask] 为安排这些任务的最小总时间。固定 mask 中编号最小的任务 $i$ ，枚举它所在的批次：

只放 $i$ ；
放 $i$ 和一个任务 $j$ ；
放 $i$ 、 $j$ 和 $k$ 。

检查批内每一对任务都没有冲突，然后转移到移除这些任务后的集合。固定最低编号任务后，每个划分只会被枚举一次；枚举第三个任务时限制 $k>j$ ，避免重复。

无冲突的部分分可以排序后每三个任务分一批。完整数据使用集合划分 DP。

用位掩码记录每个任务与哪些任务冲突。
按 mask 从小到大计算 dp[mask]，空集合的值为 $0$ 。
取出 mask 中最低编号的任务 $i$ 。
枚举与 $i$ 合法的单人、双人和三人批次，并更新 DP。
输出全集 dp[(1<<n)-1]。

任意合法划分中，最低编号任务 $i$ 都恰好属于一个大小为 $1$ 、 $2$ 或 $3$ 的批次。程序枚举了这个批次的所有合法成员组合，因此不会漏掉最优方案。

移除这一批后，剩余任务形成规模更小的同类问题。若剩余划分不是最优，就可以替换成更优划分而不影响已经选择的批次，矛盾。因此转移中的子问题必须取 dp 最优值。

反过来，每个转移都只加入合法批次，并与一个合法的剩余划分拼接，所以不会产生非法方案。按集合大小归纳，全集状态就是全局最优答案。

状态数为 $2^n$ ，每个状态枚举至多 $O(n^2)$ 个双人或三人批次，时间复杂度为 $O(n^2 2^n)$ ，空间复杂度为 $O(2^n+n^2)$ 。 $n\le18$ ，答案必须使用 long long。

三人批次必须检查三条冲突关系，不能只检查固定任务与另外两人的关系。
不能看到三个互不冲突的任务就立即成组，剩余任务仍需要全局最优。
固定最低编号任务是为了去重，不是限制最优方案的任务顺序。

部分分

测试点 1~2（ $m=0$ ，10 分）：按耗时降序排序，每三个任务分一批。
测试点 3~6（ $n\le9$ ，20 分）：递归枚举合法分组。
测试点 7~20（无额外限制，70 分）：固定最低编号任务所在批次，使用状压 DP。

参考代码

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    vector<long long> t(n);
    for (auto &x : t) scanf("%lld", &x);
    vector<int> ban(n, 0);
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        --u; --v;
        ban[u] |= 1 << v;
        ban[v] |= 1 << u;
    }
    vector<long long> dp(1 << n, 0);
    for (int mask = 1; mask < (1 << n); mask++) {
        int i = __builtin_ctz((unsigned)mask);
        int rest = mask ^ (1 << i);
        dp[mask] = dp[rest] + t[i];
        // 固定最低编号任务所在批次，只枚举其余零至两名成员。
        int avail = rest & ~ban[i];
        for (int js = avail; js; js &= js - 1) {
            int j = __builtin_ctz((unsigned)js);
            int r = rest ^ (1 << j);
            long long mx = max(t[i], t[j]);
            dp[mask] = min(dp[mask], dp[r] + mx);
            int ks = avail & ~ban[j] & ~((1 << (j + 1)) - 1);
            for (; ks; ks &= ks - 1) {
                int k = __builtin_ctz((unsigned)ks);
                dp[mask] = min(dp[mask], dp[r ^ (1 << k)] + max(mx, t[k]));
            }
        }
    }
    printf("%lld\n", dp.back());
}

有帮助，赞一个

去预览

0/2000

全部评论 45

蛋仔派对壶关
2

2026-10-14 来自广东
13
- shenzhangzheng小号
  回复
  蛋仔派对壶关
  3
  
  2026-10-15 来自浙江
  11
- ༺དༀ༒ŴĖĎF Ŷ༒ༀཌ༻
  回复
  蛋仔派对壶关
  5
  
  1周前来自北京
  2
可爱の小鹿茸哦！！！！！
1

2026-10-14 来自浙江
12
- shenzhangzheng小号
  回复
  可爱の小鹿茸哦！！！！！
  4
  
  2026-10-15 来自浙江
  6
蛋仔派对壶关
3

2026-10-14 来自广东
11
- ༺ཌༀཉི༒无敌草履虫༒༃ༀད༻
  回复
  蛋仔派对壶关
  2
  
  2026-10-20 来自浙江
  4
- 复仇者_阮迪安（蛋仔名16！软）
  回复
  蛋仔派对壶关
  呵呵呵
  
  2026-10-20 来自浙江
  5
可爱の小鹿茸哦！！！！！
1

2026-10-14 来自浙江
6
- shenzhangzheng小号
  回复
  可爱の小鹿茸哦！！！！！
  2
  
  2026-10-15 来自浙江
  4
可爱の小鹿茸哦！！！！！
1

2026-10-14 来自浙江
5
>u<
。

2026-10-19 来自浙江
3
麦晓雯大小姐（必回关）
。

2026-10-19 来自浙江
3
麦晓雯大小姐（必回关）
。

2026-10-19 来自浙江
3
麦晓雯大小姐（必回关）
。

2026-10-19 来自浙江
3
༺宇智波鼬༻ (沉浸在幻术中吧)
jrttttttttttttttttttttttttttttttttt
官方题解 | 巅峰赛#39题解
userId_undefined
Yuilice
2026-10-14 10:23:20

发布于：浙江

168
阅读
25
回复
30
点赞
导语
久违的巅峰赛，这次巅峰赛是以Dp和状压作为压轴的，毕竟许多朋友的状压熟练度还有待提升 (笑) 。

以下为题解

目录
题目编号题目标题难度
T1 Yuilice 的手工套装入门
T2 Yuilice 的相册整理普及-
T3 Yuilice 的分批冲印普及/提高-
T4 Yuilice 的打印店普及+/提高
T5 Yuilice 的小区接送普及+/提高
T6 Yuilice 的共用设备普及+/提高
Yuilice 的手工套装
题意简述
有 a 张大卡纸和 b 张小卡纸，每套手工套装需要一张大卡纸和一张小卡纸。可以把一张大卡纸剪成两张小卡纸，剪过的卡纸不能再当大卡纸使用。求最多能制作多少套。

样例 1 中输入为 5,0。剪开两张大卡纸后，还剩 3 张大卡纸和 4 张小卡纸，因此可以制作 3 套。样例 2 中小卡纸已经足够，直接使用 2 张大卡纸即可。

解题思路
解题方法
设剪开 x 张大卡纸，其中 0≤x≤a。操作结束后：

大卡纸有 a−x 张；
小卡纸有 b+2x 张。
每套需要两种卡纸各一张，所以固定 x 时最多制作

min(a−x,b+2x)

套。枚举全部合法的 x，取最大值即可。

读入 a,b，答案初始为 0。
枚举 x=0,1,…,a。
计算当前值 min(a−x,b+2x)，更新答案。
任意一种制作方案都会剪开某个合法数量 x 的大卡纸，因此一定会被程序枚举。固定 x 后，套数不能超过剩余大卡纸数量，也不能超过小卡纸数量，所以最多是 min(a−x,b+2x)；取出这么多张两种卡纸后可以逐套配对，说明这个上限能够达到。

程序枚举了所有可能的 x，并取其中最大值，所以得到的正是最优答案。

时间复杂度为 O(a)，额外空间复杂度为 O(1)。因为 a,b≤10
6
，中间数量不超过 3×10
6
，使用 int 足够。

剪纸后要同时减少大卡纸、增加小卡纸。
可以一次都不剪，x=0 必须被枚举。
不能直接输出 min(a,b)，因为剪纸可能增加可制作套数。
部分分
测试点 1~10（无额外限制）：枚举裁剪数量即可获得满分。
参考代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b;
cin >> a >> b;
int ans = 0;
for (int x = 0; x <= a; x++) {
// 剪开 x 张后，两种卡纸中较少的一种决定套数。
int now = min(a - x, b + 2 * x);
ans = max(ans, now);
}
cout << ans << '\n';
return 0;
}
Yuilice 的相册整理
题意简述
有 n 张照片，日期为 a
1

,a
2

,…,a
n

。如果 a
i

a
i+1

，则位置 i 有一处日期回退。可以不操作，也可以选择一段恰好包含 k 张照片的连续区间反转一次，求最少回退数。

反转只改变顺序，不改变日期；日期相等不算回退。

解题思路
解题方法
先记原序列的回退总数为 B，考虑反转区间 [l,r]，其中 r=l+k−1。

区间内部的相邻关系会全部反向：原来严格上升的关系会变成回退，原来的回退会消失，相等关系仍然不计数。设区间内部严格上升数为 U、回退数为 D，内部部分反转后对答案的贡献就是 U−D。

区间外的关系都不变，只需要检查最多两条连接边：

如果 l>1，原来的 (a
l−1

,a
l

) 变成 (a
l−1

,a
r

)；
如果 r<n，原来的 (a
r

,a
r+1

) 变成 (a
l

,a
r+1

)。
这样，每个区间都能在 O(1) 时间内算出答案。区间右移一格时，内部关系只删除最左边一对、加入最右边一对，因此 U,D 可以滑动维护。

统计原序列的回退数 B，并令答案初始为 B，表示可以不操作。
统计第一个长度为 k 的区间内部的上升数 U 和回退数 D。
枚举区间左端点，用 B+U−D 加上两侧连接的变化量得到当前答案。
窗口右移时删除离开窗口的相邻关系，加入新进入窗口的相邻关系。
输出所有方案中的最小值。
把原序列的相邻关系分为三类

2026-10-19 来自浙江
3
- 复仇者_阮迪安（蛋仔名16！软）
  回复
  ༺宇智波鼬༻ (沉浸在幻术中吧)
  握，打了很久吧
  
  2026-10-20 来自浙江
  1
古希腊掌管老师的神与小明之神
dddd

2026-10-17 来自四川
3
威龙凌霄戊卫
666

2026-10-14 来自浙江
3
bioxd.io
1

2026-10-14 来自浙江
3
可爱の小鹿茸哦！！！！！
1

2026-10-14 来自浙江
3
学
NoonMaple呢？

2026-10-20 来自浙江
2
麦晓雯大小姐（必回关）
。

2026-10-19 来自浙江
2
麦晓雯大小姐（必回关）
。

2026-10-19 来自浙江
2
༺宇智波鼬༻ (沉浸在幻术中吧)
fd

2026-10-19 来自浙江
2
蔡博轩
1、

2026-10-18 来自广东
2
嗯~
e

2026-10-17 来自浙江
2