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

T1: 最短路

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

对于第二档部分分,我们希望每一个点都从最近的那个点连过来。也就是说,对于某个点 ,我们可以找到一个 ,满足 并且 尽可能大,然后从 连一条权值为 的边。可以证明这样构造出的图一定是最优的(最大边边权最小的),因此若找不到点 (即 )或 ,则一定无解。暴力找前驱 可以做到 的复杂度。结合上一档部分分可以拿到 分。

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

#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: 最小生成链

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

  • ,枚举每条链,得到最小值即可。时间复杂度

  • ,类似于旅行商问题的做法,状压 DP 维护一个数组 表示目前这条链延伸到节点 ,链中包含的节点集合为 时,链中最大值的最小值。每次 枚举下一个节点直接转移过去即可。时间复杂度 ,由于遍历到的状态不多,是可以通过 的数据的。

  • ,能够证明最小生成链最大边权一定是最小生成树的最大边权。暴力写个 Prim 可以做到 ,用 Boruvka + Trie 树求最小生成树可以做到复杂度 ,详见 CF888G Xor-MST

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

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

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

由于题目中给出的图是完全图,因此 的所有 种排列都是符合要求的。于是原题就可以转化为:

给出一个长度为 的序列 ,请找出一个排列,使得相邻两元素间异或值的最大值最小。

现在我们看到特殊性质:序列中的元素只有

相信大家都能推得出来这个子任务的结论:当序列中所有元素都是 或都是 时,答案为 ;否则——序列中既有元素 又有元素 时,答案为

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

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

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

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

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

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

于是有一个显而易见的 做法,枚举任意两个元素,找出异或值的最小值。解决了

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

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

时间复杂度和空间复杂度都是

#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 思路可能很简单,但是代码写起来有点麻烦。我在此为自己的毒瘤向大家致歉。。。

对于 均不超过 的部分分,每次询问的时候都枚举起点 ,然后跑 SPFA 并路径还原找到 这两条最短路径,求一下公共路径长度,然后更新一下最大值即可。复杂度

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

的部分分是准备给写挂或者被卡空间的正解的。

对于 的数据,使用 SPFA 算法(您应该能猜到为什么不是“对于所有数据”了)跑出每个起点到其它点的最短路树。最短路树是一种满足如下条件的树:

  1. 这是一棵有根树,以起点 为根节点。
  2. 每个节点的父亲就是它在起点 到它的最短路径上的前驱节点。换句话说, 点的父亲节点 就是在最短路转移时最终的 这个 节点。

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

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

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

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

Johnson 算法大致过程是,先建一个虚拟的 号点,从 号点向 号点都连一条权值为 的有向边,然后跑一遍 SPFA。得到的最短路数组我们记作 称为 号点的势。

之后我们把原图进行一些奇妙的改造:将原图上每条边——不妨记作一条 连向 权值为 的有向边——的边权变为 。这样一来所有边权就都是非负的了,可以直接把 SPFA 换成 Dijkstra 算法(这是因为最短路满足三角形不等式 ,移项之后可得 )。

而且对于一条路径 ,则路径长度为 ,中间所有 项全部消掉了,最后剩下 项之和加上 减掉 。也就是说,在这张新图上任意两节点最短路 ,都与它们在原图上最短路 有如下等式关系:。由于 是一个常数,因此在新图上最短路路径的形状也是不会改变的,改变的只是路径长度而已,而路径长度改变量又是可以推回去的,因此 Johnson 算法就没有问题了。

做法的基础上,用 Johnson 替代 SPFA 即可,时间复杂度 ,空间复杂度

#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;
}
#内推#
全部评论
第二题也可以二分区间来做
点赞 回复 分享
发布于 2019-08-19 12:24
需要一种类似于解决费用流时我们学过的原始对偶算法的 Johnson 算法。 然而我们并没有结果掉费用流,也并没有学习过原始对偶算法。 结果我没看到负边 迪杰斯特拉 直接凉凉 完全没有办法。
点赞 回复 分享
发布于 2019-08-19 12:42
三道图论题真的好吗QAQ
点赞 回复 分享
发布于 2019-08-19 12:38
第三题Floyd骗了60分
点赞 回复 分享
发布于 2019-08-19 14:00
第三题正解打歪了5 分哭泣
点赞 回复 分享
发布于 2019-08-19 14:47
第一题没看到边权不能为0,贪心写炸的来报个到
点赞 回复 分享
发布于 2019-08-19 15:07

相关推荐

10-30 23:23
已编辑
中山大学 Web前端
去B座二楼砸水泥地:这无论是个人素质还是专业素质都👇拉满了吧
点赞 评论 收藏
分享
27 10 评论
分享
牛客网
牛客企业服务