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

ABC396题解

news 来源：原创 2025/8/10 2:45:03

A

算法标签: 模拟

问题陈述

给你一个长度为 $N$ 的整数序列： $(A_1, A_2, \ldots, A_N)$ 。
请判断在 $A$ 中是否有相同元素连续出现三次或三次以上的位置。
更正式地说，请判断是否存在一个整数 $i$ 与 $\le i \le N-2$ 中的 $A_i = A_{i+1} = A_{i+2}$ 。

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 110;int n, w[N];int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 0; i < n; ++i) cin >> w[i];int i = 0, j = 2;while (j < n) {if (w[i] == w[j] && w[i] == w[i + 1]) {cout << "Yes" << "\n";return 0;}i++, j++;}cout << "No" << "\n";return 0;
}

B

算法标签: 栈, 模拟

问题陈述

有一叠 $100$ 纸牌，每张都标有整数 $0$ 。

处理 $Q$ 个查询。每个查询都属于以下情况之一：

输入 $1$ ：将一张标有整数 $x$ 的卡片放在堆栈顶部。
类型 $2$ ：取出堆栈顶端的卡片，并输出写在该卡片上的整数。在此问题的限制条件下，牌堆中总是至少有一张牌。

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 210;int n;
int stack[N], top;int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);top = 99;cin >> n;while (n--) {int op, val;cin >> op;if (op == 1) {cin >> val;stack[++top] = val;}else cout << stack[top--] << "\n";}return 0;
}

C

算法标签: 前缀和, 贪心

问题陈述

有 $N$ 个黑球和 $M$ 个白球。
每个球都有一个值。第 $i$ 个黑球( $\le i \le N$ )的值是 $B_i$ ，第 $j$ 个白球( $\le j \le M$ )的值是 $W_j$ 。

选择零个或更多的球，使得所选黑球的数量至少等于所选白球的数量。在所有这样的选择中，求所选球的数值之和的最大值。

思路

很容易想到时间复杂度 $O(n ^ 2)$ 的做法, 但是球的数量 $10 ^ 5$ 级别, 会超时, 因此需要优化到 $O(n ^ 2)$ 以下

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef long long LL;
const int N = 2e5 + 10;int n, m;
int b[N], w[N], gre;
LL s1[N], s2[N];int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; ++i) cin >> b[i];for (int i = 1; i <= m; ++i) cin >> w[i];sort(b + 1, b + n + 1);reverse(b + 1, b + n + 1);sort(w + 1, w + m + 1);reverse(w + 1, w + m + 1);for (int i = 1; i <= n; ++i) {if (b[i] > 0) gre = i;s1[i] = (LL) s1[i - 1] + b[i];}for (int i = 1; i <= m; ++i) s2[i] = (LL) s2[i - 1] + w[i];LL res = 0;// 枚举选择白球的数量for (int k = 0; k <= min(n, m); ++k) {int cnt = max(k, gre);res = max(res, s2[k] + s1[cnt]);}cout << res << "\n";return 0;
}

D

算法标签: $df s$

问题陈述

给你一个简单相连的无向图，图中有 $N$ 个顶点，编号为 $1$ 到 $N$ ，有 $M$ 条边，编号为 $1$ 到 $M$ 。边 $i$ 连接顶点 $u_i$ 和 $v_i$ ，其标签为 $w_i$ 。

在从顶点 $1$ 到顶点 $N$ 的所有简单路径（不经过同一顶点多次的路径）中，求路径上边的标签的最小 XOR。

关于 XOR 的说明

对于非负整数 $A$ 和 $B$ ，它们的 XOR $\oplus B$ 定义如下：

在 $\oplus B$ 的二进制表示中，当且仅当 $A$ 和 $B$ 的相同数位中恰好有一位是 $1$ 时， $2^k \ (k \ge 0)$ 对应数位上的数字是 $1$ ；否则，它是 $0$ 。

例如， $\oplus 5 = 6$ （二进制为： $011 \oplus 101 = 110$ ）。

一般来说， $k$ 个整数 $p_1, \dots, p_k$ 的 XOR 定义为 $(\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k)$ 。可以证明它与 $p_1, \dots, p_k$ 的顺序无关。

思路

注意到, 点的数量不大于 $10$ , 直接暴搜

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef long long LL;
const int N = 12, M = N * N;int n, m;
int head[N], edge_end[M], next_edge[M], edge_index;
LL w[M];
bool vis[N];
LL res = 9e18;void add(int ver1, int ver2, LL val) {edge_end[edge_index] = ver2, next_edge[edge_index] = head[ver1], w[edge_index] = val, head[ver1] = edge_index++;
}void dfs(int u, LL curr) {if (u == n) {res = min(res, curr);return;}for (int i = head[u]; ~i; i = next_edge[i]) {int ver = edge_end[i];if (!vis[ver]) {vis[ver] = true;dfs(ver, curr ^ w[i]);vis[ver] = false;}}
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);memset(head, -1, sizeof head);cin >> n >> m;while (m--) {int u, v;LL val;cin >> u >> v >> val;add(u, v, val);add(v, u, val);}vis[1] = true;dfs(1, 0);cout << res << "\n";return 0;
}

