巅峰赛 #39 题解 | 非官方

userId_undefined
杰杰
荣耀黄金GESP5级出道萌新快乐小狗勇敢小狗超能小狗

2026-10-12 20:52:06

发布于：香港

6阅读
0回复
0点赞

巅峰赛 #39 题解 | 非官方

本次题目猜测的总体难度如下，仅供参考：

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

T1. Yuilice 的手工套装

题目大意

有 aa 张大卡纸和 bb 张小卡纸。一个手工需要一张大卡纸和一张小卡纸。一张大卡纸可以变成两张小卡纸。请问最多能作多少个手工。

解题思路

看到 aa 的的范围 ≤106\le 10^6，所以可以遍历 aa。遍历的意思为将 ii 张大卡纸剪成小卡纸。新的小卡纸的数量为 b+2×ib + 2\times i，而大卡纸的数量为 a−ia - i。最后答案为 min⁡(na,nb)\min(na, nb)。

参考代码

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 200010;
const int MOD = 998244353;
const int INF = 1e18 + 10;
// const int MOD = 1e9 + 7;
 
void solve() {
    int a, b; cin >> a >> b;
    int ans = -INF;
    for(int i = 0; i <= a; i++) {
        int nb = b + 2 * i;
        int na = a - i;
        ans = max(ans, min(na, nb));
    }
    cout << ans;
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;

    while(T--) {
        solve();
    }
    
    return 0;
}

时间复杂度：O(n)O(n)

T2. Yuilice 的相册整理

题目大意

定义“日期回退”为 ai>ai+1a_i > a_{i+1}。现在可以反转 kk 个数，请问“日期回退”最少为多少。

解题思路

由于 kk 为定值，所以我们可以使用滑动窗口来维护反转的区间。使用前缀和优化，如果 l∼rl\sim r 的“日期回退”数量为 xx，那么反转后这段区间里面的“日期回退”数量则为 k−xk - x，如果搞不清楚，也可以设置一个反向“日期回退”的前缀和。另外，我们需要判断反转后的两个端点，即 [l−1,r][l - 1, r] 和 [l,r+1][l, r + 1]，如果这两个也满足则需要将答案加 1。但是如果前面一段增加了那么后面一段既没有了，所以还要额外判断一下。最后取最小值。

参考代码

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 200010;
const int MOD = 998244353;
const int INF = 1e18 + 10;
// const int MOD = 1e9 + 7;
 
int a[N], pref[N], preb[N];

void solve() {
    int n, k; cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = 1; i < n; i++) {
        if(a[i] > a[i + 1]) pref[i] = pref[i - 1] + 1;
        else pref[i] = pref[i - 1];
        if(a[i] < a[i + 1]) preb[i] = preb[i - 1] + 1;
        else preb[i] = preb[i - 1];
    }

    int res = pref[n - 1];
    for(int l = 1; l <= n - k + 1; l++) {
        int r = l + k - 1;
       	int cur = preb[r - 1] - preb[l - 1];
        if(l >= 2) cur += pref[l - 2];
        
        if(r <= n - 1) cur += pref[n - 1] - pref[r];
        
        if(a[l] > a[r + 1]) cur++;
        
        if(a[l - 1] > a[r]) cur++;
        
        res = min(res, cur);
    }

    cout << res;
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;

    while(T--) {
        solve();
    }
    
    return 0;
}

时间复杂度：O(n)O(n)

T3. Yuilice 的小区接送

题目大意

有一颗 nn 个节点 n−1n-1 条边的树，需要将这个树拆成若干条简单路径。每条路径需要：

  • 支付一次固定派车费 CC。
  • 支付路径经过的每条道路的行驶费用。
  • 若路径至少包含两个站点，支付两个端点各自的服务费，内部站点不收费。
  • 若路径只有一个站点，只支付该站点一次服务费。

求所有路径费用之和的最小可能值。

解题思路

设 dp[u][fa]dp[u][fa] 为到这个节点能够获得最优解的森林构造。

设 basebase 为全部不相连的最代价，为所有孩子的 dp[v][0]dp[v][0] 之和，加上自己的端点服务费 pup_u 和 派车费 CC。也就是：

(∑v∈subtree(u)dp[v][0]))+C+pu\Bigg( \sum_{v\in subtree(u)}dp[v][0])\Bigg) + C + p_u

