杂题选讲 2

DerRichter · 2026-08-19 08:31:26 · 算法·理论

杂题选讲。

另外感谢 @yuhong056 提供好题。

P9820 [ICPC 2020 Shanghai R] Mine Sweeper II

依旧先来一道绿题开开胃。

题意

给定两张 n \times m 的扫雷地图，每个格子要么是地雷要么是空地，空地上会有数字，代表其周围 8 个格子中的地雷个数。

每次修改可以将第二张地图中任意一个格子反转（即地雷变空地，空地变地雷），求一个在修改不超过一半（若总数为奇数则向下取整）的格子的条件下，使第二张地图空地上数字的总和变为第一张的总和的方案。

思路

神秘 Ad-hoc。

先抛一个结论：第一张地图原图和其反图（所有格子反转）中至少有一个是答案。

下面给出证明：

我们把地图数字总和称为代价。首先，操作次数一定是符合要求的。原因很简单，因为把第二张图变为上面说的两种答案，修改次数总和一定等于 n \times m。所以，两种修改方案必然存在一种，使得操作次数满足限制。

然后考虑修改为反图的正确性。我们考虑原图上两个相邻的点对代价产生的贡献，分类讨论（下面说的类型都指原图上的）：

• 若两点均为地雷或均为空地，显然不会对答案产生影响；
• 若两点只有恰好一个为地雷，则反转后，原图空地的代价 -1，地雷原本没有答案，但是反转后他旁边多出一个地雷，所以代价 +1。这样就抵消掉了。

所以，反图的代价与正图是相等的。

P1989 【模板】无向图三元环计数

题意

给定一张有 n 个点 m 条边的无向图，求其三元环个数。

思路

我们依旧先说结论。我们可以按照如下方式给这张图定向：

对于一条边 (u, v)，

• 若 deg_u \lt deg_v，则定方向为 u \rightarrow v；

• 若 deg_u = deg_v，则方向为编号小的结点到编号大的结点。

下面给出证明。

我们先证引理：在定向后的有向无环图中，任意节点 x 的出度 outd_x \le \sqrt{2m}。证明如下：

假设节点 u 的出度为 k，即 outd_x = k。

根据定向规则，对于 u 的任意出边邻居 v \in Out_u，必有 deg_v \ge deg_u。

因为节点 u 有 k 个相邻节点，所以对于这 k 个出邻居 v，它们的无向图度数满足：

显然原无向图中所有节点的度数之和为 2m。考虑到节点 u 及其 k 个出邻居 v_1, v_2, \dots, v_k，这 k+1 个节点的度数和不能超过全图总度数 2m：

即：

因此，任意节点的出度满足 outdeg_u = O(\sqrt{m})。

根据引理，在定向后的图上，我们可以枚举点 u，直接标记 u 的邻域，然后枚举出点 v，再枚举 v 的出点 w，若 w 在 u 的邻域内，则算入答案。

P7804 [JOI Open 2021] 决算报告 / Financial Report

题意

给定长度为 N 的序列 A，要求在 A 中选出若干下标，使得相邻下标的距离不超过给定值 D，并且使得这些下标对应的元素构成的最长严格上升子序列最长，只需求出其 LIS 长度即可。

思路

首先，可以想到一个朴素的 N ^ 2 dp。设状态为 dp_i 表示以 i 结尾且 A_i 是选出的子序列中的前缀最大值时，子序列的最长长度。如何转移？我们设从 dp_j 转移到当前的 dp_i。我们发现，并不一定需要满足 i - j \le D 的要求，只需区间 (j, i) 中存在若干个 \le A_j 的元素，使得 j 可以通过这些下标来达到 i。

所以，如果考虑收集型转移，我们可以提前预处理出一个数组 ok_{i, j}(i \le j)，表示 i 是否可以通过若干个下标来到达 j。具体地，我们对于每个 i 都暴力枚举 j，同时记录一个右边界 R，表示满足 i \le k \le j 且 A_k \le A_i 的最大 k。每次判断，如果可以从 R 到达当前枚举的 j，那么 ok_{i, j} 就为真，否则为假。转移时枚举 j \lt i，判断是否可达即可。

但是这样不好优化。于是需要想别的做法。我们考虑先规避掉 A 值的问题。先对 A 按照值从小到大排序，相等的值按原数组中的下标从大到小排序。为什么呢？后面再说。

注意到，如果有一个集合，其中相邻的任意两个下标都满足差不大于 D，此时要转移到一个新下标 i，满足 i 大于集合中最大下标且与其相差不超过 D，那么这个集合中所有下标的 dp 值都可以作为 dp_i 的转移方案。

