ToB企服应用市场:ToB评测及商务社交产业平台

标题: P10996 【MX-J3-T3】Tuple 题解 [打印本页]

作者: 羊蹓狼 时间: 2024-8-26 13:36
标题: P10996 【MX-J3-T3】Tuple 题解
好久没写题解了
思绪

注意到正当的四元组 \((a, b, c, d)\) 形如：

（如果 \(u\) 有一个箭头连出到 \(v\)，则表示在输入的三元组中存在一组三元组使得 \(v\) 是 \(u\) 的后继（即形如 \((u, v, *)\) 或 \((*, u, v)\)，\(*\) 则表示我们不关心这个元素））
观察这张图，我们可以得出一些关系：

\(b\) 是 \(a\) 的后继
\(c\) 同时是 \(a\) 和 \((a, b)\) 的后继（二元组 \((u, v)\) 的后继界说为全部的 \(w\) 使得存在一组三元组 \((u, v, w)\)）
\(d\) 同时是 \((a, b)\)、 \((a, c)\) 和 \((b, c)\) 的后继

所以我们可以使用以下算法解决此题目：

罗列 \(a\)
罗列 \(a\) 作为三元组的第一个元素时的全部后继，即 \(a\) 固定时全部正当的 \(b\)（即形如 \((a, b, *)\)）
在 \(a\) 的后继与 \((a, b)\) 的后继的交中罗列，即 \((a, b)\) 固定时全部正当的 \(c\)
将 \((a, b)\) 的后继、 \((a, c)\) 的后继与 \((b, c)\) 的后继的交的巨细计入答案，即 \((a, b, c)\) 固定时全部正当的 \(d\) 的数量

实现细节与复杂度

怎样实现上述算法？我们可以使用 bool 数组来储存一个元素或一个二元组的全部后继，即如果 \(x\) 是对应元素或元组的后继，则在对应的 bool 数组的 \(x\) 下标位置赋值为 true，那么遍历后继即遍历数组里全部为 true 的下标，两个后继的交即为两个后继 bool 数组相同的下标同时为 true的全部下标，交的数量就只要数一数有多少个都为 true 的下标即可
但储存上会有一个小题目，储存全部 \(O(n^2)\) 个二元组的 \(O(n)\) 个后继时会用到 \(O(n^3)\) 空间，这是不能接受的。但是我们注意到全部的三元组最多只有 \(O(m)\) 个，那么二元组也只有 \(O(m)\) 个。我们可以只开 \(O(m)\) 个后继数组，将每个出现过的二元组用 \(1 \sim m\) 编号，并存储在对应编号的后继数组中，这样就只需要 \(O(n^2+nm)\) 空间。
还偶然间复杂度没有讨论：

罗列三元组 \((a, b, c)\) 一共需要 \(O(n^2+nm)\) 代价，因为：

罗列每个 \(a\) 再罗列 \(b\) 判断是否是后继总共需要 \(O(n^2)\) 代价，而 \((a, b)\) 最多只有 \(O(m)\) 对。
对于每个 \((a, b)\) 求出 \(a\) 后继与 \((a, b)\) 后继的交需要 \(O(n)\) 代价，在交中罗列总共需要 \(O(m)\) 代价，因为全部的三元组 \((a, b, c)\) 最多只有 \(O(m)\) 对

对于 \(O(m)\) 个三元组 \((a, b, c)\) 计算 \((a, b)\) 的后继、 \((a, c)\) 的后继与 \((b, c)\) 的后继的交的巨细需要 \(O(n)\) 时间，所以总共需要 \(O(nm)\) 代价

故此算法时间复杂度为 \(O(n^2+nm)\)
代码

赛时我使用了 bitset 代替 bool 数组，bitset 是个标准库中的容器，在 \(64\) 位操作系统大将一个 \(64\) 位整数的每一位当作一个 bool 变量，所以储存空间拥有 \(\frac{1}{8}\) 的常数，做很多常见操作，如给两个 bool 数组的相同的下标上的元素求 & 时拥有 \(\frac{1}{64}\) 的常数。为了用 \(O\) 标记表现 bitset 带来的优化，同时也为了表现操作系统位数对优化的差异，我们设 \(w\) 为操作系统位数，若使用 bitset 优化本算法，时间复杂度则为 \(O(\frac{n^2+nm}{w})\)。
我会在本题的代码的解释中解释 bitset 对应的操作的作用，若对 bitset 支持的更多操作感兴趣可以前往 OI-Wiki 学习更多用法。
[code]#include #include using namespace std;using ll = long long;constexpr int N = 2000 + 1, M = 50000 + 1;int mid[N][N];bitset um[N], uvm[M];int main() { int n, m; cin >> n >> m; int tot = 0; for (int i = 1; i > u >> v >> w; int &nid = mid[v];//(u, v) 二元组对应的编号 if (!nid) {//如果之前没有编号过 nid = ++tot;//新建编号 } um[v] = true; uvm[nid][w] = true; } ll ans = 0; for (int a = 1; a < n; ++a) { auto &uma = um[a]; for (int b = uma._Find_next(a)/*_Find_next(x)函数：找到 bitset 中 x 下标后的第一个 true 的位置*/; b

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)