【比赛总结】20260606 模拟赛总结

P3619 魔法

题目大意：

给定 \(n\) 对元素与数字 \(T\)，可以按任意顺序遍历所有元素，对于当前元素 \(i\)，若 \(T>t_i\)，则 \(T\gets T+v_i\)，否则遍历失败。求问是否存在一种顺序可以遍历 \(n\) 对元素。

其中 \(1\le n,T,t_i\le 10^5,-10^5\le v_i\le 10^5\)。

将元素对分成两部分：\(v_i\ge 0\) 与 \(v_i<0\)。

显然，先处理 \(v_i\ge 0\) 再处理 \(v_i<0\) 是最优的。

对于 \(v_i \ge 0\)：感性理解一下，我们与其去赌 \(t_i\) 大的，不如先老老实实的拿稳小的，因为 \(T\) 一直是增加的，所以 \(t_i<t_j\) 的时候是最优的。

对于 \(v_i < 0\)，进行相邻点分析。

有两对相邻元素 \((t_i,v_i)\) 与 \((t_j,v_j)\)，设当前时间为 \(T\)，若 \(i\) 前 \(j\) 后，则：

\[\begin{cases}T>t_i\\T+v_i>t_j\end{cases} \]

进一步，可得：

\[T>\max(t_i,t_j-v_i) \]

同理，若 \(i\) 后 \(j\) 前，则：

\[T>\max(t_j,t_i-v_j) \]

如果我们想让 \(T\) 的限制更宽松一点，即 \(i\) 在前优于 \(j\) 在前就要求：

\[\max(t_i,t_j-v_i)<\max(t_j,t_i-v_j) \]

注意到 \(v<0\)，所以 \(t<t-v\)，因此比较的关键在于 \(t_j-v_i<t_i-v_j\)，即：

\[t_i+v_i>t_j+v_j \]

按照这个排序就好了。

#include <bits/stdc++.h>
#define ll long long 
using namespace std;const int N = 1e5 + 10; int n, T;struct node {ll t, w, p;ll prz; 
} a[N];bool cmp(node x, node y) {if (x.prz != y.prz) return x.prz > y.prz;if (x.prz == 1) return x.t < y.t;if (x.prz == -1) return x.t + x.w > y.t + y.w;
}void solve() {cin >> n >> T;for (int i = 1; i <= n; i++) {cin >> a[i].t >> a[i].w;if (a[i].w >= 0) a[i].prz = 1;if (a[i].w < 0) a[i].prz = -1;a[i].p = max(a[i].t, -a[i].w);}sort(a + 1, a + n + 1, cmp);ll now = T, is = 1;for (int i = 1; i <= n; i++) {if (now <= 0 || now <= a[i].t) {cout << "-1s\n";return ;}now += a[i].w;}if (now <= 0) cout << "-1s\n";else cout << "+1s\n";
}int main() {ios::sync_with_stdio(0);cin.tie(0);int Z; cin >> Z;while (Z--) solve();return 0;
} 

P3214 [HNOI2011] 卡农

题目大意：我们要在 \(n\) 个音阶的所有非空子集（即片段）中挑选 \(m\) 个不同的子集，使得每个音阶在所有挑出的片段中出现的总次数为偶数。两个选取方案如果在调整片段的顺序后相同，则被视作同种音乐。

我们可以将每种片段看作是一个长度为 \(n\) 的二进制数，由于不能是空集，每个二进制数的值都在 \(1\) 到 \(2^n - 1\) 之间。

题目等价于：在 \(1\) 到 \(2^n - 1\) 中选出 \(m\) 个互不相同的数，且它们的异或和为 \(0\)（因为每种音阶出现的次数都为偶数，即在同一位上的 \(1\) 个数为偶数，异或必然为 \(0\)）。最后由于不考虑选取顺序，我们需要将得到的方案数除以 \(m!\)。

计算方案数肯定要 DP 呀。

• 状态：定义 \(f_i\) 表示有序地挑选 \(i\) 个互不相同的非 \(0\) 数，并且它们的异或和为 \(0\) 的方案数。
• 状态转移方程：

