2024.10.24 模拟赛

题目：2024.10.24 题目

长方体

有 $n$ 个长方体，第 $i$ 个对角线的两个顶点为 $(x_{0}, y_{0}, z_{0})$ 和 $(x_{1}, y_{1}, z_{1})$ 。求至少被 $n - 1$ 个长方体所覆盖的整点数量。

显然若答案求的是被正好 $n$ 个长方体覆盖的整点数量很好算，对于下标为 $0$ 的我们取最大值，对于下标为 $1$ 的我们取最小值，最后最小值前去最大值，三个维度乘起来即可。

想到这一步，转换到 $n - 1$ 个长方体的求法就很简单了。我们可以枚举 $i$ ，假设 $i$ 不算入答案，那么对 $1 \sim i - 1$ 和 $i + 1 \sim n$ 的长方体我们就可以使用 $n$ 个长方形的求法，时间复杂度 $O (n^{2})$ 。不难想到答案只需要各个维度的最大值与最小值，因此可以做一下前缀最大值、前缀最小值、后缀最大值、后缀最小值，这样子时间复杂度就可以有效地降到 $O (n)$ 。上面所述的方法有很大的问题，就是对于有些点，可能去掉多个不同的长方形仍然可以算在内，因此我们考虑反向容斥。

对于这种点，它们只可能是 $n$ 个长方形都共有的部分。因此我们提前将这一部分的体积算出来，假设有 $m$ 个长方形被去掉后 $n - 1$ 个长方形仍然有共同的部分，那么答案就减去 $(m - 1) \times V$ ，其中 $V$ 是这一部分的体积。问什么要减一呢？因为凡事都不能做得太绝对，毕竟「做人留一线，日后好相见。」

#include <fstream>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e5 + 5;
 
ifstream cin("cube.in");
ofstream cout("cube.out");
 
struct Cube {
  LL x0, y0, z0, x1, y1, z1;
} a[kMaxN];
 
LL premax[kMaxN][3], premin[kMaxN][3], sufmax[kMaxN][3], sufmin[kMaxN][3], n, ans;
 
int main() {
  cin >> n;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i].x0 >> a[i].y0 >> a[i].z0 >> a[i].x1 >> a[i].y1 >> a[i].z1;
  }
  premax[0][0] = premax[0][1] = premax[0][2] = -1e18;
  premin[0][0] = premin[0][1] = premin[0][2] = 1e18;
  for (LL i = 1; i <= n; i++) {
    premax[i][0] = max(premax[i - 1][0], a[i].x0);
    premax[i][1] = max(premax[i - 1][1], a[i].y0);
    premax[i][2] = max(premax[i - 1][2], a[i].z0);
 
    premin[i][0] = min(premin[i - 1][0], a[i].x1);
    premin[i][1] = min(premin[i - 1][1], a[i].y1);
    premin[i][2] = min(premin[i - 1][2], a[i].z1);
  }
  sufmax[n + 1][0] = sufmax[n + 1][1] = sufmax[n + 1][2] = -1e18;
  sufmin[n + 1][0] = sufmin[n + 1][1] = sufmin[n + 1][2] = 1e18;
  for (LL i = n; i >= 1; i--) {
    sufmax[i][0] = max(sufmax[i + 1][0], a[i].x0);
    sufmax[i][1] = max(sufmax[i + 1][1], a[i].y0);
    sufmax[i][2] = max(sufmax[i + 1][2], a[i].z0);
 
    sufmin[i][0] = min(sufmin[i + 1][0], a[i].x1);
    sufmin[i][1] = min(sufmin[i + 1][1], a[i].y1);
    sufmin[i][2] = min(sufmin[i + 1][2], a[i].z1);
  }
  for (LL i = 1; i <= n; i++) {
    LL a1 = max(premax[i - 1][0], sufmax[i + 1][0]), a2 = min(premin[i - 1][0], sufmin[i + 1][0]);
    LL b1 = max(premax[i - 1][1], sufmax[i + 1][1]), b2 = min(premin[i - 1][1], sufmin[i + 1][1]);
    LL c1 = max(premax[i - 1][2], sufmax[i + 1][2]), c2 = min(premin[i - 1][2], sufmin[i + 1][2]);
    if (a2 == 1e18 || b2 == 1e18 || c2 == 1e18) {
      continue;
    }
    if (a1 <= a2 && b1 <= b2 && c1 <= c2) {
      ans += (a2 - a1 + 1) * (b2 - b1 + 1) * (c2 - c1 + 1);
      ans -= max(0LL, premin[n][0] - premax[n][0] + 1) *
             max(0LL, premin[n][1] - premax[n][1] + 1) *
             max(0LL, premin[n][2] - premax[n][2] + 1);
    }
  }
  cout << ans + max(0LL, premin[n][0] - premax[n][0] + 1) *
                max(0LL, premin[n][1] - premax[n][1] + 1) *
                max(0LL, premin[n][2] - premax[n][2] + 1) << '\n';
  return 0;
}