E

算法标签: 贪心, $df s$

问题陈述

给你整数 $N, M$ 和长度为 $M$ 的三个整数序列： $(X_1, X_2, \ldots, X_M)$ 、 $(Y_1, Y_2, \ldots, Y_M)$ 和 $(Z_1, Z_2, \ldots, Z_M)$ 。保证 $X$ 和 $Y$ 中的所有元素都在 $1$ 和 $N$ 之间。
我们称长度为 $N$ 的非负整数序列 $(A_1, A_2, \ldots, A_N)$ 为好序列，当且仅当它满足以下条件时：

对于每一个有 $\le i \le M$ 的整数 $i$ ， $A_{X_i}$ 与 $A_{Y_i}$ 的 XOR 为 $Z_i$ 。
判断是否存在一个好序列 $A=(A_1,A_2,\ldots,A_N)$ ，如果存在，找出一个使其元素之和 $\displaystyle \sum_{i=1}^N A_i$ 最小的好序列。

关于 XOR 的说明

对于非负整数 $A$ 和 $B$ ，它们的 XOR $\oplus B$ 定义如下：

在 $\oplus B$ 的二进制表示中，当且仅当 $A$ 和 $B$ 的相同数位中恰好有一位是 $1$ 时， $2^k \ (k \ge 0)$ 对应数位上的数字是 $1$ ；否则，它是 $0$ 。
例如， $\oplus 5 = 6$ （二进制为： $011 \oplus 101 = 110$ ）。

思路

由题意, 分为两步

是否存在该序列?
如何最小化 $A_i$

首先判断是否无解

$A_{X_i} \oplus A_{Y_i} = Z_i$ , 对于异或操作有以下性质
$\oplus b = c, a \oplus c = b, b \oplus c = a$ , 异或是可逆的

因为 $X_i,Y_i, Z_i$ 是确定的, $A_{X_i}$ 和 $A_{Y_i}$ 只要确定一个数, 就可以确定另外一个数

在这里插入图片描述
会形成如图的连通块, 在连通块中知道确定一个数, 整个连通块的数都会被确定
如果从 $u$ 到 $v$ 出现了两条不一样的路径, 出现矛盾

如何找这些环的边?
在这里插入图片描述
维护并查集, 检查 $S_{path_1} \oplus S_{path_2}$ , 如果不相等无解

如何维护最小值?

在连通块中确定任何一个元素就能确定任意一个元素, 考虑树的根节点

因为异或操作是逐位异或的, 因此位与位之间是独立的, 每一位单独考虑, 因为要求和最小, 因此要求 $1$ 的数量是最小的

算法流程

将图构建成生成树, 检查非树边
求最小值, 逐位考虑, 看根节点是选 $0$ 还是选 $1$ , 最后知道了根节点的值, 然后整个树的值就知道了

XOR 的性质

XOR 操作具有以下性质：

自反性：
$\oplus A = 0$
结合律：
$\oplus B) \oplus C = A \oplus (B \oplus C)$
交换律：
$\oplus B = B \oplus A$

由于这些性质，调整根节点的值 $A [roo t]$ 为 $\oplus off$ 会使得所有顶点的值 $A [x]$ 变为 $\oplus off$ 。

一致性调整

假设根节点的值被调整为 $\oplus off$ ，那么对于任意顶点 $x$ ，其值 $A [x]$ 会被调整为：

$path_xor ) ⊕ o f f = ( A [ r o o t ] ⊕ o f f ) ⊕ path_xor A[x] \oplus off = (A[root] \oplus \text{path\_xor}) \oplus off = (A[root] \oplus off) \oplus \text{path\_xor}$

其中， $path_xor \text{path\_xor}$ 是从根节点到顶点 $x$ 的路径上所有边的 XOR 值
这种调整方式确保了所有顶点的值仍然满足边的 XOR 条件

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;typedef long long LL;
const int N = 2e5 + 10, M = 2e5 + 10;int n, m;
int head[N], edge_end[M], next_edge[M], w[M], edge_index;
int res[N];void add(int ver1, int ver2, LL val) {edge_end[edge_index] = ver2, next_edge[edge_index] = head[ver1], w[edge_index] = val, head[ver1] = edge_index++;
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);memset(head, -1, sizeof head);cin >> n >> m;for (int i = 0; i < m; ++i) {int u, v, w;cin >> u >> v >> w;u--, v--;add(u, v, w);add(v, u, w);}memset(res, -1, sizeof res);for (int x = 0; x < n; ++x) {if (res[x] != -1) continue;vector<int> q;q.push_back(x);res[x] = 0;int cnt[30]{0};for (int i = 0; i < q.size(); ++i) {int u = q[i];for (int j = 0; j < 30; ++j) cnt[j] += res[u] >> j & 1;for (int j = head[u]; ~j; j = next_edge[j]) {int ver = edge_end[j];if (res[ver] == -1) {res[ver] = res[u] ^ w[j];q.push_back(ver);}else if (res[ver] != (res[u] ^ w[j])) {cout << -1 << "\n";return 0;}}}int off = 0;for (int j = 0; j < 30; ++j) {if (cnt[j] > q.size() - cnt[j]) {off ^= 1 << j;}}for (int ver : q) res[ver] ^= off;}for (int i = 0; i < n; ++i) cout << res[i] << " ";cout << "\n";return 0;
}

