2024/10/13 模拟赛总结

人机体检，\(0+0+0+0=0\)，打代码源去了

#A. 一般图最小匹配

下次看到这种范围一定要想到 dp 啊，令 \(dp_{i,j}\) 为前 \(i\) 个元素选了 \(j\) 对点的最小代价

由于边权是绝对值，可以对原数组排一遍序，选取的两个点就一定在排序后数组的相邻节点

那么就可以得出式子：\(dp_{i,j}=\min\{dp_{i-1,j},dp_{i-2,j-1}+a_i-a_{i-1}\}\)

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

using namespace std;
using LL = long long;

const int kMaxN = 5e3 + 5;

int n, m, a[kMaxN];
LL dp[kMaxN][kMaxN >> 1];

int main() {
	freopen("match.in", "r", stdin), freopen("match.out", "w", stdout);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a + 1, a + n + 1), fill(dp[0] + 1, dp[2], 1e18), dp[1][0] = 0;
  for (int i = 2; i <= n; i++) {
    dp[i][0] = 0;
    for (int j = 1; j <= m; j++) {
      dp[i][j] = min(dp[i - 1][j], dp[i - 2][j - 1] + a[i] - a[i - 1]);
    }
  }
  cout << dp[n][m] << '\n';
  return 0;
}

#B. 重定向

对于未填入的数，直接从小到大天然有剩余的数即可

对于每一位，考虑删掉它会不会更优，当 \(a_i>a_{i+1}\) 时，删掉 \(i\) 会更优，否则会更劣

如果 \(a_{i+1}=0\)，且其本来应该填入 \(x\)，用 \(x\) 和 \(a_i\) 来比较是否要删除即可

如果 \(a_i=0\)，按同样的方式考虑

使用 set 维护每一个位置本来填入的数然后按照上面判断即可

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

using namespace std;

const int kMaxN = 2e5 + 5;

int t, n, a[kMaxN], e[kMaxN], genshin[kMaxN];
set<int> s;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("redirect.in", "r", stdin), freopen("redirect.out", "w", stdout);
  for (cin >> t, iota(genshin + 1, genshin + kMaxN, 1); t; t--, s.clear()) {
    cin >> n, for_each(genshin + 1, genshin + n + 1, [](int i) { s.insert(i); });
    for (int i = 1; i <= n; i++) {
      cin >> a[i], a[i] && s.erase(a[i]);
    }
    e[n + 1] = a[n + 1] = n + 1;
    for (int i = n; i; i--) {
      e[i] = (a[i] && a[i] < a[e[i + 1]]) ? i : e[i + 1];
    }
    for (int i = 1; i <= n; i++) {
      if (i == n || a[i] && a[i + 1] && a[i] > a[i + 1]) {
        a[i] = -1;
        break;
      }
      if (!a[i]) {
        if (a[e[i]] < *s.begin()) {
          a[e[i]] = -1;
          break;
        }
      } else if (!a[i + 1]) {
        if ((a[i] >= *s.begin() || !a[i]) && *s.begin() < a[i]) {
          a[i] = -1;
          break;
        }
      }
      !a[i] && (s.erase(s.begin()), 0);
    }
    s.clear(), for_each(genshin + 1, genshin + n + 1, [](int i) { return s.insert(i); });
    for (int i = 1; i <= n; i++) {
      ~a[i] && s.erase(a[i]);
    }
    for (int i = 1; i <= n; i++) {
      if (a[i] && ~a[i]) {
        cout << a[i] << ' ';
      } else if (~a[i]) {
        cout << *s.begin() << ' ', s.erase(s.begin());
      }
    }
    cout << '\n';
  }
  return 0;
}

#C. 斯坦纳树

令不在关键点集中的点为虚点，然后对所有相连的边权为 \(0\) 的点由于斯坦纳树的性质可以缩成一个点。当这个集合中有任意一个点在点集中就当作这整个点都在点集中

然后倒着枚举一遍如果没有虚点则答案为 \(1\)，否则为 \(0\)

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

using namespace std;
using pii = pair<int, int>;

const int kMaxN = 3e5 + 5;

int n, cnt, tot, c[kMaxN], p[kMaxN], k[kMaxN], pre[kMaxN], ans[kMaxN], f[kMaxN];
bitset<kMaxN> vis;
vector<pii> e[kMaxN];
vector<int> g[kMaxN];
set<pii> s;
set<int> o[kMaxN];

void DFS(int u) {
  c[u] = cnt;
  for (auto [v, w] : e[u]) {
    if (!c[v] && !w) {
      DFS(v);
    }
  }
}
void DFS1(int u, int fa) {
  f[u] = fa;
  for (int v : g[u]) {
    if (v != fa) {
      o[u].insert(v), DFS1(v, u);
    }
  }
}
void Calc(int u, int tmp = 0) {
  if (o[u].size() == 0) {
    o[f[u]].erase(u);
    if (o[f[u]].size() == 1 && vis[f[u]] == 1) {
      Calc(f[u]);
    }
  } else if (o[u].size() == 1) {
    tot -= vis[u], tmp = *o[u].begin(), f[tmp] = f[u];
    o[f[u]].erase(u), o[f[u]].insert(tmp);
  } else {
    tot++, vis[u] = 1;
  }
}
int main() {
  freopen("tree.in", "r", stdin), freopen("tree.out", "w", stdout);
  cin >> n;
  for (int i = 1, u, v, w; i < n; i++) {
    cin >> u >> v >> w, w = w ? 1 : 0, e[u].push_back({v, w}), e[v].push_back({u, w});
  }
  for (int i = 1; i <= n; i++) {
    cin >> p[i];
  }
  for (int i = 1; i <= n; i++) {
    if (!c[i]) {
      cnt++, DFS(i);
    }
  }
  for (int i = 1; i <= n; i++) {
    if (!vis[c[p[i]]]) {
      vis[c[p[i]]] = 1, pre[i] = c[p[i]];
    }
  }
  for (int i = 1; i <= n; i++) {
    for (auto [j, w] : e[i]) {
      int u = c[i], v = c[j];
      (u > v) && (swap(u, v), 0);
      if (u != v) {
        if (s.find({u, v}) == s.end()) {
          s.insert({u, v}), g[u].push_back(v), g[v].push_back(u);
        }
      }
    }
  }
  DFS1(c[p[1]], 0);
  vis.reset(), ans[1] = 1;
  for (int i = n; i - 1; i--) {
    ans[i] = tot == 0, pre[i] && (Calc(pre[i]), 0);
  }
  for (int i = 1; i <= n; i++) {
    cout << ans[i];
  }
  return 0;
}

#D. 直径

一道巨大的 dp 题，不想写