如果 fa=0fa = 0，那么可以连接 0,1,20, 1, 2 个孩子。每连接一个孩子，代价为 delta=w−C−dp[v][0]+dp[v][1]delta = w - C - dp[v][0] + dp[v][1]，找到代价最小的两个，设为 delta1,delta2delta_1, delta_2。当连接 11 个孩子的时候，变化为 delta1delta_1；当连接 22 个孩子的时候，变化为 delta1+delta2−pudelta_1 + delta_2 - p_u。所以 dp[u][0]=min⁡(base,base+delta1,base+delta1+delta2−pu)dp[u][0] = \min(base, base + delta_1, base + delta_1 + delta_2 - p_u)。

如果 fa=1fa = 1，那么可以连 00 个孩子或者 11 的孩子。每连接一个孩子，代价为 delta=w−C−dp[v][0]+dp[v][1]delta = w - C - dp[v][0] + dp[v][1]，找到代价最小的一个。dp[u][1]=min⁡(base,base+delta−pu)dp[u][1] = \min(base, base + delta - p_u)。减去 pup_u 的原因是 uu 多连了一个后，就变成内部点，内部站点不收费。

最后输出 dp[1][0]dp[1][0]，因为根节点不可能有父亲。

参考代码

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 200010;
const int MOD = 998244353;
const int INF = 1e18 + 10;
// const int MOD = 1e9 + 7;
 
struct Node{
    int v, w;
};

int a[N], n, c, dp[N][2]; //0 : 不选，1 : 选
vector<Node> ve[N];

void dfs(int u, int fa) {
    int cur = 0;

    dp[u][0] = dp[u][1] = c + a[u];
    int sum = 0;
    vector<int> delta;    

    for(auto [v, w] : ve[u]) {
        if(v == fa) continue;
        dfs(v, u);

        sum += dp[v][0];
        delta.push_back(w - c - dp[v][0] + dp[v][1]);
    }

    sort(delta.begin(), delta.end());

    int base = sum + c + a[u];
    
    if(delta.size() == 0) {
     	dp[u][0] = dp[u][1] = base;   
    }
    if(delta.size() >= 1) {
        dp[u][1] = min(base, base + delta[0] - a[u]);
        dp[u][0] = min(base, base + delta[0]);
    } 
    if(delta.size() >= 2) {
        dp[u][0] = min({base, base + delta[0], base + delta[0] + delta[1] - a[u]});
    }
}

void solve() {
    cin >> n >> c;

    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = 1; i < n; i++) {
        int u, v, w; cin >> u >> v >> w;
        ve[u].push_back({v, w});
        ve[v].push_back({u, w});
    }

    dfs(1, 0);

    cout << dp[1][0];
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;

    while(T--) {
        solve();
    }
    
    return 0;
}

时间复杂度：O(nlog⁡n)O(n\log n)

T4. Yuilice 的分批冲印

题目大意

有 nn 张照片，第 ii 张照片的打印时间为 tit_i，准备参数为 sis_i。可以把这些照片片分成至多 kk 个非空批次，一个批次的耗时等于其中所有照片的打印时间之和，再加上这些照片的准备参数的最大值。求批次中最大耗时的最小可能值。

解题思路

当我们在题目里面看到“最大值最小”或者“最小值最大”，我们就要先想到二分。我们这一题可以二分的是耗时。我们将 aa 不断从前往后遍历，如果 (sum+ti +(sum + t_i \space+ 区间最大 si)>mids_i) > mid，那就说明再加一个数是不可行的，所以我们要分段。记录段数为 cntcnt，如果 cnt≤kcnt \le k，则方案可行；否则不可行。

参考代码

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 200010;
const int MOD = 998244353;
const int INF = 1e18 + 10;
// const int MOD = 1e9 + 7;
 
int t[N], s[N], n, k;

bool check(int mid) {
    int cnt = 1;
    int sum = 0;
    int ma = 0;
    for(int i = 1; i <= n; i++) {
        int x = t[i];
        ma = max(ma, s[i]);

        if(sum + x + ma > mid) {
            cnt++;
            sum = x;
            ma = s[i];
            
            if(sum + ma > mid) return false;
        } else {
            sum += x;
        }
    }
    return cnt <= k;
}

