2019-08-19 12:34 已编辑福建师范大学附属中学

关注

【题解】牛客NOIP暑期七天营-提高组1

T1: 最短路

对于第一档部分分，构造一朵菊花，直接从 $1$ 向其他节点连对应权值的边即可。期望得分 $30$ 分。

对于第二档部分分，我们希望每一个点都从最近的那个点连过来。也就是说，对于某个点 $i$ ，我们可以找到一个 $j$ ，满足 $a_j < a_i$ 并且 $a_j$ 尽可能大，然后从 $j$ 向 $i$ 连一条权值为 $a_i - a_j$ 的边。可以证明这样构造出的图一定是最优的（最大边边权最小的），因此若找不到点 $j$ （即 $a_i = 0\ (i \not = 1)$ ）或 $a_i - a_j > s$ ，则一定无解。暴力找前驱 $j$ 可以做到 $\mathcal{O}(n^2)$ 的复杂度。结合上一档部分分可以拿到 $60$ 分。

对于所有数据，可以优化这个找点的过程。我们不妨将所有节点按照权值先排序，然后我们发现，随着 $i$ 的增大，点 $j$ 一定不会减小，因此用双指针扫描法即可找到这个 $j$ 。当然用二分查找也是可以的。复杂度 $\mathcal{O}(n \log n)$ ，期望得分 $100$ 分。

#include <algorithm>
#include <cstdio>
#include <cstring>

const int MaxN = 50000 + 5, MaxM = 100000 + 5;

int N, M, S;
int A[MaxN], Lnk[MaxN];
int U[MaxM], V[MaxM], W[MaxM];

void init() {
  scanf("%d %d", &N, &S);
  for (int i = 1; i <= N; ++i) {
    scanf("%d", &A[i]);
    Lnk[i] = i;
  }
}

inline bool cmp(int x, int y) {
  if (A[x] != A[y]) return A[x] < A[y];
  else return x < y;
}

void solve() {
  std::sort(Lnk + 1, Lnk + 1 + N, cmp);
  for (int i = 2, j = 1; i <= N; ++i) {
    while (j < N && A[Lnk[j + 1]] != A[Lnk[i]]) j++;
    M++;
    U[M] = Lnk[j], V[M] = Lnk[i], W[M] = A[Lnk[i]] - A[Lnk[j]];
  }

  bool ok = true;
  for (int i = 1; i <= M; ++i)
    if (W[i] < 1 || W[i] > S) ok = false;
  if (ok == false) printf("%d\n", -1);
  else {
    printf("%d\n", M);
    for (int i = 1; i <= M; ++i)
      printf("%d %d %d\n", U[i], V[i], W[i]);
  }
}

int main() {
//  freopen("a.in", "r", stdin);
//  freopen("a.out", "w", stdout);
  init();
  solve();
  return 0;
}

T2: 最小生成链

首先简单地说一下某几档部分分的做法：

$n \le 8$ ，枚举每条链，得到最小值即可。时间复杂度 $\mathcal{O}(n!)$ 。
$n \le 17$ ，类似于旅行商问题的做法，状压 DP 维护一个数组 $f[u][S]$ 表示目前这条链延伸到节点 $u$ ，链中包含的节点集合为 $S$ 时，链中最大值的最小值。每次 $\mathcal{O}(n)$ 枚举下一个节点直接转移过去即可。时间复杂度 $\mathcal{O}(n^2 2^n)$ ，由于遍历到的状态不多，是可以通过 $n = 17$ 的数据的。
$n \le 1\ 000, n \le 10^5$ ，能够证明最小生成链最大边权一定是最小生成树的最大边权。暴力写个 Prim 可以做到 $n^2$ ，用 Boruvka + Trie 树求最小生成树可以做到复杂度 $\mathcal{O}(n \log n \log a_i)$ ，详见 CF888G Xor-MST。

证明：首先最小生成树的最大边一定不大于最小生成链的最大边，然后按照下文的做法分为 $0,1$ 两块后，中间这条边就是最小生成链最大边。如果不连上这条边，那么 $0$ 的连通块和 $1$ 的连通块无法连通。因此这条边一定在最小生成树中，也就是说最小生成树的最大边不小于最小生成链的最大边。于是就证明了两种的最大边相等。

