A - Insert

题目大意

给定一个长度为 $n$ 的序列 $A$ ，在 $A$ 的第 $k$ 个元素或插入整数 $x$ 并输出新的序列.

解题思路

按要求输出即可.

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int n, k, x;
  cin >> n >> k >> x;
  for (int i = 1; i <= n; i++) {
    int y;
    cin >> y;
    cout << y << " ";
    if (i == k) {
      cout << x << " ";
    }
  }
  cout << "\n";

  return 0;
}

B - Intesection of Cuboids

题目大意

给定三维坐标系中两个各面都平行于 $xy$ 平面， $yz$ 平面， $zx$ 平面的正方体的体对角线上的顶点，问这两个正方体是否相交.

解题思路

设两个正方形的两个顶点分别为 $(a,b,c),(d,e,f)$ 和 $(g,h,i),(j,k,l)$ ，则两个正方形相交当且仅当它们在 $x$ 轴方向上的区间、 $y$ 轴方向上的区间、 $z$ 轴方向上的区间分别相交。判断 $3$ 次区间相交即可.

代码

#include <bits/stdc++.h>

using namespace std;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  vector<int> a(12);
  for (int i = 0; i < 12; i++) {
    cin >> a[i];
  }
  if (max(a[0], a[6]) < min(a[3], a[9]) && max(a[1], a[7]) < min(a[4], a[10]) &&
      max(a[2], a[8]) < min(a[5], a[11])) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }

  return 0;
}

C - Make Them Narrow

题目大意

给定一个长度为 $n$ 的序列 $A$ ，要求通过删除其中的 $k$ 个元素，使得剩余元素的最大值与最小值之差最小.

解题思路

经典滑动窗口，只需要对 $A$ 排序后维护一个长度为 $n-k$ 的滑动窗口，并同时维护答案即可.

代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

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

  sort(a.begin() + 1, a.end());
  int len = n - k;
  i64 ans = 1ll << 60;
  for (int l = 1, r = n - k; r <= n; r++, l++) {
    i64 res = a[r] - a[l];
    ans = min(ans, res);
  }

  cout << ans << "\n";

  return 0;
}

D - Go Stone Puzzle

题目大意

给定两个长度为 $n$ 的字符串 $S,T$ ，且 $S,T$ 仅由字母 ‘B’, ‘W’ 组成，最初在 $S$ 串末尾两个位置 ( $pos_{n+1}, pos_{n+2}$ )

处有两个空位，每次操作可将 $S$ 连续两个非空位置的字母组成的字串放在空位处（同时自身变为空位），问最少需要多少次操作使 $S$ 等于 $T$ .

解题思路

注意到 $n$ 最大只有 $14$ ，直接 bfs 暴搜即可.

代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int n;
  cin >> n;
  string s, t;
  cin >> s >> t;
  map<string, int> mp;
  string st = s + "00";
  mp[st] = 0;
  queue<string> q;
  q.push(st);
  while (!q.empty()) {
    auto u = q.front();
    q.pop();
    int x = 0;
    for (int i = 0; i < n + 2; i++) {
      if (u[i] == '0') {
        x = i;
        break;
      }
    }
    for (int i = 0; i < n + 1; i++) {
      if (i == x || i == x + 1 || i == x - 1) continue;
      string v = u;
      v[x] = u[i], v[x + 1] = u[i + 1];
      v[i] = '0', v[i + 1] = '0';
      if (!mp.contains(v)) {
        mp[v] = mp[u] + 1;
        q.push(v);
      }
    }
  }

  string ed = t + "00";
  cout << (mp.contains(ed) ? mp[ed] : -1) << "\n";

  return 0;
}

E - Tree and Hamilton Path 2

题目大意

给定一棵有边权的树，问最少需要经过多长的路径使得经过所有结点.

解题思路

由于不需要从终点回到出发点，所以一条合法路径相当于树上所有边的和的两倍 $sum$ 减去从出发点到终点的路径长度 $x$ . 而 $sum$ 是一个定值，因此我们只需要最大化 $x$ , 即求出树上最长路径（即树的直径） $mx$ ，最终答案为 $sum-mx$ . 求树的直径使用经典的两次 dfs 即可.

代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int n;
  cin >> n;
  vector<vector<pair<int, int>>> adj(n + 1);
  i64 sum = 0;
  for (int i = 1; i < n; i++) {
    int u, v, w;
    cin >> u >> v >> w;
    adj[u].push_back({v, w});
    adj[v].push_back({u, w});
    sum += 2ll * w;
  }

  vector<i64> d(n + 1);
  int id = 1;
  i64 mx = 0;
  auto dfs = [&](auto dfs, int u, int fa) -> void {
    for (auto [v, w] : adj[u]) {
      if (v == fa) continue;
      d[v] = d[u] + w;
      if (d[v] > mx) {
        mx = d[v], id = v;
      }
      dfs(dfs, v, u);
    }
  };
  dfs(dfs, 1, 0);
  mx = 0;
  d[id] = 0;
  dfs(dfs, id, 0);

  cout << sum - mx << "\n";

  return 0;
}

F - x = a^b

题目大意

给定整数 $n (1\le n\le 10^{18})$ ，求 $1$ 到 $n$ 中有多少数可以表示为 $a^b$ 的形式，其中 $a,b$ 为正整数且 $b\ge 2$ .

解题思路

我们考虑对不同范围的 $i$ 分别进行计数. 对于 $10^6$ 以内的数，我们暴力枚举每个数的 $x$ 次幂是否在 $1$ 到 $n$ 范围内，这一部分的复杂度为 $O(10^6\cdot\log{10^6})$ , 对于大于 $10^6$ 的部分，这些数字最多只有 $2$ 次幂是可能符合要求的（因为 $(10^6)^3$ 已经达到了 $10^{18}$ ），因此对于这一部分，我们只需要求出 $\lfloor \sqrt{n} \rfloor$ ，再减去 $10^6$ 即可. 注意计数时要防止重复计数.

代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const int m = 1'000'000;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  i64 n;
  cin >> n;

  i64 ans = 1, cnt = 0;
  set<i64> vis;
  i64 hi = sqrtl(n);
  for (int i = 2; i <= m; i++) {
    i64 a = 1ll * i * i;
    while (a <= n) {
      if (!vis.contains(a)) {
        vis.insert(a);
        ans++;
        if (a > m && a <= hi) cnt++;
      }
      if (a > n / i) {
        break;
      }
      a *= i;
    }
  }

  ans += max(0ll, hi - m - cnt);
  cout << ans << "\n";

  return 0;
}

G - Go Territory

待补题.