2024/10/02 模拟赛总结

暴力挂惨了，\(0+0+5+0=5\)

#A. 躲避技能

评价：人机高精度

由于边权是正数，多走一条边一定更劣，所以能在子树内解决的就尽量不要出来

那么对于每一条边，它被遍历的次数是子树内起点与终点数量之差

直接枚举每一条边，算答案即可

人机高精度

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

using namespace std;
using LL = long long;

const int kL = 2e2 + 5, kMaxN = 1e5 + 5;

int n, m, s[kMaxN], f[kMaxN], e[kMaxN][kL], in[kL], ans[kMaxN], r;
string S;
vector<pair<int, int>> g[kMaxN];

void DFS(int u, int fa) {
  for (auto [v, i] : g[u]) {
    if (v != fa) {
      DFS(v, u), f[u] += f[v], f[v] = abs(f[v]);
      for (int j = 0; j <= 100; j++) {
        ans[j] += f[v] * e[i][j];
      }
    }
  }
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("skill.in", "r", stdin), freopen("skill.out", "w", stdout);
  cin >> n >> m;
  for (int i = 1, x; i <= m; i++) {
    cin >> x, f[x]++;
  }
  for (int i = 1, x; i <= m; i++) {
    cin >> x, f[x]--;
  }
  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v >> S, g[u].push_back({v, i}), g[v].push_back({u, i});
    for (int j = 0; j < S.size(); j++) {
      e[i][j] = S[j] - '0';
    }
  }
  DFS(1, 0);
  for (int i = 0; i < kL - 2; i++) {
    ans[i + 1] += ans[i] / 10, ans[i] %= 10;
  }
  for (int i = kL - 1; ~i; i--) {
    if (ans[i]) {
      r = i;
      break;
    }
  }
  for (int i = r; ~i; i--) {
    cout << ans[i];
  }
  cout << '\n';
  return 0;
}

#B. 奶茶兑换券

评价：人机双指针

都有无限张卷还管有没有浪费

列出两个值组合出来浪费的值：\((m-((a_i+a_j) \bmod m))\bmod m\)，显然所有 \(a_i\) 都可以更新为 \(a_i\bmod m\)。当这个两个数都小于 \(\frac m2\) 时，浪费的钱是直接相加。都大于的时候浪费的钱是相加后减去 \(m\)

那么最后答案就是所有取模后的 \(a_i\) 相加后减去的几个 \(m\)。然后就是要尽量多的凑齐和大于 \(m\) 的数，双指针例题

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

using namespace std;
using LL = long long;
using Pll = pair<LL, LL>;

const int kMaxN = 1e5 + 5;

int n, m;
LL ans, l, r;
Pll a[kMaxN];

int main() {
  freopen("tea.in", "r", stdin), freopen("tea.out", "w", stdout);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].first >> a[i].second, a[i].second %= m;
    if (!a[i].second) {
      n--, i--;
      continue;
    }
    ans += a[i].first * (m - a[i].second);
  }
  sort(a + 1, a + n + 1, [](Pll l, Pll r) { return l.second < r.second; }), l = 1, r = n;
  for (; l < r;) {
    for (; a[l].second + a[r].second > m; r--) {
    }
    LL k = min(a[l].first, a[r].first);
    a[l].first -= k, a[r].first -= k, ans -= k * m;
    (a[l].first == 0) && (l++), (a[r].first == 0) && (r--);
  }
  (a[l].second * 2 < m) && (ans -= a[l].first / 2 * m);
  cout << ans << '\n';
  return 0;
}

#C. 帮助

评价：人机二分

令 \(g_{i,j}\) 表示成绩为 \(j\) 且愿意帮助成绩为 \(i\) 的人所做题目数量之和

递推式为 \(g_{i,j}=g_{i-1,j}\displaystyle\sum_{c_p=i\cap t_p=j}f_p-\displaystyle\sum_{d_p=i-1\cap t_p=j} f_p\)

所以我们排序然后离散化，找到上式的两个断点，用 fenwick tree 维护并递推 \(g\) 值即可

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

using namespace std;
using LL = long long;
#define int long long

const int kMaxN = 1e5 + 5;

struct P {
  LL a[5], e, f, id, l, r;
  bool operator<(const P &o) const {
    return f < o.f;
  }
};
struct T {
  int tot, c[kMaxN << 3];
  int L(int x) { return x & -x; }
  void Update(int x, LL k) {
    for (; x <= tot + 1; c[x] += k, x += L(x)) {
    }
  }
  LL Query(int x, LL ret = 0) {
    for (; x; ret += c[x], x -= L(x)) {
    }
    return ret;
  }
};

int n;
LL u[kMaxN << 3], c[kMaxN];
vector<int> L[kMaxN], R[kMaxN];
T tr;
P w[kMaxN];

signed main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("help.in", "r", stdin), freopen("help.out", "w", stdout);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> w[i].e;
  }
  for (int i = 1; i <= n; i++) {
    cin >> w[i].f, w[i].id = i, u[5 * i] = w[i].f;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 4; j++) {
      cin >> w[i].a[j];
      u[5 * i - j] = w[i].a[j];
    }
  }
  sort(u + 1, u + 5 * n + 1), tr.tot = unique(u + 1, u + 5 * n + 1) - u - 1;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= 4; j++) {
      w[i].a[j] = lower_bound(u + 1, u + tr.tot + 1, w[i].a[j]) - u;
    }
    w[i].f = lower_bound(u + 1, u + tr.tot + 1, w[i].f) - u;
  }
  sort(w + 1, w + n + 1);
  for (int i = 1; i <= n; i++) {
    L[lower_bound(w + 1, w + n + 1, (P){{0, 0, 0, 0, 0}, 0, w[i].a[1], 0, 0, 0}) - w - 1].push_back(i);
    R[upper_bound(w + 1, w + n + 1, (P){{0, 0, 0, 0, 0}, 0, w[i].a[2], 0, 0, 0}) - w - 1].push_back(i);
  }
  for (int i = 0; i <= n; i++) {
    for (LL j : L[i]) {
      w[j].l = tr.Query(w[j].f);
    }
    for (int j : R[i]) {
      w[j].r = tr.Query(w[j].f);
    }
    (i != n) && (tr.Update(w[i + 1].a[3], w[i + 1].e), tr.Update(w[i + 1].a[4] + 1, -w[i + 1].e), 0);
  }
  for (int i = 1; i <= n; i++) {
    c[w[i].id] = w[i].r - w[i].l;
    if (w[i].f < w[i].a[1] || w[i].f > w[i].a[2] || w[i].f < w[i].a[3] || w[i].f > w[i].a[4]) {
      c[w[i].id] += w[i].e;
    }
  }
  for (int i = 1; i <= n; i++) {
    cout << c[i] << ' ';
  }
  cout << '\n';
  return 0;
}

#D. 神奇的变换

评价：人机数论分块

std 写的比 poker 还长，先咕咕咕