原问题在完全图上，边数达到了 $n^2$ 级别。直接在原图上处理显然是不行的，因此考虑转化问题。

众所周知，我们可以从左往右唯一的遍历一条链，这样得到的遍历序实际上就是一个序列。因此，一条链与一个序列是可以一一对应的。也就是说，对于一个 $n$ 个点若干条边的图，它当中存在的所有生成链对应的就是 $1$ 到 $n$ 的一个排列，且这个排列满足相邻元素间在原图中有边。

由于题目中给出的图是完全图，因此 $1$ 到 $n$ 的所有 $n!$ 种排列都是符合要求的。于是原题就可以转化为：

给出一个长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$ ，请找出一个排列，使得相邻两元素间异或值的最大值最小。

现在我们看到特殊性质：序列中的元素只有 $0$ 或 $1$ 。

相信大家都能推得出来这个子任务的结论：当序列中所有元素都是 $0$ 或都是 $1$ 时，答案为 $0$ ；否则——序列中既有元素 $0$ 又有元素 $1$ 时，答案为 $1$ 。

为什么会这样呢？感性理解一下，就是原序列中既有 $1$ 也有 $0$ ，那么无论如何都避免不了有至少一组 $0$ 和 $1$ 相邻，因此最大值至少就为 $1$ 。

我们把这个情况推广一下。由于位运算任意两位是不会互相影响的，我们考虑提取出原数列中的第 $i$ 位，单独考虑这一位的情况。我们容易发现，对于这独立的一位，同样满足类似性质——当原序列中所有数在这一位上都是 $0$ 或都是 $1$ 时，这位的答案一定是 $0$ ；否则这位答案一定是 $1$ 。

相信大家可以已经有一些想法了。

接下来我们需要回想起进制的一个有趣的性质，这也是我们经常利用的来做贪心的性质。也就是对于该进制的某一位 $i$ ，如果有两个数 $a, b$ ，满足 $a, b$ 高于 $i$ 的位全部相等并且 $a$ 在第 $i$ 位比 $b$ 在第 $i$ 位上的数大，那么无论低于 $i$ 的位是什么样的， $a$ 一定大于 $b$ 。

二进制也满足这个性质。因此我们考虑找出最高的一位满足原数列中所有数在这一位上既有 $0$ 也有 $1$ ，那么我们就可以根据这一位的值将原序列分成这一位为 $0$ 和这一位为 $1$ 的两部分。我们不难发现，对于这每个部分内，由于这个最高位是 $0$ ，因此永远不可能出现最大值。这个序列的最大值一定是出现在 $0$ 和 $1$ 交界的部分。

我们希望这个交界的部分两元素异或值最小。也就是说，我们需要从这一位为 $0$ 的元素中和这一位为 $1$ 的元素中各找出一个元素，使得这两个元素的异或值最小。

于是有一个显而易见的 $\mathcal{O}(n^2)$ 做法，枚举任意两个元素，找出异或值的最小值。解决了 $n \le 1\ 000$ 。

接下来这个找最小值的过程可以进行优化。这里有异或操作，很自然地能够想到 0-1 Trie。我们可以维护一棵 0-1 Trie，我们将序列中所有这一位为 $0$ 的元素插入这棵 Trie，然后用所有这一位为 $1$ 的元素去 Trie 中查异或最小值。最后所有最小值的最小值就是答案了。

要注意特判一下所有元素都相同的情况，因为这会找不到这个最高的位满足这一位上有 $0$ 和 $1$ 。

时间复杂度和空间复杂度都是 $\mathcal{O}(n \log a_i)$ 。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <vector>

const int MaxN = 1000000 + 5;
const long long INF = 0x7F7F7F7F7F7F7F7F;

int N;
long long A[MaxN];

struct Trie {
  int cntv;
  std::vector<int> ch[2];

  Trie() { cntv = 1; }

  inline void insert(long long x) {
    int u = 1;
    for (int i = 59; i >= 0; --i) {
      int c = (x & (1LL << i)) ? 1 : 0;
      if (ch[c][u] == 0) ch[c][u] = ++cntv;
      u = ch[c][u];
    }
  }