F

算法标签: 分治, 树状数组, $F e n w i c k - T ree$

问题陈述

给你一个整数 $N, M$ 和一个长度为 $N$ 的非负整数序列 $(A_1, A_2, \ldots, A_N)$ 。

就 $\ldots, M-1$ 求解下面的问题：

定义一个整数序列 $(B_1, B_2, \ldots, B_N)$ ，使 $B_i$ 除以 $M$ 后的余数是 $A_i + k$ 。求 $B$ 中的倒数。

什么是倒数？
序列 $(A_1, A_2, \dots, A_N)$ 的反转数是满足 $\le i < j \le N$ 和 $A_i > A_j$ 的整数对 $(i, j)$ 的个数。

思路

$B_i = (A_i + k) \mod M$ . 求 $B$ 的逆序对数量, 首先考虑简单情况, 如果没有 $\mod M$ , 输出就是原 $A_i$ 的逆序对数量

考虑简单情况, $B_i = A_i + 1$ , 哪些逆序对数量发生改变?
$B_i= M - 1$ 的那些数如果加 $1$ , $\mod M$ 变为 $0$ , 逆序对数量发生变化, 而对于 $\le B_i \le M - 2$ 的数字, 加上 $1$ 再对 $M$ 取模逆序对数量不会发生变化

因此考虑 $B_i = M - 1$ 的情况
在这里插入图片描述
会与每一个后面的非 $M - 1$ 的位置形成逆序对, 因为在 $\mod M$ 情况下, $M - 1$ 就是最大值

逆序对的变化量 $\Delta cnt = -[M - 1] + [0]$ , 也就是减去变化前 $M - 1$ 位置的逆序对数量, 加上变为 $0$ 后与前面形成的逆序对数量
假设当前位置是 $p$ , 减去的逆序对数量等于 $n - p - cnt_{M - 1}$

因为每个数加 $1$ , 因此变为 $0$ 后前面与前面形成的逆序对数量等于 $p - 1$
以上是 $k = 1$ 的逆序对数量, 以此类推计算到到 $k = M - 1$ , 也就是 $\mod M$ 的最大余数

第 $i$ 个数什么时候变成 $M$ ?
在 $M - A_i$ 时刻 $\mod M$ 变为 $0$ , 算法时间复杂度 $O(n\log n)$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;typedef long long LL;
const int N = 2e5 + 10;int n, m;
int w[N], tr[N];
vector<int> change[N];int lowbit(int val) {return val & -val;
}void add(int u, int val){for (int i = u; i <= m; i += lowbit(i)) tr[i] += val;
}int query(int u) {int res = 0;for (int i = u; i; i -= lowbit(i)) res += tr[i];return res;
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;LL res = 0;for (int i = 1; i <= n; ++i) {cin >> w[i];change[m - w[i]].push_back(i);res += query(m - w[i] - 1);add(m - w[i], 1);}cout << res << "\n";for (int k = 1; k < m; ++k) {// 枚举在k时刻从m - 1变为0的所有位置for (int j = 0, sz = change[k].size(); j < sz; ++j) {int p = change[k][j];res -= n - p - (sz - j - 1);res += p - 1 - j;}cout << res << "\n";}return 0;
}

G

算法标签:

问题陈述

有一个 $\times W$ 网格，每个单元格都包含 $0$ 或 $1$ 。从顶部起第 $i$ 行和从左侧起第 $j$ 列的单元格中包含一个整数 $A_{i,j}$ 。

您可以按照任意顺序执行以下两种操作任意多次：

操作 X：选择一个整数 $x$ （ $\leq x \leq H$ ）。对于每一个整数 $\leq y \leq W$ ，将 $A_{x,y}$ 替换为 $1 - A_{x,y}$ 。
操作 Y：选择一个整数 $y$ （ $\leq y \leq W$ ）。对于每一个整数 $\leq x \leq H$ ，将 $A_{x,y}$ 替换为 $1 - A_{x,y}$ 。

求替换后 $\displaystyle \sum_{x=1}^H \sum_{y=1}^W A_{x,y}$ 的最小值。

A

算法标签: 模拟

问题陈述

B

算法标签: 栈, 模拟

问题陈述

C

算法标签: 前缀和, 贪心

问题陈述

思路

D

算法标签: d f s dfs dfs

问题陈述

关于 XOR 的说明

思路

E

算法标签: 贪心, d f s dfs dfs

问题陈述

关于 XOR 的说明

思路

首先判断是否无解

如何维护最小值?

算法流程

XOR 的性质

一致性调整

F

算法标签: 分治, 树状数组, F e n w i c k − T r e e Fenwick-Tree Fenwick−Tree

问题陈述

思路

G

算法标签:

问题陈述

思路

相关文章：

算法标签: $df s$

算法标签: 贪心, $df s$

算法标签: 分治, 树状数组, $F e n w i c k - T ree$