• 2022杭电多校（五）

    2022杭电多校（五）

    文章目录

    一、比赛小结

    比赛链接：Problems (hdu.edu.cn)

    二、题目分析及解法（基础题）

    1003、Slipper

    题目链接：Problem - 7187 (hdu.edu.cn)

    题意：

    给出一棵树，每个边的权均为 ω \omega ω ，魔法可以使得，层数差 k k k 的节点边权为 p p p

    题解：

    很简单的分层图题，常规思路是 每层多一个点+双向边 或 每层多两个点+单向边。

    设树的深度为 d d d ，在第 i i i 层 ( 1 ≤ i ≤ d ) (1\le i \le d) (1≤i≤d) 和第 i + 1 i+1 i+1 层中新增两个点 l i , r i , l i l_i, r_i, l_i li​,ri​,li​ ， 连向所有第 i + 1 i+1 i+1 层的点， r i r_i ri​ 连向所有第 i i i 层的点，对于原来树中所有的点，向 l d e p u + k − 1 l_{dep_u+k-1} ldepu​+k−1​ 连一条权为 p p p 单向边，向 r d e p u − k r_{dep_u-k} rdepu​−k​ 连一条权值为 p p p 的单向边，在修改后的图中跑 dijkstra 求 s s s 到 t t t 的最短路即可，复杂度 O ( n l o g n ) O(nlogn) O(nlogn) 。

    代码：

    #include 
#include 
#include 
#include 
using namespace std;
using ll = long long;

const int maxn = 1e6 + 5;
int e[maxn << 3][3], head[maxn << 2], tot = -1;
int dep[maxn << 2], maxdep = 0, n = 0, k = 0, p = 0, s = 0, t = 0;

void addEdge(int u, int v, int w) {
  e[++tot][0] = v;
  e[tot][1] = head[u];
  e[tot][2] = w;
  head[u] = tot;
}

void dfs(int u, int fa) {
  dep[u] = dep[fa] + 1;
  maxdep = max(maxdep, dep[u]);
  for (int i = head[u]; ~i; i = e[i][1]) {
    if (e[i][0] == fa) continue;
    dfs(e[i][0], u);
  }
}

ll dis[maxn << 2];
bool vis[maxn << 2];
void dijkstra() {
  memset(dis, 0x3f, sizeof(dis));
  memset(vis, false, sizeof(vis));
  dis[s] = 0;
  priority_queue<pair<ll, int>> pq;
  pq.emplace(0, s);
  while (!pq.empty()) {
    int u = pq.top().second;
    pq.pop();
    if (vis[u]) continue;
    vis[u] = true;
    for (int i = head[u]; ~i; i = e[i][1]) {
      int v = e[i][0], w = e[i][2];
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        pq.emplace(-dis[v], v);
      }
    }
  }
}

void solve() {
  memset(head, -1, sizeof(head));
  tot = -1, maxdep = 0;
  scanf("%d", &n);
  int u = 0, v = 0, w = 0;
  for (int i = 1; i <= n - 1; ++i) {
    scanf("%d %d %d", &u, &v, &w);
    addEdge(u, v, w), addEdge(v, u, w);
  }
  dep[0] = -1;
  dfs(1, 0);
  scanf("%d %d", &k, &p);
  for (int i = 1; i <= n; ++i) {
    if (dep[i] != 0) addEdge(n + 2 * dep[i] - 1, i, p);
    if (dep[i] != maxdep) addEdge(n + 2 * (dep[i] + 1), i, p);
    if (dep[i] + k <= maxdep) addEdge(i, n + 2 * (dep[i] + k) - 1, 0);
    if (dep[i] - k >= 0) addEdge(i, n + 2 * (dep[i] - k + 1), 0);
  }
  scanf("%d %d", &s, &t);
  dijkstra();
  printf("%lld\n", dis[t]);
}

