2024/09/30 模拟赛总结

\(0+0+42+40\)，T1在写正解的时候突然比赛还有1分钟结束，然后把 freopen 注释的暴力在最后几秒交了上去

#A. 博弈

唐氏 xor-hashing，首先博弈游戏很简单，如果有一个数的出现次数是奇数则先手必胜，否则先手必败

那么先手必败的条件就是路径上所有边权都是两两配对的，即异或和为 \(0\)。那么钦定点 \(1\) 为根，求出它到每个点的异或和，用 map 存下每个和的出现次数。答案为 \({n \choose 2} - \sum {\text{mp}_i \choose 2}\)

因为边权太小，异或可能会挂掉，所以需要随机一个较大值来异或防止错误

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 5e5 + 5;

LL cnt, s[kMaxN];
vector<pair<int, LL>> g[kMaxN];
int t, n;
map<LL, LL> h, ans;
mt19937_64 rd(time(0) + 3247 + 1508);

void DFS(int u, int fa) {
  ans[s[u]]++;
  for (auto [v, w] : g[u]) {
    if (v != fa) {
      s[v] = s[u] ^ h[w], DFS(v, u);
    }
  }
}

int main() {
  freopen("game.in", "r", stdin), freopen("game.out", "w", stdout);
  for (cin >> t; t; t--, ans.clear()) {
    cin >> n;
    for (int i = 1, u, v, w; i < n; i++) {
      cin >> u >> v >> w, g[u].push_back({v, w}), g[v].push_back({u, w}), (!h[w]) && (h[w] = rd());
    }
    s[1] = 0, DFS(1, 0), cnt = 1ll * n * (n - 1) / 2;
    for (auto [u, v] : ans) {
      cnt -= v * (v - 1) / 2;
    }
    cout << cnt << '\n';
    for (int i = 1; i <= n; i++) {
      g[i].clear();
    }
  }
  return 0;
}

#B. 跳跃

显然跳跃形式一定是形如 \(l_1 \rightarrow r_1 \rightarrow l_1 \dots l_1 \rightarrow r_2 \rightarrow l_2 \rightarrow r_2 \rightarrow l_2 \rightarrow r_3 \dots r_m \rightarrow l_m\)，其中 \(l_i \le r_1 \le l_2 \le r_2 \le \dots \le l_m \le r_m\)

令 \(dp_i\) 为跳到 \(i\)，最小跳跃次数以及分数。然后枚举上一个段来直接大力转移即可

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 1e3 + 5;

LL t, n, k, a[kMaxN << 1], s[kMaxN << 1], mx[kMaxN << 1], ans, e[kMaxN << 1], vis[kMaxN << 1], g[kMaxN << 1];
queue<LL> q;

LL Calc(LL x, LL y) { return s[max((x - 1) % n + 1, (y - 1) % n + 1)] - s[min((x - 1) % n + 1, (y - 1) % n + 1) - 1]; }

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("jump.in", "r", stdin), freopen("jump.out", "w", stdout);
  for (cin >> t; t; t--, ans = 0) {
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
      cin >> a[i], s[i] = s[i - 1] + a[i];
    }
    fill(mx + 1, mx + 2 * n + 1, -1e18), fill(e + 1, e + 2 * n + 1, 1e18), fill(vis + 1, vis + 2 * n + 1, 0), fill(g + 1, g + 2 * n + 1, -1e18);
    for (int i = 1; i <= n; i++) {
      for (int j = i; j <= n; j++) {
        mx[i] = max(mx[i], (s[j] - s[i - 1]) << 1), mx[j + n] = max(mx[j + n], (s[j] - s[i - 1]) << 1);
      }
    }
    for (e[1] = g[1] = 0, q.push(1); !q.empty();) {
      LL u = q.front();
      q.pop(), vis[u]++;
      if (vis[u] == (n << 1 | 1)) {
        continue;
      }
      for (int i = 1; i <= n << 1; i++) {
        if ((u <= n && i >= u + n) || (i <= n && u >= i + n)) {
          LL v = e[u], w = g[u], tmp = Calc(i, u);
          if (w + tmp < 0 && mx[u] <= 0) {
            continue;
          }
          if (w + tmp < 0) {
            LL p = (mx[u] - 1 - w - tmp) / mx[u];
            v += p << 1, w += p * mx[u];
          }
          w += tmp, v++;
          if (v < e[i] || v == e[i] && w > g[i]) {
            e[i] = v, g[i] = w, q.push(i);
          }
        }
      }
    }
    for (int i = 1; i <= n << 1; i++) {
      if (e[i] <= k) {
        ans = max({ans, g[i], (k - e[i]) / 2 * mx[i]});
        if (e[i] != k) {
          for (int j = 1; j <= n << 1; j++) {
            LL tmp = Calc(i, j);
            (tmp >= 0) && (ans = max(ans, g[i] + (k - 1 - e[i]) / 2 * mx[i] + tmp));
          }
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

#C. 大陆

原题

纯人类智慧，进行一遍 DFS 所当前子树节点数量大于 \(B\)，则直接割开。最后剩下遗留的子树合起来一定小于 \(3B\)，之久分为一组即可

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 1e4 + 5;

int n, b, tot, ans[kMaxN], sz[kMaxN], m[kMaxN];
vector<int> g[kMaxN], s[kMaxN];

void DFS(int u, int fa) {
  for (int v : g[u]) {
    if (v != fa) {
      DFS(v, u), sz[u] += sz[v], (s[u].size() < s[v].size()) && (swap(s[u], s[v]), 0);
      for (int tmp : s[v]) {
        s[u].push_back(tmp);
      }
      if (sz[u] >= b) {
        m[++tot] = u;
        for (int tmp : s[u]) {
          ans[tmp] = tot;
        }
        s[u].clear(), sz[u] = 0;
      }
    }
  }
  sz[u]++, s[u].push_back(u);
  if (sz[u] >= b) {
    m[++tot] = u;
    for (int tmp : s[u]) {
      ans[tmp] = tot;
    }
    s[u].clear(), sz[u] = 0;
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("mainland.in", "r", stdin), freopen("mainland.out", "w", stdout);
  cin >> n >> b;
  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
  }
  DFS(1, 0);
  for (int tmp : s[1]) {
    ans[tmp] = tot;
  }
  cout << tot << '\n';
  for (int i = 1; i <= n; i++) {
    cout << (ans[i] ? ans[i] : tot) << " \n"[i == n];
  }
  for (int i = 1; i <= tot; i++) {
    cout << m[i] << " \n"[i == tot];
  }
  return 0;
}

#D. 排列

要写 FHQ，理解思路但懒得写，先咕咕咕