  inline long long qmin(long long x) {
    long long res = 0; int u = 1;
    for (int i = 59; i >= 0; --i) {
      int c = (x & (1LL << i)) ? 1 : 0;
      if (ch[c][u] != 0) u = ch[c][u];
      else {
        res |= (1LL << i);
        u = ch[c ^ 1][u];
      }
    }
    return res;
  }
};
Trie T;

void init() {
  scanf("%d", &N);
  for (int i = 1; i <= N; ++i) scanf("%lld", &A[i]);

  T.ch[0].resize(N * 60 + 5);
  T.ch[1].resize(N * 60 + 5);
}

void solve() {
  std::sort(A + 1, A + 1 + N);
  int maxBit = -1;
  for (int i = 59; i >= 0; --i)
    if ((A[1] ^ A[N]) & (1LL << i)) {
      maxBit = i;
      break;
    }

  if (maxBit == -1) {
    printf("%d\n", 0);
    return;
  }

  long long Ans = INF;
  for (int i = 1; i <= N; ++i) {
    if (A[i] & (1LL << maxBit)) Ans = std::min(Ans, T.qmin(A[i]));
    else T.insert(A[i]);
  }
  printf("%lld\n", Ans);
}

int main() {
//  freopen("b.in", "r", stdin);
//  freopen("b.out", "w", stdout);
  init();
  solve();
  return 0;
}

T3: 最小字典最短路

这是一道码农题 QwQ 思路可能很简单，但是代码写起来有点麻烦。我在此为自己的毒瘤向大家致歉。。。

对于 $n, m, q$ 均不超过 $300$ 的部分分，每次询问的时候都枚举起点 $x$ ，然后跑 SPFA 并路径还原找到 $x \to u$ 和 $x \to v$ 这两条最短路径，求一下公共路径长度，然后更新一下最大值即可。复杂度 $\mathcal{O}(nmq)$ 。

对于数据随机的部分分，可以把询问先读入进来。将出发点提前枚举，求出到每个点的最短路径，然后再处理这个出发点对每个询问的贡献。由于数据随机，因此最短路经过边数的期望可以视作小常数 $k$ ，应该不会超过 $10$ 。复杂度 $\mathcal{O}(nm + knq)$ 。

$n, m \le 300$ 的部分分是准备给写挂或者被卡空间的正解的。

对于 $85\% \sim 95\%$ 的数据，使用 SPFA 算法~~（您应该能猜到为什么不是“对于所有数据”了）~~跑出每个起点到其它点的最短路树。最短路树是一种满足如下条件的树：

这是一棵有根树，以起点 $s$ 为根节点。
每个节点的父亲就是它在起点 $s$ 到它的最短路径上的前驱节点。换句话说， $v$ 点的父亲节点 $u$ 就是在最短路转移时最终的 $\texttt{dis[v] = dis[u] + weight}$ 这个 $u$ 节点。

最短路树拥有一个很重要的性质：每个节点 $u$ 到根 $s$ 的这条路径，就是原图上 $s$ 到 $u$ 的最短路。

于是本问题转化为，对每个询问，找到一个根节点，使得 $u, v$ 在最短路树上的 LCA 到根距离最长。

这样本题就基本完成了，先用 DFS 跑出每个点的最短路树，然后对最短路树树剖，然后枚举每个询问，用树剖查找在这个最短路树上的 LCA，用根到 LCA 的最短路长度直接更新这个询问对应的答案即可。但是这题空间只开 32 MiB，建出 $n$ 棵最短路树会炸空间。因此要把询问离线读进来，枚举最短路树的根，然后再对每一个询问进行查询，用完后把最短路树滚动掉，让下一个起点接着用。复杂度 $\mathcal{O}(knm + nq \log n)$ ，~~ $k$ 是基于图的小常数~~。

不知道 SPFA 加一些奇奇怪怪的优化能不能通过本题，至少我的 SLF+LLL 优化都被卡了。如果想要做到满分，需要一种类似于解决费用流时我们学过的原始对偶算法的 Johnson 算法。

