526互联

3 月 22 日测试题解

发布时间 2023-03-24 22:36:56作者: ForgotDream

3 月 22 日测试题解

T1

题意

定义两个长度为 \(n\) 的 01 串 \(i\) 与 \(j\) 的差异值 \(d(i, j)\) 为：

\[\sum_{k = 0}^{n - 1}{i_k \oplus j_k} \]

现在给你 \(n\) 个 01 串的集合 \(s\)，你需要找到一个 01 串 \(ans\) 使得 \(\sum_{i \in s} d(i, ans)\) 最小并且保证 0 最多，求出这个 01 串。

\(n \le 1000\)。

思路

\(\text{100pts}\)

我们考虑到每一位的差异值是相互独立的，也就是说优化总的差异值等价于优化每一位的差异值。

那么这道题就很简单了，考虑对每一位进行贪心，统计每一位的 0 与 1 的个数，再取个数多的那个就是了。唯一的一个坑点就是当 0 与 1 的个数相等时要输出 0，这样才能保证 0 的个数最多。

代码

\(\text{100pts}\)

#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <iostream>

using i64 = long long;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  
  int n;
  std::cin >> n;
  
  std::string s;
  std::cin >> s;
  int l = s.length();
  
  std::vector<std::vector<int>> a(l, std::vector<int>(n));
  for (int i = 0; i < l; i++) {
    a[i][0] = (s[i] == '1');
  }
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < l; j++) {
      char c;
      std::cin >> c;
      a[j][i] = (c == '1');
    }
  }
  
  for (int i = 0; i < l; i++) {
    int cnt = std::count(a[i].begin(), a[i].end(), 1);
    if (cnt > n - cnt) {
      std::cout << "1";
    } else {
      std::cout << "0";
    }
  }
  std::cout << "\n";
  
  return 0;
}

T2

题意

数轴上有 \(n\) 个点，你可以执行如下操作：

  1. 选取一段长度为 \(L\) 的区间并将其中的点全部删去；
  2. 选取一段长度为 \(2L\) 的区间并将其中的点全部删去。

其中，操作 1 可以执行 \(r\) 次，操作 2 可以执行 \(g\) 次，现在问你能够删去数轴上所有点的最小的 \(L\) 是多少。

对于 \(50\%\) 的数据，\(n \le 100\)；
对于 \(100\%\) 的数据，\(1 \le n \le 2000\)，\(1 \le r, g \le 10^9\)，对于任意一个点 \(i\)，保证 \(1 \le i \le 10^9\)。

思路

\(\text{50pts(Maybe)}\)

考虑爆搜，对每一个点判断一下使用第一种还是第二种，加上一些剪枝能过。

\(\text{100pts}\)

本题正解为二分 + DP，突然知道考场上为啥没想出来了。

考虑二分一个答案 \(num\)，我们通过预处理计算出对于每一个点在执行操作 1 与操作 2 时最远能够覆盖到哪个点并将其记录在数组 \(p\) 与 \(q\) 中，并钦定 \(p_{n + 1} = q_{n + 1} = n\)，然后做 DP，设 \(f_{i, j}\) 为执行 \(i\) 次操作 1，\(j\) 次操作 2 时能够达到的最远的点，那么有：

\[f_{i, j} = \begin{cases} \max(f_{i, j}, p_{f{i - 1, j} + 1}) & i > 0 \\ \max(f_{i, j}, q_{f{i, j - 1} + 1}) & j > 0 \\ \end{cases} \]

时间复杂度为 \(O(n^2 \log n)\)。预处理部分可以用二分搜索做一下，也可以直接暴力枚举。

代码

\(\text{100pts}\)

#include <bits/stdc++.h>

