当前位置：首页 > news >正文

NOIP 模拟赛 4 总结

news 2026/3/27 1:13:35

分数：\(40 + 0 + 0 + 0 = \color{red}{40}\)

我恨子任务！
我恨全是坑的贪心！
我很码量超大的数据结构！
我恨 ad-hoc ！

当然，还是要承认自己很菜，不然分数不可能如此惨淡。

T1

众所周知，贪心本身并不难，难的是这么证明一道题是贪心，以及找到具体的贪心策略。显然我就在这一点上翻车了。

对于这道题，我是这么想的：

把每条边的边权设为 \(\max(0, s_i - k)\)；
使用 Kruskal 算法跑最小生成树；
检查已选的边中的最大值 \(\max(s_i)\) 是否小于 \(k\) ，若小于，则在答案上加 \(k - \max(s_i)\)。

然而这么干是有问题的，因为当 \(\max(s_i) < k\) 时，原本限速最大的那条边可能不会被选入最小生成树中。

那么正解是什么呢？首先我们直接把限速当成边权，然后跑一边 Kruskal。接着分两种情况考虑：

如果最小生成树上的最大边权 \(\ge k\)，那么最终选中的树一定最优，这时 \(\mathrm{ans} = \sum\limits \max(0, E - k), E \in \mathrm{MST}\) ;
否则，直接放弃掉刚才的最小生成树，选择最接近 \(k\) 的那条边作为最小生成树的一条边，然后改变它的限速。由于题目规定原有的图为强连通图，因此一定可以以这条边构造生成树。

时间复杂度 \(O(m \log m)\)。

跳过代码

#include <bits/stdc++.h>
typedef long long ll;
const int M = 2e5+10, N = 2e5+10;
struct Side {int s, t, speed;
} s[M];
int n, m, k;struct UF {int par[N], siz[N];void init() {for (int i = 1; i <= n; i++) {par[i] = i;siz[i] = 1;}}int find(int u) {return u == par[u] ? u : (par[u] = find(par[u]));}void merge(int u, int v) {u = find(u), v = find(v);if (siz[u] > siz[v]) std::swap(u, v);par[u] = v;siz[v] += siz[u];}
} uf;
signed main() {freopen("speed.in", "r", stdin);freopen("speed.out", "w", stdout);std::ios::sync_with_stdio(false); std::cin.tie(0);std::cin >> n >> m >> k;ll ans1 = 1e18, ans2 = 0;for (int i = 1; i <= m; i++) {int u, v, w;std::cin >> u >> v >> w;s[i] = {u, v, w};ans1 = std::min(ans1, ll(std::abs(s[i].speed - k)));}std::sort(s+1, s+1+m, [](Side a, Side b) {return a.speed < b.speed;});int cnt = 0;uf.init();int mx = 0;std::vector <Side> chosen;for (int i = 1; i <= m; i++) {if (cnt >= n - 1) break;if (uf.find(s[i].s) == uf.find(s[i].t)) continue;uf.merge(s[i].s, s[i].t);cnt++;if (s[i].speed > k) ans2 += s[i].speed - k;}std::cout << std::max(ans1, ans2) << '\n';return 0;
}

T2

一道神秘 Ad-hoc（思维题），候补。

T3

一道神秘数据结构题。我在考场上想到了线段树，但是因为节点设计不合理遗憾离场。赛后翻看了 AeeE5x 大神的代码，被他分块 + 线段树的做法大为震撼。

首先我们可以用分块的思想，每个块中储存其单调性信息（全部相同 / 递增 / 递减 / 其它）以及懒标记（用于优化区间加法）。检查一个区间是否递增 / 递减 / 全部相同是很显然的，那么如何检查其是否单峰呢？我们可以找到查询区间的最大值在哪里，然后看看其左侧是否单调递增，右侧是否单调递减即可。查询最大值可以用线段树维护。时间复杂度 \(O(q \sqrt{n})\)。

以上描述听起来很简单，但既然这道题卡了我 2 个小时，说明其中坑点满满：

注意 pushdown、修改和 getType 的先后顺序；
注意修改的范围；
注意 long long；
……

澄清：由于代码较长，逻辑较为复杂，以下代码使用了较为规范的命名和码风，并使用 enum、Lambda 表达式进一步增加可读性。这样的代码可能看起来像 AI 生成的，但本人保证此代码非 AI 直接编写。 类似 enum、Lambda 表达式等语法虽然看起来有些“科技”，但可以增加可读性、减少码量，同时也被 C++14 支持，同学们可以酌情学习。

跳过代码