Johnson 算法大致过程是，先建一个虚拟的 $0$ 号点，从 $0$ 号点向 $1, 2, \cdots, n$ 号点都连一条权值为 $0$ 的有向边，然后跑一遍 SPFA。得到的最短路数组我们记作 $h[]$ ， $h_i$ 称为 $i$ 号点的势。

之后我们把原图进行一些奇妙的改造：将原图上每条边——不妨记作一条 $u$ 连向 $v$ 权值为 $w$ 的有向边——的边权变为 $w + h_u - h_v$ 。这样一来所有边权就都是非负的了，可以直接把 SPFA 换成 Dijkstra 算法（这是因为最短路满足三角形不等式 $w \ge h_v - h_u$ ，移项之后可得 $w + h_u - h_v \ge 0$ ）。

而且对于一条路径 $p = \langle a_1, a_2, a_3, \cdots, a_k \rangle$ ，则路径长度为 $w_{a_1 \to a_2} + h_{a_1} - h_{a_2} + w_{a_2 \to a_3} + h_{a_2} - h_{a_3} + \cdots + w_{a_{k - 1} \to a_k} + h_{a_{k - 1}} - h_{a_k}$ ，中间所有 $h$ 项全部消掉了，最后剩下 $w$ 项之和加上 $h_{a_1}$ 减掉 $h_{a_k}$ 。也就是说，在这张新图上任意两节点最短路 $dis'_{u \to v}$ ，都与它们在原图上最短路 $dis_{u \to v}$ 有如下等式关系： $dis'_{u \to v} = dis_{u \to v} + h_u - h_v$ 。由于 $h_u - h_v$ 是一个常数，因此在新图上最短路路径的形状也是不会改变的，改变的只是路径长度而已，而路径长度改变量又是可以推回去的，因此 Johnson 算法就没有问题了。

在 $95\%$ 做法的基础上，用 Johnson 替代 SPFA 即可，时间复杂度 $\mathcal{O}(nm \log m + nq \log n)$ ，空间复杂度 $\mathcal{O}(n + m + q)$ 。

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <functional>
#include <queue>
#include <utility>
#include <vector>

const int MaxV = 2000 + 5, MaxE = 8000 + 5;
const int MaxQ = 6000 + 5;
const int INF = 0x7F7F7F7F;

struct Graph {
  int cnte;
  int Head[MaxV], To[MaxE], Next[MaxE], Val[MaxE];

  inline void add_edge(int from, int to, int val) {
    cnte++; To[cnte] = to; Val[cnte] = val;
    Next[cnte] = Head[from]; Head[from] = cnte;
  }
};

struct Tree {
  int cnte;
  int Head[MaxV], To[MaxV], Next[MaxV], Val[MaxV];
  int fa[MaxV], dep[MaxV], siz[MaxV], wson[MaxV], top[MaxV], dis[MaxV];

  inline void clear() {
    cnte = 0;
    memset(Head, 0, sizeof Head);
    memset(To, 0, sizeof To);
    memset(Next, 0, sizeof Next);
    memset(Val, 0, sizeof Val);
    memset(fa, 0, sizeof fa);
    memset(dep, 0, sizeof dep);
    memset(siz, 0, sizeof siz);
    memset(wson, 0, sizeof wson);
    memset(top, 0, sizeof top);
    memset(dis, 0, sizeof dis);
  }

  inline void add_edge(int from, int to, int val) {
    cnte++; To[cnte] = to; Val[cnte] = val;
    Next[cnte] = Head[from]; Head[from] = cnte;
  }

  void dfs1(int u) {
    siz[u] = 1;
    for (int i = Head[u]; i; i = Next[i]) {
      int v = To[i], w = Val[i];
      fa[v] = u; dep[v] = dep[u] + 1;
      dis[v] = dis[u] + w;
      dfs1(v);
      siz[u] += siz[v];
      if (siz[v] > siz[wson[u]]) wson[u] = v;
    }
  }

  void dfs2(int u, int chain) {
    top[u] = chain;
    if (wson[u] != 0) dfs2(wson[u], chain);
    for (int i = Head[u]; i; i = Next[i]) {
      int v = To[i];
      if (v == wson[u]) continue;
      dfs2(v, v);
    }
  }

  void getRelation(int rt) {
    dfs1(rt);
    dfs2(rt, rt);
  }