设 \(P_{i-1}\) 为任选 \(i-1\) 个互不相同的非 \(0\) 数的方案数（不管异或和）：

\[P_{i-1} = (2^n - 1)(2^n - 2)\dots(2^n - i + 1) \]

我们只需要从中减去非法的方案就好了。

第一种情况：若第 \(i\) 个数为 \(0\)，则要求前 \(i-1\) 个元素异或和为 \(0\) 的方案数，即 \(f_{i-1}\)。

第二种情况：

第 \(i\) 个数与前 \(i-1\) 个数中的某个数相等，假设与第 \(k\) 个数相等。这意味着除了第 \(k\) 个数以外的其余 \(i-2\) 个数异或和为 \(0\)。

我们可以把它们看作是一个长度为 \(i-2\) 且异或和为 \(0\) 的合法方案。对于每种这样的合法方案，有 \(i-1\) 个位置可以安插第 \(k\) 个数。第 \(k\) 个数的取值可以是除去这 \(i-2\) 个数以及 \(0\) 之外的任意一个数，共有 \((2^n - 1) - (i - 2) = 2^n - i + 1\) 种选择。所以这种情况共有 \((i-1)(2^n - i + 1)f_{i-2}\) 种。

因此 \(f_i=P_{i-1}-f_{i-1}-(i-1)(2^n - i + 1)f_{i-2}\)。

• 初始化：\(f_0=1,f_1=0\)。

答案就是 \(\Large{\frac{f_m}{m!}}\)（不计顺序）。

P3968 [TJOI2014] 电源插排

维护动态开点线段树上四个信息：

• 区间最长连续空位长度
• 区间左起最长连续空位长度
• 区间右起最长连续空位长度
• 区间空位数量

赛时挂分点：

1. 在左侧完全空闲时，没有让父节点的左起最长连续空位长度向右侧延伸
2. 寻找最长空闲区间时，没有遵循最靠右原则，即优先查右树 -> 跨界 -> 左树
3. 读错题目，当区间长度为偶数时，把插排位置理解为最靠右插排，实为中点靠右插排
4. 查询区间内空闲插排数时爆栈了