于是我们考虑使用并查集来存储集合。再开一个 set 来存储当前已经处理完的下标（这里指原下标），用于快速找到当前点 i 左边且离当前下标最近的下标 j。如果 j 满足要求，那么 i 可以加入 j 的集合，此时更新 dp_i 为这个集合的答案的最大值。此时前面提到的排序规则的作用就体现出来了：值相同时按照 ID 从大到小排序，意味着值相同时，ID 更大的元素会出现在前面，寻找 j 时就会发现，更大下标的元素不在 i 的左边，从而规避了 ID 较小的元素错误地从 ID 较大的元素转移过来。如何求解最大值？我们每次合并的时候，将大的下标合并到小的去，这样可以保证每次 find 时可以找到最左端点 L。找到后，直接查询 [L, j] 的区间最大值即可。为什么查询 [L, j] 呢？显然这个集合的所有下标在 set 中是连续的，所以这个区间内只有这个集合的答案，其他都为非法值。初始需要将没有处理的答案赋上 - \infty。注意此时还需要将 set 中最小的大于 i 的下标 k 并入集合，如果 k - i \le D 的话。

P8078 [WC2022] 秃子酋长

题意

给定一个排列 A，每次查询：把区间 [l, r] 排序后，相邻两个数在原序列内位置差之和。

思路

回滚莫队。

你会发现这题线段树比较难实现，区间合并很难，但是又考虑到这题时限较宽（5s），可以过 O(n \sqrt n) 做法，所以考虑莫队。

若我们考虑普通莫队，可以对每个数存它的的出现位置，再开一个链表维护所有位置的有序列表，每次扩展区间的时候，就可以在链表中找到当前数的前驱后继，贡献容易算出。这样是 O(n \sqrt n \log n) 的。稍微算一算，炸了。

但是我们注意到，因为我们对每个数分别存了出现位置，所以，在不考虑 set 的情况下，我们的删除操作可以做到 O(1)。于是可以想到只删除不增加的回滚莫队，时间复杂度 O(n \sqrt n)。

本题卡常。

[ABC405G] Range Shuffle Query

题意

给定长为 N 的序列 A，Q 次询问，每次询问 (l, r, x)，表示子段 A_l, A_{l + 1}, \dots, A_r 中，去掉 \ge x 的元素后，将剩下的子段中的元素重排，能够得到的不同序列数量。

思路

首先，答案可以表示为

于是，问题转化为求区间内小于等于给定值的出现个数。

但是，如果直接莫队+树状数组动态维护的话，时间复杂度是 O(n \sqrt n \log_2 n) 的，炸了。于是我们需要换一种思路。

注意到，时间复杂度的瓶颈在于，每次扩展/收缩区间都需要 \log_2n 的时间，而总共有 n \sqrt n 次端点移动。但是查询总共只有 n 次，所以我们可以换一种修改很快，查询可以稍慢一点的数据结构。

能够想到值域分块。修改时只需修改当前点和块内的总和/积，查询时枚举完整块的和/积再并上非完整块部分的即可。

此时，我们修改的时间复杂度来到了 O(1)，而查询是 O(\sqrt n)，但总时间复杂度降了下来，O(n \sqrt n)，这也是一种平衡吧。

[ABC259Ex] Yet Another Path Counting

题意

给定 n \times n 的矩阵 A_{i, j}，求：满足起点和终点的数相等的不同的路径数量。

思路

显然，对于任意两个点 (x_1, y_1), (x_2, y_2)，我们可以 O(1) 地求出答案：\text C _ {|x_1 - x_2|} ^ {|x_1 - x_2| + |y_1 - y_2|}。若点集大小为 S，则这个做法是 O(S ^ 2) 的。

我们还有一个做法：确定一个起点，然后 O(n ^ 2) dp。

但是，如果我们直接枚举颜色，对所有的颜色都用同一种方法暴力求的话，是 O(n ^ 4) 的，TLE。

考虑根号分治。对于点集大小 \le B 的颜色，易知其最多有 B 个，用第一种求法，时间复杂度 O(B \times S ^ 2) \le O(n ^ 2 B)。

对于点集大小 \gt B 的颜色，这时候显然就不能直接 O(S ^ 2) 做了，此时 O(n ^ 2) 的 dp 更优。下面证明这部分的时间复杂度。

设点集大小大于 B 的颜色共有 C 种，则所有满足条件的点集大小之和 \sum \limits _ {S_i \gt B} S_i \gt C \times B，又总共只有 n ^ 2 个点，所以 \sum \limits _ {S_i \gt B} S_i \le n ^ 2，结合上面两式，得 C \lt \frac {n ^ 2} B，则这部分的时间复杂度为 O(n ^ 2 C) \lt O(\frac {n ^ 4} B)。

