2024/10/20 模拟赛总结

\(0+0+0+0=0\)，没考

#A. 袜子分配

直接大眼找规律，得到 \(n\) 双袜子期望为 \(\frac{n}{2n-1}\)

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

using namespace std;
using DB = long double;

DB n;

int main() {
  freopen("socks.in", "r", stdin), freopen("socks.out", "w", stdout);
  cin >> n, cout << fixed << setprecision(10) << n / (n + n - 1) << '\n';
  return 0;
}

#B. 艰难睡眠

有点像选种子的那题

枚举牛牛睡觉的时间，用 multiset 维护单调队列，像那道题差不多的方法查一下就可以了

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

using namespace std;

const int kMaxN = 5e3 + 5, kMaxM = 2e3 + 5;

int n, m, k, a[kMaxN], b[kMaxN], c[kMaxN][kMaxM << 1], f[kMaxN], sz, ans = 1e9;
multiset<int> s;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("sleep.in", "r", stdin), freopen("sleep.out", "w", stdout);
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i] >> b[i];
  }
  for (int i = 1; i <= n; i++) {
    if (k + b[i] > m) {
      return cout << "-1\n", 0;
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> c[i][j], c[i][j + m] = c[i][j];
    }
    sz = m - b[i] - k + 1, s.clear();
    for (int j = 1; j <= m << 1; j++) {
      s.insert(c[i][j]);
      if (s.size() == sz) {
        int e = (b[i] + j) % m == 0 ? m : (b[i] + j) % m;
        f[e] += *s.begin(), s.erase(s.find(c[i][j - sz + 1]));
        if (e == b[i] + sz - 1) {
          break;
        }
      }
    }
  }
  for (int i = 1; i <= m; i++) {
    ans = min(ans, f[i]);
  }
  cout << ans << '\n';
  return 0;
}

#C. 路径难题

考的就是建图

每条公交车线路建一个点，把这个点连向所有有向公交车线路的点连一条边

存下每个出租车线路的整数和余数，在 dij 时枚举接下来的点是否走公交车如果是，则把余数清零，否则加上并继续转移即可

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

using namespace std;
using LL = long long;

const int kMaxN = 2e5 + 5;

struct P {
  int x;
  LL f, g;
  LL Calc() const { return f + !!g; }
  bool operator<(const P &o) const {
    return Calc() != o.Calc() ? Calc() < o.Calc() : (f != o.f ? f < o.f : g < o.g);
  }
  bool operator>(const P &o) const {
    return Calc() != o.Calc() ? Calc() > o.Calc() : (f != o.f ? f > o.f : g > o.g);
  }
};

int n, m, k, r, qtot, sz;
LL f[kMaxN], g[kMaxN];
vector<pair<int, LL>> gr[kMaxN];
vector<int> vec;
priority_queue<P, vector<P>, greater<P>> q;

LL Solve(int s, int t) {
  for (; !q.empty(); q.pop()) {
  }
  q.push((P){s, 0, 0}), fill(f, f + kMaxN, 1e9), fill(g, g + kMaxN, 0), f[s] = g[s] = 0;
  for (P u; !q.empty();) {
    u = q.top(), q.pop();
    if ((P){u.x, f[u.x], g[u.x]} < u) {
      continue;
    }
    (u.x > sz) && (u.g && (u.f++, u.g = 0));
    for (auto [v, w] : gr[u.x]) {
      LL dis = u.g + w, cos = dis / r + u.f;
      dis %= r;
      if ((P){v, cos, dis} < (P){v, f[v], g[v]}) {
        q.push((P){v, cos, dis}), f[v] = cos, g[v] = dis;
      }
    }
  }
  return f[t] + !!g[t];
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("path.in", "r", stdin), freopen("path.out", "w", stdout);
  cin >> n >> m >> k >> r >> qtot, sz = n;
  for (int i = 1, u, v, w; i <= m; i++) {
    cin >> u >> v >> w, gr[u].push_back({v, w}), gr[v].push_back({u, w});
  }
  for (int i = 1, t, c; i <= k; i++, vec.clear()) {
    cin >> t >> c;
    for (int j = 1, in; j <= t; j++) {
      cin >> in, vec.push_back(in);
    }
    n += 2;
    for (int x : vec) {
      gr[x].push_back({n - 1, c * 1ll * r}), gr[n].push_back({x, 0});
    }
    gr[n - 1].push_back({n, 0});
  }
  for (int S, T; qtot; qtot--) {
    cin >> S >> T, cout << Solve(S, T) << '\n';
  }
  return 0;
}

#D. 牛半仙的妹子序列

不会吉司机