#include <bits/stdc++.h>
typedef long long ll;
const int N = 1e5+10, SQRT_N = 320;
const ll MIN = -1e18;
int n, q; ll a[N];class Segtree {private:struct Node {int le, ri;std::pair<ll, int> maxVal; // val, pos;ll tag;} tr[4 * N];void pushDown(int p) {if (tr[p].tag) {tr[p*2].tag += tr[p].tag;tr[p*2+1].tag += tr[p].tag;tr[p*2].maxVal.first += tr[p].tag;tr[p*2+1].maxVal.first += tr[p].tag;tr[p].tag = 0;}}void pushUp(int p) {tr[p].maxVal = std::max(tr[p*2].maxVal, tr[p*2+1].maxVal);}public:  void build(int s = 1, int t = n, int p = 1) {tr[p] = {s, t, {MIN, 0}, 0};if (s == t) {tr[p].maxVal = {a[s], s};return;}int mid = (s + t) >> 1;build(s, mid, p*2);build(mid+1, t, p*2+1);pushUp(p);}void update(int l, int r, ll c, int s = 1, int t = n, int p = 1) {if (l <= s && t <= r) {tr[p].tag += c;tr[p].maxVal.first += c;return;} pushDown(p);int mid = (s + t) >> 1;if (l <= mid) {update(l, r, c, s, mid, p*2);}if (r > mid) {update(l, r, c, mid+1, t, p*2+1);}pushUp(p);}std::pair<ll, int> queryMax(int l, int r, int s = 1, int t = n, int p = 1) {if (l <= s && t <= r) {return tr[p].maxVal;}pushDown(p);int mid = (s + t) >> 1;std::pair<ll, int> res = {MIN, 0};if (l <= mid) {auto temp = queryMax(l, r, s, mid, p*2);if (temp.first > res.first) {res = temp;}}if (r > mid) {auto temp = queryMax(l, r, mid+1, t, p*2+1);if (temp.first > res.first) {res = temp;}}return res;}
} tree;int blockSize, blockID[N];enum Type {inc, dec, same, others
};
struct Block {int start; ll add;  Type type;
} blocks[SQRT_N];void pushDown(int p) {if (!blocks[p].add) return;for (int i = blocks[p].start; i < blocks[p+1].start; i++) {a[i] += blocks[p].add;}blocks[p].add = 0;
}void getType(int p) {bool isInc = true, isDec = true, isSame = true;for (int i = blocks[p].start + 1; i < blocks[p+1].start; i++) {isInc &= (a[i-1] < a[i]);isDec &= (a[i-1] > a[i]);isSame &= (a[i-1] == a[i]);}if (isInc) blocks[p].type = inc;else if (isDec) blocks[p].type = dec;else if (isSame) blocks[p].type = same;else blocks[p].type = others;
}void rangeAdd(int l, int r, ll c) {pushDown(blockID[l]);if (blockID[l] == blockID[r]) {for (int i = l; i <= r; i++) {a[i] += c;}    getType(blockID[r]);} else {pushDown(blockID[l]);for (int i = l; i < blocks[blockID[l] + 1].start; i++) {a[i] += c;}getType(blockID[l]);for (int i = blockID[l] + 1; i < blockID[r]; i++) {blocks[i].add += c;}pushDown(blockID[r]);for (int i = blocks[blockID[r]].start; i <= r; i++) {a[i] += c;}    getType(blockID[r]);}
}bool check(int l, int r, Type type) {std::function <bool(ll, ll)> cmp;if (type == same) {cmp = [](ll a, ll b) -> bool {return a == b;};} else if (type == inc) {cmp = [](ll a, ll b) -> bool {return a < b;};} else if (type == dec) {cmp = [](ll a, ll b) -> bool {return a > b;};}bool res = true;int lBlock = blockID[l];int rBlock = blockID[r];if (lBlock == rBlock) {pushDown(lBlock);getType(lBlock);for (int i = l + 1; i <= r; i++) {res &= cmp(a[i-1], a[i]);}} else {pushDown(lBlock);pushDown(rBlock);getType(lBlock);getType(rBlock);for (int i = l + 1; i < blocks[lBlock+1].start; i++) {res &= cmp(a[i-1], a[i]);}for (int i = lBlock + 1; i < rBlock; i++) {res &= (blocks[i].type == type && cmp(blocks[i-1].add + a[blocks[i].start - 1], blocks[i].add + a[blocks[i].start]));}res &= cmp(blocks[rBlock - 1].add + a[blocks[rBlock].start - 1], a[blocks[rBlock].start]);for (int i = blocks[rBlock].start + 1; i <= r; i++) {res &= cmp(a[i-1], a[i]);}}return res;
}bool checkPeak(int l, int r) {int maxPos = tree.queryMax(l, r).second;if (maxPos == l || maxPos == r) return false;return check(l, maxPos, inc) && check(maxPos, r, dec);
}signed main() {#ifndef ONLINE_JUDGEfreopen("peak.in", "r", stdin);freopen("peak.out", "w", stdout);#endifstd::ios::sync_with_stdio(false); std::cin.tie(0);std::cin >> n;for (int i = 1; i <= n; i++) {std::cin >> a[i];}blockSize = std::max(int(std::sqrt(n)), 1);for (int i = 1; i <= n; i++) {blockID[i] = (i - 1) / blockSize + 1;if (!blocks[blockID[i]].start) {blocks[blockID[i]].start = i;}}blocks[blockID[n] + 1].start = n + 1;for (int i = 1; i <= blockID[n]; i++) {bool isInc = true, isDec = true, isSame = true;for (int j = blocks[i].start + 1; j < blocks[i+1].start; j++) {isInc &= (a[j-1] < a[j]);isDec &= (a[j-1] > a[j]);isSame &= (a[j-1] == a[j]);}if (isInc) blocks[i].type = inc;else if (isDec) blocks[i].type = dec;else if (isSame) blocks[i].type = same;else blocks[i].type = others;} tree.build();std::cin >> q;while (q--) {int op, l, r;std::cin >> op >> l >> r;if (op == 1) {ll x;std::cin >> x;rangeAdd(l, r, x);tree.update(l, r, x);} else if (op == 2) {std::cout << check(l, r, same) << '\n';} else if (op == 3) {std::cout << check(l, r, inc) << '\n';} else if (op == 4) {std::cout << check(l, r, dec) << '\n';} else if (op == 5) {std::cout << checkPeak(l, r) << '\n';}}return 0;
}