int main() {
  int T = 0;
  scanf("%d", &T);
  for (int cas = 1; cas <= T; ++cas) solve();
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79

    1006、BBQ

    题目链接：Problem - 7190 (hdu.edu.cn)

    题意：

    定义 “组” 为形如 “abba” 这样的长为 4 的字符串，给定一个长为 n n n 的字符串，每次可以删除一个或增加一个字符，求将该字符串变为若干 “组” 连接的串的最小操作次数

    题解：

    我们可以对比初始串与结果串，发现其变换是由初始串中若干相连的 “块” 变换成了若干相连的 “组” ，其解空间预计不超过 O ( 8 n ) O(8n) O(8n) ，因此可以考虑 d p dp dp ，事实上，其解空间确实不超过 O ( 8 n ) O(8n) O(8n) ，当一个块长度超过 8 8 8 时便没有了意义，因此每个字符可以在不超过 8 8 8 的范围内有解

    具体地，其表达式可以写成： d p [ n ] = min ⁡ i = 1 7 ( d p [ n − i ] + c o s t ( n − u + 1 , n ) ) \displaystyle dp[n]=\min_{i=1}^{7}(dp[n-i] + cost(n-u+1, n)) dp[n]=i=1min7​(dp[n−i]+cost(n−u+1,n))

    代码：

    #include 
#include 

#include 

#define U unsigned
#define LL long long
#define UL U LL

int t[10];
int g[10][5];
char w[3000000];

void dfs(int n, int c, int idx) {
  int m = 9999999;
  if (n)
    for (int a = 1; a <= 7; a++)
      for (int b = 1; b <= 7; b++) {
        int p[5] = {0, a, b, b, a};
        memset(g, 1, sizeof g);
        for (int i = 0; i <= 4; i++) g[0][i] = i;
        for (int i = 0; i <= 7; i++) g[i][0] = i;
        for (int i = 1; i <= n; i++)
          for (int j = 1; j <= 4; j++)
            g[i][j] = std::min(
                std::min(g[i - 1][j] + 1, g[i - 1][j - 1] + (t[i] != p[j])),
                g[i][j - 1] + 1);
        if (g[n][4] < m) m = g[n][4];
      }
  if (n) w[idx] = m;
  if (n == 7) return;
  n++;
  for (int i = 1; i <= c; i++) {
    t[n] = i;
    dfs(n, c, idx * 8 + i);
  }
  t[n] = c + 1;
  dfs(n, c + 1, idx * 8 + c + 1);
}

char s[1000001];
int dp[1000001];
int last[26];
int pre[1000001];
void sol() {
  scanf("%s", s + 1);
  int n = strlen(s + 1);
  memset(dp + 1, 10, n * 4);
  memset(last, -1, sizeof last);

  for (int i = 1; i <= n; i++) {
    pre[i] = last[s[i] - 'a'];
    last[s[i] - 'a'] = i;
  }

  for (int i = 0; i < n; i++) {
    dp[i + 1] = std::min(dp[i + 1], dp[i] + 1);
    int cnt = 0;
    int idx = 0;
    int tmp[8];

    for (int j = 1; j <= 7 && i + j <= n; j++) {
      int c = s[i + j] - 'a';
      if (pre[i + j] <= i)
        idx = idx * 8 + (tmp[j] = ++cnt);
      else
        idx = idx * 8 + (tmp[j] = tmp[pre[i + j] - i]);
      dp[i + j] = std::min(dp[i + j], dp[i] + w[idx]);
    }
  }
  printf("%d\n", dp[n]);
}

int main() {
  dfs(0, 0, 0);
  int t;
  scanf("%d", &t);
  while (t--) sol();
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79

    1007、Count Set

    题目链接：Problem - 7191 (hdu.edu.cn)

    题意：

    给定 1 ∼ n 1 \sim n 1∼n 排列 p p p 和非负整数 k k k . 请计算 1 ∼ n 1 \sim n 1∼n 子集 T T T 的数量，满足|T| = k和 |P(T)∩T| ≤ 0 . P(T) = {y | y = px，x∈T}.

    题解：

    简单数学题，排列可以认为是若干个置换换的积，对于一个大小为 m m m 的环，可以在这个图中挑出若干个不相邻的点即可，具体地，选出 l l l 个这样的点的方案数为： ( m − k k ) + ( m − k − 1 k − 1 ) \displaystyle { m-k \choose k } + { m-k-1 \choose k-1 } (km−k​)+(k−1m−k−1​)

    最后在这些子图中一共挑出 k k k 个点即可。最后可以化成一个数学表达式（不可化简），一个简单的方法是 NTT 无脑合并就行

    代码：

    #include 
using namespace std;
using i64 = long long;
constexpr int mod = 998244353;
int norm(int x) {
  if (x < 0) {
    x += mod;
  }
  if (x >= mod) {
    x -= mod;
  }
  return x;
}
template <class T>
T power(T a, int b) {
  T res = 1;
  for (; b; b /= 2, a *= a) {
    if (b % 2) {
      res *= a;
    }
  }
  return res;
}

struct Z {
  int x;
  Z(int x = 0) : x(norm(x)) {}
  int val() const { return x; }
  Z operator-() const { return Z(norm(mod - x)); }
  Z inv() const {
    assert(x != 0);
    return power(*this, mod - 2);
  }
  Z &operator*=(const Z &rhs) {
    x = i64(x) * rhs.x % mod;
    return *this;
  }
  Z &operator+=(const Z &rhs) {
    x = norm(x + rhs.x);
    return *this;
  }
  Z &operator-=(const Z &rhs) {
    x = norm(x - rhs.x);
    return *this;
  }
  Z &operator/=(const Z &rhs) { return *this *= rhs.inv(); }
  friend Z operator*(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res *= rhs;
    return res;
  }
  friend Z operator+(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res += rhs;
    return res;
  }
  friend Z operator-(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res -= rhs;
    return res;
  }
  friend Z operator/(const Z &lhs, const Z &rhs) {
    Z res = lhs;
    res /= rhs;
    return res;
  }
  friend istream &operator>>(istream &is, Z &a) {
    i64 v;
    is >> v;
    a = Z(v);
    return is;
  }
  friend ostream &operator<<(ostream &os, const Z &a) { return os << a.val(); }
};
vector<int> rev;
vector<Z> roots{0, 1};
void dft(vector<Z> &a) {
  int n = a.size();
  if (int(rev.size()) != n) {
    int k = __builtin_ctz(n) - 1;
    rev.resize(n);
    for (int i = 0; i < n; i++) {
      rev[i] = rev[i >> 1] >> 1 | (i & 1) << k;
    }
  }
  for (int i = 0; i < n; i++) {
    if (rev[i] < i) {
      swap(a[i], a[rev[i]]);
    }
  }
  if (int(roots.size()) < n) {
    int k = __builtin_ctz(roots.size());
    roots.resize(n);
    while ((1 << k) < n) {
      Z e = power(Z(3), (mod - 1) >> (k + 1));
      for (int i = 1 << (k - 1); i < (1 << k); i++) {
        roots[i << 1] = roots[i];
        roots[i << 1 | 1] = roots[i] * e;
      }
      k++;
    }
  }
  for (int k = 1; k < n; k *= 2) {
    for (int i = 0; i < n; i += 2 * k) {
      for (int j = 0; j < k; j++) {
        Z u = a[i + j], v = a[i + j + k] * roots[k + j];
        a[i + j] = u + v, a[i + j + k] = u - v;
      }
    }
  }
}
void idft(vector<Z> &a) {
  int n = a.size();
  reverse(a.begin() + 1, a.end());
  dft(a);
  Z inv = (1 - mod) / n;
  for (int i = 0; i < n; i++) {
    a[i] *= inv;
  }
}
struct Poly {
  vector<Z> a;
  Poly() {}
  Poly(const vector<Z> &a) : a(a) {}
  Poly(const initializer_list<Z> &a) : a(a) {}
  int size() const { return a.size(); }
  void resize(int n) { a.resize(n); }
  Z operator[](int idx) const {
    if (idx < size()) {
      return a[idx];
    } else {
      return 0;
    }
  }
  Z &operator[](int idx) { return a[idx]; }
  Poly mulxk(int k) const {
    auto b = a;
    b.insert(b.begin(), k, 0);
    return Poly(b);
  }
  Poly modxk(int k) const {
    k = min(k, size());
    return Poly(vector<Z>(a.begin(), a.begin() + k));
  }
  Poly divxk(int k) const {
    if (size() <= k) {
      return Poly();
    }
    return Poly(vector<Z>(a.begin() + k, a.end()));
  }
  friend Poly operator+(const Poly &a, const Poly &b) {
    vector<Z> res(max(a.size(), b.size()));
    for (int i = 0; i < int(res.size()); i++) {
      res[i] = a[i] + b[i];
    }
    return Poly(res);
  }
  friend Poly operator-(const Poly &a, const Poly &b) {
    vector<Z> res(max(a.size(), b.size()));
    for (int i = 0; i < int(res.size()); i++) {
      res[i] = a[i] - b[i];
    }
    return Poly(res);
  }
  friend Poly operator*(Poly a, Poly b) {
    if (a.size() == 0 || b.size() == 0) {
      return Poly();
    }
    int sz = 1, tot = min(5000000, a.size() + b.size() - 1);
    while (sz < tot) {
      sz *= 2;
    }
    a.a.resize(sz);
    b.a.resize(sz);
    dft(a.a);
    dft(b.a);
    for (int i = 0; i < sz; i++) {
      a.a[i] = a[i] * b[i];
    }
    idft(a.a);
    a.resize(tot);
    return a;
  }
  friend Poly operator*(Z a, Poly b) {
    for (int i = 0; i < int(b.size()); i++) {
      b[i] *= a;
    }
    return b;
  }
  friend Poly operator*(Poly a, Z b) {
    for (int i = 0; i < int(a.size()); i++) {
      a[i] *= b;
    }
    return a;
  }
  Poly &operator+=(Poly b) { return (*this) = (*this) + b; }
  Poly &operator-=(Poly b) { return (*this) = (*this) - b; }
  Poly &operator*=(Poly b) { return (*this) = (*this) * b; }
  Poly deriv() const {
    if (a.empty()) {
      return Poly();
    }
    vector<Z> res(size() - 1);
    for (int i = 0; i < size() - 1; i++) {
      res[i] = (i + 1) * a[i + 1];
    }
    return Poly(res);
  }
  Poly integr() const {
    vector<Z> res(size() + 1);
    for (int i = 0; i < size(); i++) {
      res[i + 1] = a[i] / (i + 1);
    }
    return Poly(res);
  }
  Poly inv(int m) const {
    Poly x{a[0].inv()};
    int k = 1;
    while (k < m) {
      k *= 2;
      x = (x * (Poly{2} - modxk(k) * x)).modxk(k);
    }
    return x.modxk(m);
  }
  Poly log(int m) const { return (deriv() * inv(m)).integr().modxk(m); }
  Poly exp(int m) const {
    Poly x{1};
    int k = 1;
    while (k < m) {
      k *= 2;
      x = (x * (Poly{1} - x.log(k) + modxk(k))).modxk(k);
    }
    return x.modxk(m);
  }
  Poly pow(int k, int m) const {
    int i = 0;
    while (i < size() && a[i].val() == 0) {
      i++;
    }
    if (i == size() || 1LL * i * k >= m) {
      return Poly(vector<Z>(m));
    }
    Z v = a[i];
    auto f = divxk(i) * v.inv();
    return (f.log(m - i * k) * k).exp(m - i * k).mulxk(i * k) * power(v, k);
  }
  Poly sqrt(int m) const {
    Poly x{1};
    int k = 1;
    while (k < m) {
      k *= 2;
      x = (x + (modxk(k) * x.inv(k)).modxk(k)) * ((mod + 1) / 2);
    }
    return x.modxk(m);
  }
  Poly mulT(Poly b) const {
    if (b.size() == 0) {
      return Poly();
    }
    int n = b.size();
    reverse(b.a.begin(), b.a.end());
    return ((*this) * b).divxk(n - 1);
  }
};
vector<Z> fact, infact;
void init(int n) {
  fact.resize(n + 1), infact.resize(n + 1);
  fact[0] = infact[0] = 1;
  for (int i = 1; i <= n; i++) {
    fact[i] = fact[i - 1] * i;
  }
  infact[n] = fact[n].inv();
  for (int i = n; i; i--) {
    infact[i - 1] = infact[i] * i;
  }
}
Z C(int n, int m) {
  if (n < 0 || m < 0 || n < m) return Z(0);
  return fact[n] * infact[n - m] * infact[m];
}

struct DSU {
  vector<int> p, Size;
  DSU(int n) : p(n), Size(n, 1) { iota(p.begin(), p.end(), 0); }
  int find(int x) { return p[x] == x ? p[x] : p[x] = find(p[x]); }
  bool same(int u, int v) { return find(u) == find(v); }
  void merge(int u, int v) {
    u = find(u), v = find(v);
    if (u != v) {
      Size[v] += Size[u];
      p[u] = v;
    }
  }
};
void solve() {
  int n, k;
  cin >> n >> k;
  DSU p(n + 1);
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    p.merge(i, a[i]);
  }
  vector<vector<Z>> f(n + 1);
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (p.find(i) == i) {
      cnt++;
      f[cnt].resize(p.Size[i] / 2 + 1);
      for (int j = 0; j <= p.Size[i] / 2; j++) {
        f[cnt][j] = C(p.Size[i] - j - 1, j - 1) + C(p.Size[i] - j, j);
      }
    }
  }
  function<Poly(int, int)> dc = [&](int l, int r) {
    if (l == r) return Poly(f[l]);
    int mid = l + r >> 1;
    return dc(l, mid) * dc(mid + 1, r);
  };
  Poly ans = dc(1, cnt);
  ans.resize(k + 1);
  cout << ans[k] << "\n";
}
signed main() {
  init(1e7);
  cin.tie(0)->sync_with_stdio(0);
  int T;
  cin >> T;
  while (T--) {
    solve();
  }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156
    • 157
    • 158
    • 159
    • 160
    • 161
    • 162
    • 163
    • 164
    • 165
    • 166
    • 167
    • 168
    • 169
    • 170
    • 171
    • 172
    • 173
    • 174
    • 175
    • 176
    • 177
    • 178
    • 179
    • 180
    • 181
    • 182
    • 183
    • 184
    • 185
    • 186
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332

    1010、Bragging Dice

    题目链接：Problem - 7194 (hdu.edu.cn)

    题意：

    两个人博弈，可以claim 或 chanllenge

    题解：

    输出 “Win!” 即可，其实题意有点模糊，先手都能claim出

    最大的 x 个 y 。

    代码：

    #include 
using namespace std;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int T;
  scanf("%d", &T);
  int n, x;
  while (T--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &x);
    for (int i = 1; i <= n; ++i) scanf("%d", &x);
    puts("Win!");
  }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15

    1012、Buy Figurines

    题目链接：Problem - 7196 (hdu.edu.cn)

    题意：

    一些人去商店排队，排成若干对，每人有起始时间和购买时间，求最后一个人购买完毕的时间

    题解：

    数据结构题，快速维护对应信息即可，自己想了一个线段树方法，其实这题也是挺常规的，答案用 set 维护了 queue ，挺逆天的高科技，看来需要多多学习 STL

    代码：

    线段树版：

    #include 
