练习本

牛客2025秋季算法编程训练联赛6-基础组

Tags:

题目🔗 牛客2025秋季算法编程训练联赛6-基础组

A. 签到题

三条边构成三角形的充分必要条件是：假设 $a \le b \le c$ ，满足 $a + b \lt c$

题目给出的样例有一点误导性，开始以为需要等腰三角形才可以，其实并不是。

如果能够组成三角形，那么必定能够构造三个圆外切。设它们的半径分别是 $r_1, r_2, r_3$ , 那么满足 $r_1 + r_2 = a, r_1 + r_3 = b, r_2 + r_3 = c$ ，求解这个三元一次方程组。

void solve() {
  vector<int> a(3);
  For(i, 0, 3) cin >> a[i];
  sort(all(a));

  if (a[0] + a[1] > a[2]) {
    vector<double> arr(3);
    arr[1] = (1.0 * a[0] + a[1] - a[2]) / 2;
    arr[2] = a[1] - arr[1];
    arr[0] = a[0] - arr[1];
    sort(all(arr));
    cout << "Yes\n";
    for (auto i : arr) {
      cout << fixed << setprecision(2) << i << ' ';
    }
    cout << '\n';
  } else {
    cout << "wtnl\n";
  }
}

B. 括号序列

这道题比 A 简单。

我们只需要求出不匹配的括号的个数，只有两种情况不匹配：剩余的左括号，不能被匹配掉的右括号。

void solve() {
  int n;
  string s;
  cin >> n >> s;

  int ans{}, cur = 0;
  for (auto c : s) {
    if (c == '(')
      cur++;
    else {
      if (cur > 0)
        cur--;
      else
        ans++;
    }
  }

  ans += cur;
  cout << ans << '\n';
}

C. 十字阵列

记录第 $i$ 行总的伤害数，记录第 $j$ 列总的伤害数。如果把这两部分加起来，那么位置 $(i, j)$ 的伤害会被计算两次，因此我们需要记录下 $(i, j)$ 最后应该需要减去的伤害数。这样我们就可以得到每个位置最后实际的伤害数。

const int N = 2010;
ll a[N][N], col[N], row[N];

void solve() {
  int n, m, h;
  cin >> n >> m >> h;

  For1(i, 1, n) {
    row[i] = 0;
    For1(j, 1, m) a[i][j] = 0;
  }
  For1(j, 1, m) col[j] = 0;

  For(i, 0, h) {
    int x, y, z;
    cin >> x >> y >> z;
    row[x] += z;
    col[y] += z;
    a[x][y] += z;
  }

  ll ans = 0;
  For1(i, 1, n) {
    For1(j, 1, m) {
      ll tmp = row[i] + col[j] - a[i][j];
      ans = (ans + (tmp * (i + j) % MOD)) % MOD;
    }
  }
  cout << ans << '\n';
}

D. 配对

容易想到我们可以对答案进行二分，设最终的答案是 $sum$ ，我们需要保证两个数组中，我们可以构造出数对和 $\ge sum$ 的数对的数量 $\ge k$ 。此时最大 $sum$ 就是所求。

接下来考虑对于给定的 $sum$ ，如何找到这样的数对的数量，使得每个数对的和都 $\ge sum$ 。这恰好是一个双指针经典问题：把数组 $A$ 从小到大排序，数组 $B$ 从大到小排序。如果 $A_i + B_j \ge sum$ ，那么我们找到合法的一对，此时 $i++, j++$ 。如果 $A_i + B_j \lt sum$ ，此时 $i++$ 。

void solve() {
  int n, k;
  cin >> n >> k;

  VI a(n), b(n);
  For(i, 0, n) cin >> a[i];
  For(i, 0, n) cin >> b[i];
  sort(all(a));
  sort(all(b), greater<int>());

  auto check = [&](ll sum) -> bool {
    ll res = 0;
    for (int i = 0, j = 0; i < n && j < n;) {
      if ((ll)a[i] + b[j] >= sum) {
        res++;
        i++;
        j++;
      } else {
        i++;
      }
    }
    return res >= k;
  };

  ll l = 1, r = 2e8 + 10, mid;
  while (l < r) {
    mid = (l + r + 1) / 2;
    if (check(mid))
      l = mid;
    else
      r = mid - 1;
  }

  cout << l << '\n';
}

E. 重排列

容易发现，对两个数组排序，不会影响答案。

如果排序之后，还是不能够满足条件，那么无解。

如果有解，我们可以求出方案数。对于 $B_i$ ，我们可以求出 $A_j \le B_i$ 的最大的 $j$ ，也就是说 $A[1..j]$ 中的所有数字都可以放在 $B_i$ 的位置。因为 $B$ 已经排好序了，我们还需要考虑到 $B[1..i-1]$ 它们已经占用的位置，因此 $B_i$ 对应的方案数是 $j - (i - 1)$ ，根据乘法原理，把所有的 $B_i$ 对应的方案数相乘就是答案。

void solve() {
  int n;
  cin >> n;

  VI a(n), b(n);
  For(i, 0, n) cin >> a[i];
  For(i, 0, n) cin >> b[i];
  sort(all(a));
  sort(all(b));

  ll ans = 0;
  int cnt = 0;
  For(i, 0, n) {
    if (a[i] > b[i]) {
      cout << "0\n";
      return;
    }
  }

  ans = 1;
  for (int i = 0, j = 0; j < n; j++) {
    while (i < n && a[i] <= b[j])
      i++;
    ans = ans * (i - cnt) % MOD;
    cnt++;
  }
  cout << ans << '\n';
}

F. 图

很有意思的一道题目。

简单路径的含义是，路径上不经过重复的点。

因为题目条件中要求每个点仅有一条出边，所以这个图其实并不复杂。可能存在环，如果存在环也没有问题，我们可以把环切断作为路径的一部分。

画图可以发现，分成一下几种情况：

最简单的是一条链的情况。

如果存在环，那么就不能“逃”出去了，每个点的入度都恰好是 1.

一条链或者多条链最多可以连接到一个环中。

也就是最终的答案构成一定是：一条链+可选的一个环。

我们可以通过拓扑排序，得到所有的环，同时得到所有链上每个点的深度（也就是以当前点做为终点的最长链的长度）。

然后对每个环进行一次 DFS，求出环的大小。用环大小加上链长度维护答案。

const int N = 1000100;
int n, g[N], deg[N], dep[N];
bool st[N];

void Init() {
  For1(i, 1, n) {
    deg[i] = 0;
    g[i] = -1;
    st[i] = false;
    dep[i] = 1;
  }
}

int dfs(int u, int &mx) {
  st[u] = true;
  ckmax(mx, dep[u]);

  int res = 1, v = g[u];
  if (!st[v]) {
    res += dfs(v, mx);
  }
  return res;
}

void solve() {
  cin >> n;
  Init();
  For1(i, 1, n) {
    int x;
    cin >> x;
    g[i] = x;
    deg[x]++;
  }

  queue<int> q;
  For1(i, 1, n) {
    if (deg[i] == 0) {
      q.push(i);
    }
  }

  while (!q.empty()) {
    auto t = q.front();
    st[t] = true;
    q.pop();
    int v = g[t];
    ckmax(dep[v], dep[t] + 1);
    deg[v]--;
    if (deg[v] == 0) {
      q.push(v);
    }
  }

  int ans = 0;
  For1(i, 1, n) {
    if (!st[i]) {
      int cur_dep = 0;
      int sz = dfs(i, cur_dep), tmp = sz + cur_dep;
      ckmax(ans, tmp - 1);
    }
  }
  cout << ans << '\n';
}