void solve() {
    cin >> n >> k;
    int l = 0, r = 0;
    for(int i = 1; i <= n; i++) {
        cin >> t[i] >> s[i];
        r += t[i];
        l = max(l, t[i] + s[i]);
    }

    r += *max_element(s + 1, s + n + 1);

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

    cout << ans;
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;

    while(T--) {
        solve();
    }
    
    return 0;
}

时间复杂度：O(nlog⁡(∑ti+max⁡si))O(n\log (\sum t_i + \max s_i))

T5. Yuilice 的打印店

题目大意

有 pp 台打印机，第 j 台打印机打印一页需要 sjs_j 个时间单位。有四种操作：增加订单、取消订单、暂停接收、恢复接受。若在时刻 tt 把一个 aa 页的订单交给打印机 jj，它在时刻 t+asjt+as _j 完成。求订单最终的结果。

解题思路

这是一题非常罕见的大模拟，让我们分析一下。

我们可以先创建一个 enum{enum}，表示订单状态。订单有四种状态，分别为：等待中、打印中、已取消、已完成。接着，我们分别要创建三个不同的结构体，分别是：打印机、订单、操作。

  • 打印机结构体中，需要包含：

    • 速度
    • 当前订单
    • 订单结束时间
    • 是否可以用
    • 打印机编号（可有可无）

  • 订单结构体中，需要包含：

    • 订单编号
    • 订单页数
    • 订单状态
    • 订单答案结果

  • 操作结构体中，需要包含：

    • 操作类型
    • 操作编号
    • 操作参数
    • 操作编号（可有可无）

接下来开始模拟，我们需要将打印机的操作开一个函数，表示操作。每一次操作需要遍历所有的打印机，如果这台打印机可用，那么我们就要从订单列表里面拿取下一个订单。但是如果这个订单取消了，我们就需要遍历下一个。接下来将打印机当前订单设置为这个订单，将订单状态设置为打印中，将订单结束时间设置为当前时间加上订单页数乘以打印机速度。然后将这个结束时间加入一个操作的大根堆，方便我们后续进行操作。

然后是主函数里面的操作。我们如果看到 op=0op = 0，那说明这是自己设置的，其中的意思为订单已经完成。我们将这台打印机设置为空闲状态，订单设置为已完成，结果为完成时刻。如果 op=1op = 1，则增加订单，将订单加入订单列表，订单数量 cnt++cnt++。如果 op=2op = 2，那判断订单是否存在，且订单状态是否为等待中，如果是，则将订单状态设置为已取消，将答案设为 −1-1。如果 op=3op = 3，直接将打印机能否使用改为 falsefalse。如果 op=4op = 4，则将打印机能否使用改为 truetrue。

接下来，如果操作为空，或者操作堆顶的结束时间不等于当前时间，则调用打印机操作函数。

最后，输出每一个订单的答案即可。

参考代码

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 200010;
const int MOD = 998244353;
const int INF = 1e18 + 10;
// const int MOD = 1e9 + 7;

enum status {
    wait, cancel, done, print
};

struct Order {
    int id, t, pa;
    status st;
    int res = -2;
};

struct printer {
    int sp, cur, ftime, id;
    bool usable;
};

struct Op {
    int t, op, x, order;

    bool operator > (const Op& y) const {
        if(t != y.t) return t > y.t;

        else if(op == 0 && y.op != 0) return false;
        else if(op != 0 && y.op == 0) return true;

        return order > y.order;
    }
};

int n, qq;
vector<printer> prt(N);
vector<Order> ord;

void start(int curt, queue<int>& q, priority_queue<Op, vector<Op>, greater<Op>>& pq) {
    for(int i = 1; i <= n; i++) {
        if(prt[i].usable && prt[i].cur == 0) {
            while(!q.empty()) {
                int nxt_ord = q.front();
                if(ord[nxt_ord].st == cancel) {
                    q.pop();
                    continue;
                }

                q.pop();
                prt[i].cur = nxt_ord;
                ord[nxt_ord].st = print;

                int fin_time = curt + prt[i].sp * ord[nxt_ord].pa;
                prt[i].ftime = fin_time;

                pq.push({fin_time, 0, i, nxt_ord});
                break;
            }
        }
    }
}

