教学记录
2024年下学期信奥记录
2025上学期上课记录
国庆第二天
国庆第三天
国庆第五天
提高组10月18日 国庆第十天
本文档使用 MrDoc 发布
-
+
首页
国庆第二天
第二题的代码 // 029 - Long Bricks(★5) #include <bits/stdc++.h> using namespace std; struct SegTree { int N; vector<int> maxv, setv; // maxv: 区间最大值, setv: 懒惰标记(-1表示无) SegTree(int n) : N(n), maxv(4 * n + 2), setv(4 * n + 2, -1) {} // 下推懒惰标记:将父节点的更新任务传递给子节点 void pushdown(int o) { int lc = 2 * o, rc = 2 * o + 1, &s = setv[o]; if (s > -1) { // 如果当前节点有“待办”更新 maxv[lc] = maxv[rc] = setv[lc] = setv[rc] = s; // 执行更新并传递任务 s = -1; // 清除当前节点的“待办” } } // 查询区间 [ql, qr] 的最大值 int query(int ql, int qr, int o = 1, int L = 1, int R = -1) { if (R == -1) R = N; if (ql <= L && R <= qr) return maxv[o]; // 区间完全覆盖,直接返回结果 int lc = 2 * o, rc = 2 * o + 1, m = (L + R) / 2, ans = 0; pushdown(o); // 查询子节点前,先处理懒惰任务 if (ql <= m) ans = max(ans, query(ql, qr, lc, L, m)); if (m < qr) ans = max(ans, query(ql, qr, rc, m + 1, R)); return ans; } // 更新区间 [ql, qr] 的值为 v int update(int ql, int qr, int v, int o = 1, int L = 1, int R = -1) { if (R == -1) R = N; if (ql <= L && R <= qr) { // 区间完全覆盖,打上懒惰标记 return setv[o] = maxv[o] = v; } int lc = 2 * o, rc = 2 * o + 1, m = (L + R) / 2; pushdown(o); // 更新子节点前,先处理懒惰任务 if (ql <= m) update(ql, qr, v, lc, L, m); if (m < qr) update(ql, qr, v, rc, m + 1, R); return maxv[o] = max(maxv[lc], maxv[rc]); // 用子节点信息更新自己 } }; int main() { ios::sync_with_stdio(false), cin.tie(0); int W, N; cin >> W >> N; SegTree T(W + 1); // 建立覆盖 [1, W] 的线段树 for (int i = 0, l, r; i < N and cin >> l >> r; i++) { int h = T.query(l, r) + 1; // 1. 查询最大高度 T.update(l, r, h); // 2. 区间更新为新高度 cout << h << "\n"; } return 0; } 第三题 // USACO2023 Dec S, Bovine Acrobatics #include <bits/stdc++.h> #define _for(i, a, b) for (int i = (a); i < (int)(b); i++) using namespace std; int main() { ios::sync_with_stdio(false), cin.tie(0); int N, M, K; cin >> N >> M >> K; struct Cow { int w, a; }; vector<Cow> C(N); for (Cow &c : C) cin >> c.w >> c.a; sort(C.begin(), C.end(), [&](const Cow &a, const Cow &b) { return a.w > b.w; }); long long ans = 0; map<int, int, greater<int>> T{{int(2e9), M}}; for (const Cow &c : C) { // 从大到小枚举每一种牛 int a = c.a; // 这种牛的数量, 从塔顶最大的开始 for (auto it = begin(T); a > 0 and it != end(T) and it->first - c.w >= K;) { // 如果该重量的牛数量为0,或者与当前塔顶不能满足题意要求(后续塔肯定也不满足),就准备操作下一种重量的牛 int &w = it->second, x = min(w, a); // 当前塔最多能叠放多少奶牛 w -= x, a -= x; if (w == 0) it = T.erase(it); // 这个塔顶全部放了牛c,等于被替代了 } // c.a-a个奶牛就会有c.w个塔 if (a < c.a) T[c.w] += c.a - a, ans += c.a - a; } cout << ans; return 0; }
admin
2025年10月2日 21:58
转发文档
收藏文档
上一篇
下一篇
手机扫码
复制链接
手机扫一扫转发分享
复制链接
进则科技特长,退则数理化强
Markdown文件
分享
链接
类型
密码
更新密码