  inline int getLca(int u, int v) {
    while (top[u] != top[v]) {
      if (dep[top[u]] < dep[top[v]]) std::swap(u, v);
      u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
  }
};

int N, M, Q;
int X[MaxQ], Y[MaxQ], Ans[MaxQ];
int H[MaxV], dis[MaxV];
Graph G1, G2;
Tree T;
std::vector<int> G[MaxV];

void init() {
  scanf("%d %d %d", &N, &M, &Q);
  for (int i = 1; i <= M; ++i) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    G1.add_edge(u, v, w);
  }
  for (int i = 1; i <= Q; ++i) scanf("%d %d", &X[i], &Y[i]);
}

void SPFA(int s) {
  std::queue<int> que;
  static bool in_queue[MaxV];
  memset(in_queue, false, sizeof in_queue);
  memset(H, 0x7F, sizeof H);
  H[s] = 0;
  que.push(s); in_queue[s] = true;
  while (!que.empty()) {
    int u = que.front(); que.pop();
    in_queue[u] = false;
    for (int i = G1.Head[u]; i; i = G1.Next[i]) {
      int v = G1.To[i], w = G1.Val[i];
      if (H[u] + w < H[v]) {
        H[v] = H[u] + w;
        if (in_queue[v] == false) {
          que.push(v);
          in_queue[v] = true;
        }
      }
    }
  }
}

void Dijkstra(int s) {
  std::priority_queue< std::pair<int, int> > pq;
  static bool vis[MaxV];
  memset(vis, false, sizeof vis);
  memset(dis, 0x7F, sizeof dis);
  dis[s] = 0; pq.push(std::make_pair(dis[s], s));
  while (!pq.empty()) {
    int u = pq.top().second; pq.pop();
    if (vis[u] == true) continue;
    vis[u] = true;
    for (int i = G2.Head[u]; i; i = G2.Next[i]) {
      int v = G2.To[i], w = G2.Val[i];
      if (dis[u] + w < dis[v]) {
        dis[v] = dis[u] + w;
        pq.push(std::make_pair(-dis[v], v));
      }
    }
  }
}

bool bsptVis[MaxV];

void buildShortestPathTree(int u) {
  for (std::vector<int>::iterator it = G[u].begin(); it != G[u].end(); ++it) {
    int v = *it;
    if (bsptVis[v] == false) {
      bsptVis[v] = true;
      buildShortestPathTree(v);
      T.add_edge(u, v, dis[v] - dis[u] + H[v] - H[u]);
    }
  }
}

void solve() {
  memset(Ans, -1, sizeof Ans);

  for (int i = 1; i <= N; ++i)
    G1.add_edge(0, i, 0);
  SPFA(0);
  for (int u = 1; u <= N; ++u) {
    for (int i = G1.Head[u]; i; i = G1.Next[i]) {
      int v = G1.To[i], w = G1.Val[i];
      G2.add_edge(u, v, w + H[u] - H[v]);
    }
  }

  for (int i = 1; i <= N; ++i) {
    T.clear();
    Dijkstra(i);

    for (int u = 1; u <= N; ++u) {
      G[u].clear();
      for (int e = G2.Head[u]; e; e = G2.Next[e]) {
        int v = G2.To[e], w = G2.Val[e];
        if (dis[u] != INF && dis[v] != INF && dis[u] + w == dis[v]) {
          G[u].push_back(v);
        }
      }
      std::sort(G[u].begin(), G[u].end());
    }

    memset(bsptVis, false, sizeof bsptVis);
    bsptVis[i] = true;
    buildShortestPathTree(i);
    T.getRelation(i);

    for (int q = 1; q <= Q; ++q) {
      int u = X[q], v = Y[q];
      if (i != u && T.dep[u] == 0) continue;
      if (i != v && T.dep[v] == 0) continue;
      Ans[q] = std::max(Ans[q], T.dis[T.getLca(u, v)]);
    }
  }

  for (int i = 1; i <= Q; ++i) printf("%d\n", Ans[i]);
}

int main() {
//  freopen("c.in", "r", stdin);
//  freopen("c.out", "w", stdout);
  init();
  solve();
  return 0;
}

#内推#