void solve() {
    cin >> n >> qq;
    for(int i = 1; i <= n; i++) {
        int sp; cin >> sp;
        prt[i] = {sp, 0, 0, i, true};
    }

    ord.push_back({0, 0, 0, cancel, -1});
    int cnt = 0;

    priority_queue<Op, vector<Op>, greater<Op>> pq;
    queue<int> q;

    for(int i = 1; i <= qq; i++) {
        int t, op, x; cin >> t >> op >> x;
        pq.push({t, op, x, i});
    }

    while(!pq.empty()) {
        auto opa = pq.top(); pq.pop();
        int cur = opa.t;

        if(opa.op == 0) {
            int prt_id = opa.x;
            int ord_id = prt[prt_id].cur;
            
            if(ord_id != 0) {
                ord[ord_id].st = done;
                ord[ord_id].res = cur;
                prt[prt_id].cur = 0;
            } 
        } else if(opa.op == 1) {
            cnt++;
            ord.push_back({cnt, cur, opa.x, wait, -2});
            q.push(cnt);
        } else if(opa.op == 2) {
            int tar = opa.x;

            if(tar <= cnt && ord[tar].st == wait) {
                ord[tar].st = cancel;
                ord[tar].res = -1;
            }
        } else if(opa.op == 3) {
            prt[opa.x].usable = false;
        } else if(opa.op == 4) {
            prt[opa.x].usable = true;
        }

        if(pq.empty() || pq.top().t != cur) {
            start(cur, q, pq);
        }
    }

    for(int i = 1; i <= cnt; i++) cout << ord[i].res << endl;
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;

    while(T--) {
        solve();
    }
    
    return 0;
}

单组测试样例时间复杂度：O(qlog⁡q)O(q\log q)。

T6. Yuilice 的共用设备

题目大意

有 nn 个任务，每个人物有一个时间单位。每台设备可以有 1∼31\sim 3 项任务。同一批中的任务同时开始，这一批的耗时等于其中最长任务的耗时。只有当前批次全部完成，下一批才能开始。有 mm 对任务存在冲突，每对冲突任务不能放在同一批。计算完成全部任务的最短总时间。

解题思路

看到 nn 的范围 ≤18\le 18，范围非常小，所以可以使用状压 dpdp。

定义 SS 为任务的完成状态，如果二进制下的位为 11，表示已完成；否则未完成。dp[S]dp[S] 为记录完成状态 SS 下的最小总耗时。

我们预先处理好所有的不冲突情况，n3n^3 暴力枚举，把任务状态最大值也记录下来，使用邻接表表示冲突关系。

状压 dpdp 过程中，我们要判断当前状态与之前暴力枚举的 maskmask 是否有交集。如果有，则直接跳过，因为当前状态一定比之前状态更优。转移方程为：

dp[S ∣ mask]=min⁡(dp[S ∣ mask],val+dp[S])dp[S\space| \space mask] = \min(dp[S\space| \space mask], val + dp[S])

最后结果为 dp[(1≪n)−1]dp[(1 \ll n) - 1]。

参考代码

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 20;
const int MOD = 998244353;
const int INF = 1e18 + 10;
// const int MOD = 1e9 + 7;
 
struct Node {
    int x, y, z;
};

int n, m, a[N];
bool conf[N][N];
int dp[1 << N];
vector<PII> val;
map<PII, int> mp;

void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> a[i];

    for(int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        conf[u][v] = true;
        conf[v][u] = true;
    }

    int res = 0, cnt = 0, base = 0;
    
    for(int i = 1; i <= n; i++) {
        val.push_back({1 << (i - 1), a[i]});
        for(int j = i + 1; j <= n; j++) {
            if(conf[i][j]) continue;
            val.push_back({1 << (i - 1) | (1 << (j - 1)), max(a[i], a[j])});

            for(int k = j + 1; k <= n; k++) {
                if(!conf[i][k] && !conf[j][k]) {
                    val.push_back({1 << (i - 1) | (1 << (j - 1)) | (1 << (k - 1)), max({a[i], a[j], a[k]})});   
                }
            }
        }
    }

    for(int i = 0; i <= (1 << n); i++) {
        dp[i] = INF;
    }
    
    dp[0] = 0;

    for(int S = 0; S < (1 << n); S++) {
        if(dp[S] == INF) continue;
        
		for(auto [ma, v] : val) {
			if((S & ma) == 0) {
                dp[S | ma] = min(dp[S | ma], v + dp[S]);
            }
        }
    } 

    cout << dp[(1 << n) - 1];
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    // cin >> T;

    while(T--) {
        solve();
    }
    
    return 0;
}

时间复杂度：O(2n⋅n3)O(2^n \cdot n^3)

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论