#define int long long
using namespace std;
const int maxn = 2e5 + 5;
int n, m;
int ans;
struct segtree {
  int l, r;
  int num;    // 人数
  int minid;  // 人数最少的id
  int late;   // 人数最少的id的队列最晚结束时间
} t[maxn << 2];
struct node {
  int st, end;  // 每个人的开始和结束时间
  int dui;      // 每个人的队列id
  bool operator>(const node &rhs) const { return end > rhs.end; }
};
struct people {
  int a, s;
} p[maxn];
void build(int u, int l, int r) {
  t[u].l = l, t[u].r = r;
  if (l == r) {
    t[u].num = 0;
    t[u].minid = l;
    t[u].late = 0;
    return;
  }
  int mid = (l + r) >> 1;
  build(u << 1, l, mid);
  build(u << 1 | 1, mid + 1, r);
  int lnum = t[u << 1].num, rnum = t[u << 1 | 1].num;
  t[u].num = min(lnum, rnum);
  t[u].minid = lnum <= rnum ? t[u << 1].minid : t[u << 1 | 1].minid;
  t[u].late = lnum <= rnum ? t[u << 1].late : t[u << 1 | 1].late;
}
// 让编号为 id 的队列增加 x 人，结束时间增加 val
void update(int u, int id, int x, int val) {
  if (t[u].l == id && t[u].r == id) {
    t[u].num += x;
    t[u].late += val;
    return;
  }
  int mid = (t[u].l + t[u].r) >> 1;
  if (id <= mid)
    update(u << 1, id, x, val);
  else
    update(u << 1 | 1, id, x, val);
  int lnum = t[u << 1].num, rnum = t[u << 1 | 1].num;
  t[u].num = min(lnum, rnum);
  t[u].minid = lnum <= rnum ? t[u << 1].minid : t[u << 1 | 1].minid;
  t[u].late = lnum <= rnum ? t[u << 1].late : t[u << 1 | 1].late;
}
// 查询队列人数最少的队列id
int query1(int u) { return t[u].minid; }
// 查询队列人数最少的队列id的结束时间
int query2(int u) { return t[u].late; }
signed main() {
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  int _t;
  cin >> _t;
  while (_t--) {
    ans = 0;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> p[i].a >> p[i].s;
    sort(p + 1, p + n + 1, [](people u, people v) { return u.a < v.a; });
    build(1, 1, m);
    priority_queue<node, vector<node>, greater<node> > pq;
    for (int i = 1; i <= n; i++) {
      while (pq.size() && pq.top().end <= p[i].a) {
        node cur = pq.top();
        update(1, cur.dui, -1, 0);
        pq.pop();
      }
      int id = query1(1), time = query2(1);
      node now = {max(time, p[i].a), max(time, p[i].a) + p[i].s, id};
      // printf("%lld %lld %lld %lld\n", id, time, now.st, now.end);
      ans = max(ans, now.end);
      pq.push(now);
      update(1, id, 1, now.end - time);
    }
    cout << ans << endl;
  }
  return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88

    STL 版：

    #include
using namespace std;
using ll = long long;
const int N= 2e5 + 5;
struct Data { int arrival, spent; }data[N];
struct Timeline {
    ll time; int type, id;
    Timeline(ll _time = 0, int _type = 0, int _id = 0) :
        time(_time), type(_type), id(_id) {}
    // type = 0 for departure, type = 1 for arrival
    bool operator < (const Timeline &t) const {
        if(time != t.time) return time > t.time;
        return type > t.type;
    }
};
priority_queue<Timeline> Tl;
struct Queue {
    int num, id;
    Queue(int _num = 0, int _id = 0) :
        num(_num), id(_id) {}
    bool operator < (const Queue &t) const {
        if(num == t.num) return id < t.id;
        return num < t.num;
    }
}q[N];
set<Queue> Que;
int T, n, m, Queue_select[N];
ll ans, Last[N];
int main() {
    // freopen("test.in", "r", stdin);
    // freopen("test.out", "w", stdout);
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i)
            scanf("%d%d", &data[i].arrival, &data[i].spent);
        for(int i = 1; i <= n; ++i)
            Tl.push(Timeline(data[i].arrival, 1, i));
        Que.clear();
        for(int i = 1; i <= m; ++i) {
            q[i].num = 0, q[i].id = i;
            Que.insert(q[i]);
            Last[i] = 0;
        }
        while(!Tl.empty()) {
            auto tl = Tl.top(); Tl.pop();
            ll time = tl.time; int type = tl.type, id = tl.id;
            if(type == 0) {
                int qid = Queue_select[id];
                Que.erase(Queue(q[qid].num, q[qid].id));
                Que.insert(Queue(--q[qid].num, q[qid].id));
            }
            else {
                auto que = *Que.begin();
                int num = que.num, qid = que.id;
                Que.erase(que);
                Queue_select[id] = qid;
                if(num == 0) Last[qid] = time + data[id].spent;
                else Last[qid] += data[id].spent;
                q[qid].num++; que.num++;
                Que.insert(que);
                Tl.push(Timeline(Last[qid], 0, id));
            }
        }
        ans = 0;
        for(int i = 1; i <= m; ++i) ans = max(ans, Last[i]);
        printf("%lld\n", ans);
    }

    return 0;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71

    三、题目分析及解法（进阶题）

    这次不会做的好多X

    1001、

    1002、

    1004、

    1005、

    1008、

    1009、

    1011、

  • 相关阅读:
    JAVA面试题（精选java面试题、最最基础java面试题目、java面试必备）
    C++函数如何具有多个返回值？
    玩转MySQL：你知道什么是表分区吗
    【数据结构】堆排序与TopK问题
    电脑键盘各按键的作用及常用的快捷键总结
    【数据挖掘】2022年深信服科技机器学习工程师笔试
    基站天线交叉极化比测量的不确定度评定
    Hadoop超详细入门（一）介绍及安装
    想找一个英文的二元分类数据集，类似sst2这种
    自定义注解实现入参校验
  • 原文地址：https://blog.csdn.net/m0_54646258/article/details/126971707