三角形

给定长度为 $n$ 的序列 $a$ ，第 $i$ 个数为 $a_{i}$ 。进行 $q$ 次询问，每次询问的格式为 $[l, r]$ ，求区间内是否能够选出三个不同的下标 $(i, j, k)$ 使得三条 $(a_{i}, a_{j}, a_{k})$ 的线段可以组成三角形。

不会写，采用暴力。首先我们可以对区间 $[l, r]$ 内的所有元素都进行一个 $O (n^{3})$ 的枚举，然后判断是否满足条件。这种枚举是最暴力最纯洁得了，总时间复杂度 $O (m n^{3})$ 。

不难想到优化，假设 $a_{i}$ 和 $a_{j}$ 是最小的那两个，并且 $a_{i} \leq a_{j}$ ，只枚举 $i$ 和 $j$ ， $k$ 肯定是选择满足 $a_{k} > a_{j}$ 的，且 $k$ 尽量小，这样子对于一个区间我们只需要花费 $O (n^{2})$ ，总时间复杂度 $O (m n^{2})$ 。

考虑继续优化。此时忽然想起小学数学老师告诉过我们的，对于一个数列，想要选择三个数的长度的线段组成三角形，只需要选择大小相邻的就行了。因此我们可以对 $[l, r]$ 内的元素排序，然后三个三个判断，这样子的总时间复杂度就降到了 $O (mn)$ 。可以获得 $60$ 分。

正解：考虑最坏的情况，无法组成三角形。由于 $a_{i} + a_{j} > a_{k}$ ，因此最坏的情况是构造类斐波那契数列的 $a_{k} = a_{i} + a_{j}$ 的序列。由于斐波那契数列在 $1 0^{18}$ 的范围之内只有不到 $100$ 个数，因此大于 $100$ 的情况就可以直接输出有解，否则采用暴力判断。

区间

给定长度为 $n$ 的序列 $a$ ，第 $i$ 个数为 $a_{i}$ ，并给定 $m$ 和 $q$ 次操作，每次操作给出 $(o, l)$ 。若 $o = 1$ ，则翻转区间 $[l, l + m - 1]$ 内的元素；如果 $o = 2$ ，则获取 $a_{l}$ 。对于所有的操作 $2$ ，求出答案的异或和。

采用暴力。对于操作一，我们直接使用两个指针 $i, j$ 通过交换来实现区间翻转；对于第二个操作直接输出 $a_{l}$ 即可。该算法的时间复杂度为 $O (m q)$ ，在对应的数据范围中理论上只能获得 $30$ 分，但是由于数据过水，此做法实际上可以获得 $60$ 分。

图

有 $n$ 个结点，第 $i$ 个结点的点权为 $a_{i}$ 。若 $a_{i} and a_{j} = 0$ （ $and$ 是按位与），则 $i$ 与 $j$ 有一条边。初始时集合 $S = \emptyset$ ，进行 $n$ 次操作，每次加入一个结点到 $S$ 。加入结点 $v$ 有两种方式：

直接加入结点 $v$ ，代价为 $0$ ；
选择另一个结点 $u \in S$ 且 $u$ 与 $v$ 之间有一条边，代价为 $a_{u}$ 。

求能够获得的最大代价。

赛时一眼想到了最大生成树，但是由于大样例挂掉红温便没有继续调试，实际上我的代码改几行就可以通过。

我提交的代码是采用状态压缩动态规划的版本。令 $d p_{i}$ 表示为当前状态为二进制 $i$ （第 $j$ 位为 $1$ 代表第 $j$ 个结点已经加入了集合，反之反之），那么我们可以枚举新加入哪一个结点，必须是 $i$ 里面没有的；再枚举和哪一个连边，找出最大值，然后转移即可。

时间复杂度为 $O (2^{n} n^{2})$ ，侥幸获得 $40$ 分。

总结

排名： $7$ ；
比赛分数： $260/400$ ；
情况：相比 2024.10.23 模拟赛，没区别；
问题：调不出题目就红温。

Haokee Note

Explorer

2024.10.24 模拟赛

长方体

三角形

区间

图

总结

Graph View

Table of Contents

Backlinks