综上，总时间复杂度为 O(n ^ 2 B + \frac {n ^ 4} B)，由均值不等式知，n ^ 2 B + \frac {n ^ 4} B \ge 2n ^ 3，在 B = n 时等号成立。证毕。

所以，将 n 作为阈值，根号分治即可。

P6880 [JOI 2020 Final] 奥运公交 / Olympic Bus

题意

给定一个含有 N 个点，M 条边的有向图，点的编号从 1 到 N。每条边从 U_i 指向 V_i，经过这条边的代价为 C_i。图中可能存在重边。

在最开始时，我们可以翻转至多一条边，即让这条边从 U_i\to V_i 永久变为 V_i\to U_i，并产生 D_i 的代价。

你要从点 1 到点 N，再从点 N 回到点 1，你想知道，通过翻转至多一条边，能得到的最小代价和为多少？

数据范围：

思路

容易看出，答案 = \min\Big(dist(1\to N)+dist(N\to 1),\ \min_i\big[D_i+dist'_i(1\to N)+dist'_i(N\to 1)\big]\Big)，其中 dist'_i 表示把第 i 条边反转后的最短路。

如果对每条边都反转、重新跑两遍 Dijkstra，时间复杂度是 O(N^2M) 的，这显然是 TLE 的。所以需要避免对很多边重新跑最短路。

首先，我们对于每一个点 x，求出 1 \to x, N \to x, x \to 1, x \to N 的最短路，这个可以通过建反图得到。

然后，对于一条边，分类讨论：

若这条边在某一条最短路径（1 \to N 或 N \to 1）上，那么如果翻转这条边，可能破坏原来的最短路，需要重新计算。但是显然不能跑堆优化 Dijkstra。因为这图是稠密图，M = N ^ 2，这种情况下 O(N ^ 2) 的朴素 Dijikstra 会比堆优化更快。由于最短路径上的边数是 O(N) 的，所以这部分时间复杂度为 O(N ^ 3)；

若这条边不在任何一条最短路径上，那么翻转这条边不会使答案变大。我们设当前边为 (u, v, w)，此时答案为：

但是这样会有一个问题：如果 1 \to v 的最短路径恰好包含当前边 (u, v, w)，那么 dist(1 \to v) 不就是错的了吗？事实上，这不会影响答案。下面我们来讨论这个问题。

假设 1 \to v 最短路的最后一条边确为 (u, v, w)，即 dist(1, v) = dist(1, u) + w代入入上式：

你会发现这个答案一定不比最初的最短路优。所以这并不会影响答案。

综上，对于在最短路上的边，重新跑 N ^ 2 Dijkstra；对于不在最短路上的边，直接把初始最短路和翻转后经过这条边的答案取 \min 即可。

这里放一份代码，主要是这题太恶心了。

:::info[参考代码]

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;

const int MAXN = 2e2 + 10, MAXM = 5e4 + 10;
const ll INF = 1e18;

struct SEdge {
  ll u, v, w, d;
} E[MAXM];

struct Edge {
  ll w, id;
  bool operator<(const Edge &oth) const {
    return w < oth.w;
  }
  bool operator<=(const Edge &oth) const {
    return w <= oth.w;
  }
} g[2][MAXN][MAXN][2];

ll n, m, dis[2][2][MAXN], tdis[2][MAXN], pre[MAXN];
bool vis[MAXN], flag[2][MAXM];

void chkmin(Edge arr[2], Edge w) {
  if (w <= arr[0]) {
    arr[1] = arr[0], arr[0] = w;
  } else if (w < arr[1]) arr[1] = w;
}

void addedge(int u, int v, Edge w) {
  chkmin(g[0][u][v], w);
  chkmin(g[1][v][u], w);
}

int findu(bool graph, bool nor1) {
  int u = 0;
  for (int i = 1; i <= n; i++) {
    if (!vis[i] && dis[nor1][graph][i] < dis[nor1][graph][u]) {
      u = i;
    }
  }
  return u;
}

int tfindu(bool nor1) {
  int u = 0;
  for (int i = 1; i <= n; i++) {
    if (!vis[i] && tdis[nor1][i] < tdis[nor1][u]) {
      u = i;
    }
  }
  return u;
}

void getpath(int s, bool nor1) {
  if (!pre[s]) return;
  flag[nor1][pre[s]] = 1;
  getpath(E[pre[s]].u, nor1);
}

void dij(int s, bool graph, bool nor1) {
  fill(dis[nor1][graph], dis[nor1][graph] + n + 1, INF);
  fill(vis, vis + n + 1, 0), fill(pre + 1, pre + n + 1, 0);
  dis[nor1][graph][s] = 0;
  for (int i = 1; i <= n; i++) {
    int u = findu(graph, nor1);
    vis[u] = 1;
    for (int v = 1; v <= n; v++) {
      if (dis[nor1][graph][v] > dis[nor1][graph][u] + g[graph][u][v][0].w) {
        dis[nor1][graph][v] = dis[nor1][graph][u] + g[graph][u][v][0].w, pre[v] = g[graph][u][v][0].id;
      }
    }
  }
  if (!graph) getpath(n + 1 - s, nor1);
}