using i64 = long long;

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  int n, r, g;
  std::cin >> n >> r >> g;

  std::vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i];
  }

  if (r + g >= n) {
    std::cout << 1 << "\n";
    return 0;
  }

  std::sort(a.begin() + 1, a.end());

  auto check = [&](int num) -> bool {
    std::vector<std::vector<int>> f(r + 1, std::vector<int>(g + 1));
    std::vector<int> p(n + 2), q(n + 2);
    
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (a[j] - a[i] + 1 <= num) {
          p[i] = j;
        }
        if (a[j] - a[i] + 1 <= 2 * num) {
          q[i] = j;
        }
      }
    }

    p[n + 1] = q[n + 1] = n;

    for (int i = 0; i <= r; i++) {
      for (int j = 0; j <= g; j++) {
        if (i > 0) {
          f[i][j] = std::max(f[i][j], p[f[i - 1][j] + 1]);
        }
        if (j > 0) {
          f[i][j] = std::max(f[i][j], q[f[i][j - 1] + 1]);
        }
      }
    }

    return f[r][g] == n;
  };

  int L = 1, R = a[n] - a[1], ans = 0;

  while (L <= R) {
    int mid = (L + R) >> 1;
    if (check(mid)) {
      ans = mid;
      R = mid - 1;
    } else {
      L = mid + 1;
    }
  }

  std::cout << ans << "\n";

  return 0;
}

T3

题意

在无向图中求单源严格次短路。原点为 \(1\)，汇点为 \(n\)。

\(n \le 5000\)。

思路

\(\text{100pts}\)

你谷上有原题。

求单源次短路大概有这么几种做法：

  • 在 Bellman-Ford 或者 SPFA 的过程中同时维护最小值与次小值；
  • 从原点做一遍最短路，再从汇点做一遍最短路，然后枚举每一条边；
  • 先求一遍最短路，然后用 BFS 或者 DFS 暴力枚举，时间复杂度同上。但是可以改造为求 \(k\) 短路的暴力算法；
  • 利用 A* 优化上边的 BFS，最劣时间复杂度不变，但是在随机数据下会快很多。
  • 可持久化可并堆。

我在考试的时候写的是第二种做法，其他几个都可以说是杀鸡用牛刀了。时间复杂度为 \(O(n \log n)\)。

代码

\(\text{100pts}\)

#include <bits/stdc++.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>

using i64 = long long;
using Edge = std::pair<int, int>;

struct Graph {
  std::vector<std::vector<Edge>> e;
  int n, m;

  Graph(int n) {
    this->n = n;
    e.resize(n);
  }
  
  void add(int u, int v, int w) {
    e[u].emplace_back(v, w);
    return;
  }
  
  std::vector<int> dijkstra(int s, int t) {
    std::priority_queue<std::pair<int, int>, 
                        std::vector<std::pair<int, int>>, 
                        std::greater<std::pair<int, int>>> pq;
    std::vector<int> dis(n, 2e9);
    std::vector<bool> vis(n);
    dis[s] = 0;
    
    pq.emplace(0, s);
    while (!pq.empty()) {
      int u = pq.top().second;
      // std::cerr << u << "\n";
      pq.pop();
      
      if (vis[u]) {
        continue;
      }
      vis[u] = true;
      
      for (auto i : e[u]) {
        int v = i.first, w = i.second;
        if (dis[v] > dis[u] + w) {
          dis[v] = dis[u] + w;
          pq.emplace(dis[v], v);
        }
      }
    }
    
    return dis;
  }
  
  int solve(int s, int t) {
    auto rst1 = dijkstra(t, s), rst2 = dijkstra(s, t);
    int min = rst1[s], ans = 2e9;
    
    for (int u = 1; u < n; u++) {
      for (auto i : e[u]) {
        int v = i.first, w = i.second;
        if (rst1[v] + rst2[u] + w > min) {
          ans = std::min(ans, rst1[v] + rst2[u] + w);
        }
      }
    }
    
    return ans;
  }
};

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  int n, m;
  std::cin >> n >> m;
  Graph G(n + 1);
  
  for (int i = 0, u, v, w; i < m; i++) {
    std::cin >> u >> v >> w;
    G.add(u, v, w);
    G.add(v, u, w);
  }
  
  std::cout << G.solve(1, n) << "\n";
  
  return 0;
}