#include <bits/stdc++.h>
using namespace std;// 动态开点线段树的最大节点数，扩大以防止 MLE/RE
const int N = 6e6 + 10; int n, q, root;
int tot = 1;
map<int, int> cnt;struct node {int l, r, ls, rs;// 区间内空闲插排数量，总最长连续空闲，左起最长空闲，右起最长空闲int siz, all, le, re;
} tree[N];void newnode(int &rt, int l, int r) {tree[rt].l = l;tree[rt].r = r;tree[rt].all = tree[rt].le = tree[rt].re = tree[rt].siz = r - l + 1;
}void pushup(int rt) {int ls = tree[rt].ls, rs = tree[rt].rs;int mid = (tree[rt].l + tree[rt].r) >> 1;// 如果子节点不存在，动态开点if (!ls) ls = tree[rt].ls = ++tot, newnode(tree[rt].ls, tree[rt].l, mid);if (!rs) rs = tree[rt].rs = ++tot, newnode(tree[rt].rs, mid + 1, tree[rt].r);// 合并最长区间tree[rt].all = max({tree[ls].all, tree[rs].all, tree[ls].re + tree[rs].le});// 修复 Bug 1：只有左侧完全空闲，父节点的 le 才能向右侧延伸tree[rt].le = tree[ls].le;if (tree[ls].le == tree[ls].r - tree[ls].l + 1) tree[rt].le += tree[rs].le;// 只有右侧完全空闲，父节点的 re 才能向左侧延伸tree[rt].re = tree[rs].re;if (tree[rs].re == tree[rs].r - tree[rs].l + 1) tree[rt].re += tree[ls].re;// 合并空闲个数tree[rt].siz = tree[ls].siz + tree[rs].siz;
}void update(int &rt, int l, int r, int x, int v) {if (!rt) rt = ++tot, newnode(rt, l, r);if (l == r) {tree[rt].all = tree[rt].le = tree[rt].re = tree[rt].siz = v;return;}int mid = (l + r) >> 1;if (x <= mid) update(tree[rt].ls, l, mid, x, v);else update(tree[rt].rs, mid + 1, r, x, v);pushup(rt);
}// 修复 Bug 2：寻找最长空闲区间，优先查右树 -> 跨界 -> 左树（遵循最靠右原则）
pair<int, int> query1(int rt, int maxlen) {// 尚未下放过的节点意味着整个区间都是完全空闲的，直接返回当前边界if (!tree[rt].ls) { int l = tree[rt].l, r = tree[rt].r, mid = (l + r) >> 1;newnode((tree[rt].ls = ++tot), l, mid);newnode((tree[rt].rs = ++tot), mid + 1, r);return {l, r};}// 1. 优先查右半边（最靠右的同长区间）if (tree[tree[rt].rs].all == maxlen) return query1(tree[rt].rs, maxlen);// 2. 其次查跨越中心的拼接区间if (tree[tree[rt].ls].re + tree[tree[rt].rs].le == maxlen) {int la = tree[tree[rt].ls].r - tree[tree[rt].ls].re + 1;int ra = tree[tree[rt].rs].l + tree[tree[rt].rs].le - 1;return { la, ra };  }// 3. 最后查左半边return query1(tree[rt].ls, maxlen);
}// 计算区间内空闲插排数
int query2(int &rt, int l, int r, int x, int y) {if (!rt) rt = ++tot, newnode(rt, l, r);if (tree[rt].l > y || tree[rt].r < x) return 0;if (x <= tree[rt].l && tree[rt].r <= y) return tree[rt].siz;int mid = (tree[rt].l + tree[rt].r) >> 1, ans = 0;// 修复 Bug 4：用查询范围 [x, y] 去决定下落方向，避免无关节点爆栈if (x <= mid) ans += query2(tree[rt].ls, l, mid, x, y);if (y > mid)  ans += query2(tree[rt].rs, mid + 1, r, x, y);return ans;
}int main() {// 优化输入输出流ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> q;newnode((root = 1), 1, n);for (int i = 1, id, l, r; i <= q; i++) {cin >> id;if (!id) {cin >> l >> r;// query2 取的是“空闲”，要求的答案是“已被使用”，两者相减cout << (r - l + 1) - query2(root, 1, n, l, r) << "\n";} else {if (cnt[id]) {// 离开：标记位置释放为空闲（1）update(root, 1, n, cnt[id], 1);cnt[id] = 0;} else {// 进入：寻找最长空闲段auto p = query1(root, tree[root].all);// 修复 Bug 3：不论区间长度是奇数还是偶数，此行都能定位到居中并靠右的位置cnt[id] = (p.first + p.second + 1) >> 1;// 标记该位置已被占据（0）update(root, 1, n, cnt[id], 0);}}}return 0;
}

P5234 [JSOI2012] 越狱老虎桥

题目大意：

给定一张图，\(A\) 先添加一条边，\(B\) 再删去一条边使得图不连通，\(A\) 要最大化删除边的权值，\(B\) 要最小化删除边的权值，问最终的权值是多少。

数据范围：\(n \le 5 \times 10^5, m \le 10^6\)。

显然，边双中的边是肯定不能删的，因为删除了也并不会使图不连通。所以我们有个自然的想法，我们可以把边双缩点，在重新建图，这样我们就简化为了树上问题。

由于敌人很聪明，他为了让我们需要出动的特工最多，一定会优先把代价最小的那些桥变成环，逼我们去切代价大的桥。

既然敌人会优先覆盖代价小的边，我们可以按照桥的代价从小到大排序，设为 \(e_1, e_2, e_3, \dots, e_m\)。

假设我们当前遍历到了第 \(k\) 条边，我们要判断前 \(k\) 条边能否构成一条链，如果构成就说明敌人只要在首尾加上新边就无敌了。反之如果不构成说明删掉 \(e_k\) 敌人就成小丑了。