void dij(int s, bool nor1) {
  fill(tdis[nor1], tdis[nor1] + n + 1, INF);
  fill(vis + 1, vis + n + 1, 0);
  tdis[nor1][s] = 0;
  for (int i = 1; i <= n; i++) {
    int u = tfindu(nor1);
    vis[u] = 1;
    for (int v = 1; v <= n; v++) {
      tdis[nor1][v] = min(tdis[nor1][v], tdis[nor1][u] + g[0][u][v][0].w);
    }
  }
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int _ : {0, 1}) {
    for (int __ : {0, 1}) {
      for (int u = 1; u <= n; u++) {
        for (int v = 1; v <= n; v++) {
          g[_][u][v][__].w = INF;
        }
      }
    }
  }
  for (int i = 1; i <= m; i++) {
    auto &[u, v, w, d] = E[i];
    cin >> u >> v >> w >> d;
    addedge(u, v, {w, i});
  }
  dij(1, 0, 0), dij(n, 0, 1), dij(1, 1, 0), dij(n, 1, 1);
  ll ans = dis[0][0][n] + dis[1][0][1];
  for (int i = 1; i <= m; i++) {
    auto &[u, v, w, d] = E[i];
    if (flag[0][i] || flag[1][i]) {
      ll duv = g[0][u][v][0].w, dvu = g[0][v][u][0].w;
      g[0][v][u][0].w = min(dvu, w);
      if (g[0][u][v][0].w == w) g[0][u][v][0].w = g[0][u][v][1].w;
      dij(1, 0), dij(n, 1);
      g[0][u][v][0].w = duv, g[0][v][u][0].w = dvu;
      ans = min(ans, d + tdis[0][n] + tdis[1][1]);
    } else {
      ans = min(ans, d + min(dis[0][0][n], dis[0][0][v] + dis[1][1][u] + w) + min(dis[1][0][1], dis[1][0][v] + dis[0][1][u] + w));
    }
  }
  cout << (ans < INF ? ans : -1);
  return 0;
}

:::

P5355 [Ynoi Easy Round 2017] 由乃的玉米田

题意

给你一个序列 a，长度为 n，有 m 次操作，每次询问一个区间是否可以选出两个数它们的差为 x，或者询问一个区间是否可以选出两个数它们的和为 x，或者询问一个区间是否可以选出两个数它们的乘积为 x ，或者询问一个区间是否可以选出两个数它们的商为 x（没有余数） ，这四个操作分别为操作 1,2,3,4。

选出的这两个数可以是同一个位置的数。

思路

我们一个一个来看。

首先，显然对于乘法，在知道区间内所有数是否出现的情况下，我们可以 O(\sqrt x) 枚举两个数，再判断是否存在。如果考虑在线，只能主席树，但是显然会挂。所以我们考虑离线，那么就是莫队模板了。这样是 O(n \sqrt n + m \sqrt V) 的。

然后，对于加减法，我们可以通过 bitset 来记录每个数是否出现，查询时只需 bitset 移位判断即可。这样是 O(\frac {N ^ 2} {32}) 的。

以上三个操作是另一个题（即双倍经验）：P3674 小清新人渣的本愿。

最后来看除法。我们设一个阈值 B。如果 x > B，我们考虑直接枚举一个数，如果能够找到另一个数使得两数作商没有余数且值为 x，答案就是 yuno 了。这个和上面所有的操作一起做莫队。

如果 x \le B，我们记录 last _ {i, k}，表示在区间 [1, i] 中，满足作商结果为 x 的二元组 (a, b) 中，a 在数组中下标的最大值，这里我们钦定 pos_a \lt pos_b。于是，只需判断是否满足 l \le last _ {r, x} 即可。

如何维护？你可能会想到预处理，但是这样空间复杂度是 O(NB) 的，128 MB 的空间使你意识到这似乎不太行依旧 Ynoi 特色。我们依然把他离线下来，对每个 x 分开存储，按照 r 从小到大排序，然后从 1 到 n 维护即可。这样可以省去大小为 n 的一维，这样空间就只有 O(B) 了。

CF1364E X-OR

题意

交互题。有一个 0 到 n - 1 的排列 p，初始时你不知道。你可以通过询问两个 1 到 n 中的下标 (i, j)，交互库会返回 p_i \mathbin{|} p_j，即 p_i 与 p_j 按位或的结果。求这个排列。