Haokee Note

2025.9.11 模拟赛

9 min read

好三角形

数学 树状数组 排序

首先看到曼哈顿距离就知道不好处理，所以把整个坐标轴旋转 变成切比雪夫距离1，更方便操作。题目要求存在 满足 ，而在切比雪夫距离中，与 点距离为 的所有点会连成一个以 为中心，边长为 的正方形。

因此，问题就变成了选择一个三元组，是否存在一个正方形使得三元组中每一个点都能在正方形的边上。但是这个问题非常的复杂，并且通过样例我们可以发现不能满足的三元组数量较少，因此可以选择容斥，求不满足条件的三元组的数量。

经过长达两个多小时的开庭，我找到了三元组不满足条件的充分条件，就是其中一个点在另外两个点以对角组成的长方形内部，这样子是肯定无法满足条件的，因为内部的那个点无法搞到正方形的边上，强制搞上另外两个点就不行了。

转换成坐标来表述就是如果三元组以 递增/减排序的话， 坐标仍然也是递增/减的（二位偏序，严格），那么三元组不满足条件。所以我们能够简单地写出一个 的暴力。

#include <iostream>
#include <map>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 5e5 + 5;
 
struct Node {
  LL x, y, u, v;
} a[kMaxN];
 
LL n, ans;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (LL i = 1; i <= n; i++) {
    cin >> a[i].x >> a[i].y;
    a[i].u = a[i].x + a[i].y;
    a[i].v = a[i].x - a[i].y;
  }
  // 如果 j 在 i 和 k 作为对角组成的长方形内部，则无法构成好三角形
  for (LL i = 1; i <= n; i++) {
    for (LL j = 1; j <= n; j++) {
      if (i != j) {
        for (LL k = 1; k <= n; k++) {
          if (k != i && k != j) {
            ans += a[i].u < a[j].u && a[j].u < a[k].u && a[i].v < a[j].v && a[j].v < a[k].v;
            ans += a[i].u < a[j].u && a[j].u < a[k].u && a[i].v > a[j].v && a[j].v > a[k].v;
          }
        }
      }
    }
  }
  cout << n * (n - 1) * (n - 2) / 6 - ans << '\n';
  return 0;
}

可以发现这份代码能过大样例，只是复杂度不对。这证明我们猜测的结论正好就是三元组不满足条件的充分必要条件，那么就可以尝试优化了。

首先按照 递增排序，这样子后面的 一定大于前面的 。 的话就用树状数组维护，此时就可以很简单地写出求解二位偏序二元组的代码了。但是这里是三元的，所以我们可以先跑一遍二维的，然后在二维的答案的基础上再跑一遍得到二维偏序三元组的数量，即不满足条件的三元组数量，然后用总数减去它就行了。

注意是严格递增/减，所以 排序之后仍然要用双指针维护。时间复杂度 。

#include <iostream>
#include <algorithm>
 
using namespace std;
using LL = long long;
 
const LL kMaxN = 1e6 + 5;
 
struct Node {
  LL x, y;
} a[kMaxN];
 
LL val[kMaxN], tr[kMaxN], dp[kMaxN], n, m, ans;
 
void modify(LL x, LL y) {
  for (; x <= m; x += x & -x) {
    tr[x] += y;
  }
}
 