也就是说我们要判断前 \(k\) 条边是否构成一条链。

方法很多：

• 二分 \(k\) + 暴力判链，时间复杂度为 \(O(n\log n)\)
• 依次遍历所有边，若前 \(k\) 条边所经过的结点最多只有一个结点拥有两个儿子，其余结点只拥有一个儿子，则这些边构成链，可以暴力跳、可以倍增跳，随便写，时间复杂度 \(O(n\log n)\)
• 对前 \(k\) 条边设为 \(1\)，其余设为 \(0\)，然后用这个边权求一遍树的直径，只需要检查直径长度是否等于 \(k\) 即可

#include <bits/stdc++.h>
using namespace std;const int N = 5e5 + 10;
const int M = 2e6 + 10;int n, m;
int head[N], to[M], nxt[M], weight[M], edge_cnt = 0;void add_edge(int u, int v, int w) {to[edge_cnt] = v;weight[edge_cnt] = w;nxt[edge_cnt] = head[u];head[u] = edge_cnt++;
}int dfn[N], low[N], tim, top;
int bri[M], dcc[N], cnt, stk[N];void tarjan(int x, int ine) {dfn[x] = low[x] = ++tim;stk[++top] = x;for (int i = head[x]; i != -1; i = nxt[i]) {int v = to[i];if (!dfn[v]) {tarjan(v, i);low[x] = min(low[x], low[v]);if (low[v] > dfn[x])bri[i] = bri[i ^ 1] = 1;} else if (i != (ine ^ 1)) {low[x] = min(low[x], dfn[v]);}}if (dfn[x] == low[x]) {++cnt;while (true) {int y = stk[top--];dcc[y] = cnt;if (x == y) break;}}
}struct edge {int u, v, w;
} Tim[N];
int tot = 0;struct Edge {int v, w;
};
vector<Edge> linker[N]; // 缩点后构建的树int fa[N], dis[N], dep[N], son;void bfs(int root) {queue <int> q;q.push(root);dep[root] = 1, fa[root] = 0;while (!q.empty()) {int u = q.front();q.pop();for (auto i : linker[u]) {int v = i.v;if (v != fa[u]) {fa[v] = u, dep[v] = dep[u] + 1;q.push(v);}}}
}int main() {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m; memset(head, -1, sizeof(head));for (int i = 1, u, v, w; i <= m; i++) {cin >> u >> v >> w;add_edge(u, v, w);add_edge(v, u, w);}tarjan(1, -1);for (int i = 0; i < edge_cnt; i += 2) {if (bri[i]) {int u = to[i ^ 1], v = to[i], w = weight[i];linker[dcc[u]].push_back({ dcc[v], w }); linker[dcc[v]].push_back({ dcc[u], w });Tim[++tot] = { dcc[u], dcc[v], w };}}if (tot == 0) {cout << -1 << "\n";return 0;}auto work = [](const edge &x, const edge &y){ return x.w < y.w; };sort(Tim + 1, Tim + tot + 1, work);int root = Tim[1].u;bfs(root); dis[root] = Tim[1].v; for (int i = 2; i <= tot; i++) {int u = Tim[i].u, v = Tim[i].v;int k = dep[u] > dep[v] ? u : v; // 取深度较深的点// 魔法步骤：不断往上跳，将没有分配分支的祖先分配给当前路径while (!dis[fa[k]]) {dis[fa[k]] = k; k = fa[k];}// 验证当前边能否并入已有路径，不产生冲突if (fa[k] == root && son == 0 && dis[fa[k]] != k) {son = k; // 合法！根节点拥有了第二个分支}else if (dis[fa[k]] == k || (fa[k] == root && son == k)) {; // 合法！在同一条分支上，没有产生新的分叉}else {// 产生冲突！敌人无法用一条线串起所有的边，答案就是当前这条加不进去的边cout << Tim[i].w << "\n";return 0;}}// 所有桥都被串在了一条路径上，敌人只要把路径两端连起来，所有桥都失效，必败cout << -1 << "\n";return 0;
}