LL query(LL x) {
  LL res = 0;
  for (; x; x -= x & -x) {
    res += tr[x];
  }
  return res;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (LL i = 1, x, y; i <= n; i++) {
    cin >> x >> y;
    a[i].x = x + y;
    a[i].y = x - y;
    val[++m] = a[i].y;
  }
 
  sort(val + 1, val + m + 1);
  m = unique(val + 1, val + m + 1) - val - 1;
  sort(a + 1, a + n + 1, [](const Node &a, const Node &b) {
    return a.x < b.x;
  });
 
  // x 递增且 y 递增
  for (LL i = 1, j = 1; i <= n; i++) {
    a[i].y = lower_bound(val + 1, val + m + 1, a[i].y) - val;
    for (; j < n && a[j].x < a[i].x; j++) {
      modify(a[j].y, 1);
    }
    dp[i] = query(a[i].y - 1);
  }
  fill(tr + 1, tr + m + 1, 0);
  for (LL i = 1, j = 1; i <= n; i++) {
    for (; j < n && a[j].x < a[i].x; j++) {
      modify(a[j].y, dp[j]);
    }
    ans += query(a[i].y - 1);
  }
 
  // x 递增且 y 递减
  fill(tr + 1, tr + m + 1, 0);
  for (LL i = 1, j = 1; i <= n; i++) {
    for (; j < n && a[j].x < a[i].x; j++) {
      modify(a[j].y, 1);
    }
    dp[i] = query(m) - query(a[i].y);
  }
  fill(tr + 1, tr + m + 1, 0);
  for (LL i = 1, j = 1; i <= n; i++) {
    for (; j < n && a[j].x < a[i].x; j++) {
      modify(a[j].y, dp[j]);
    }
    ans += query(m) - query(a[i].y);
  }
 
  cout << n * (n - 1) * (n - 2) / 6 - ans << '\n';
  return 0;
}

树上探测

树形dp

首先预处理倍增 LCA，这样子就可以方便地计算树上距离。对于 的数据，选择 往上跳 步或者选择 往上跳 步就行了，用那个不会跳到 LCA 以上的。其余数据全部写暴力。成功获得 分。

#include <iostream>
#include <vector>
 
using namespace std;
 
const int kMaxN = 4e5 + 5, kLog = 21;
 
int dp[kMaxN][kLog], d[kMaxN], n, q;
vector<int> e[kMaxN];
 
void dfs(int x, int f) {
  d[x] = d[f] + 1;
  dp[x][0] = f;
  for (int i = 1; i < kLog; i++) {
    dp[x][i] = dp[dp[x][i - 1]][i - 1];
  }
  for (int i : e[x]) {
    if (i != f) {
      dfs(i, x);
    }
  }
}
 
int jump(int x, int k) {
  for (int i = 0; i < kLog; i++) {
    if (k & (1 << i)) {
      x = dp[x][i];
    }
  }
  return x;
}
 
int lca(int x, int y) {
  if (d[x] < d[y]) {
    swap(x, y);
  }
  x = jump(x, d[x] - d[y]);
  if (x == y) {
    return x;
  }
  for (int i = kLog - 1; i >= 0; i--) {
    if (dp[x][i] != dp[y][i]) {
      x = dp[x][i];
      y = dp[y][i];
    }
  }
  return dp[x][0];
}
 
int dis(int x, int y) {
  return d[x] + d[y] - 2 * d[lca(x, y)];
}
 
int main() {
  // freopen("main.in", "r", stdin);
  // freopen("main.out", "w", stdout);
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> q;
  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs(1, 0);
  int x, dx, y, dy;
  for (; q; q--) {
    cin >> x >> dx >> y >> dy;
    int l = lca(x, y);
    if (d[x] + d[y] - 2 * d[l] == dx + dy) {
      if (d[x] < d[y]) {
        swap(x, y);
        swap(dx, dy);
      }
      if (dx <= d[x] - d[l]) {
        cout << jump(x, dx) << '\n';
      } else {
        cout << jump(y, dy) << '\n';
      }
    } else {
      bool b = 0;
      for (int i = 1; i <= n; i++) {
        if (dis(i, x) == dx && dis(i, y) == dy) {
          cout << i << '\n';
          b = 1;
          break;
        }
      }
      if (!b) {
        cout << "-1\n";
      }
    }
  }
  return 0;
}

按位覆盖

二分 前缀和

暴力都不会， 分。

最小权值

树形dp 背包dp

采取的纯暴力，DFS 套 DFS，成功获得 分。

总结

总分 。

全场精力基本上全部都在想 T1，虽然最后想出来了但是另外几题啥都没过脑，代码源该降低难度了。不过感谢 PTY 老铁之前 ABC 教我们曼哈顿转切比雪夫，让我成功守住了 T1 的 AC。T2 应该也是我可以做的，等会想一想。后面两题太超标了。

Footnotes

  1. 和 之间的切比雪夫距离为 ，即斜着走需要的最小步数。 ↩

Graph View

Backlinks