2024/10/07 模拟赛总结

\(20+55+25+0=100\)，压线拿到小饼干！

#A. A

可以发现 \(u_i=A,v_i=B,w_i=C\) 至少有一个成立，将这些点抽象到三位空间中。则原长方体一定被一个从 \((1,1,1)\) 出发的长方体打穿，但是似乎重叠部分比较难实现

对于从底打到顶的长方体，可以用后缀 \(\max\) 解决，然后原长方体就变成了阶梯状棱柱。然后横竖的操作就可以简化成一条线了，那么每一层剩下的数量可以直接计算

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

using namespace std;
using ull = unsigned long long;

const int kMaxN = 3e7 + 5;

int n, mx[kMaxN], mn[kMaxN], e[kMaxN], u[kMaxN], v[kMaxN], w[kMaxN], k[kMaxN], A, B, C;
__int128 p = 1, ans, cnt;

ull Rand(ull &k1, ull &k2) {
  ull k3 = k1, k4 = k2;
  k1 = k4;
  k3 ^= (k3 << 23);
  k2 = k3 ^ k4 ^ (k3 >> 17) ^ (k4 >> 26);
  return k2 + k4;
}
void GetData() {
  ull x, y;
  cin >> n >> A >> B >> C >> x >> y;
  for (int i = 1; i <= n; i++) {
    u[i] = Rand(x, y) % A + 1;
    v[i] = Rand(x, y) % B + 1;
    w[i] = Rand(x, y) % C + 1;
    if (Rand(x, y) % 3 == 0) u[i] = A;
    if (Rand(x, y) % 3 == 0) v[i] = B;
    if ((u[i] != A) && (v[i] != B)) w[i] = C;
  }
}
void print(__int128 pr) {
  (pr < 10) ? putchar(pr + '0') : (print(pr / 10), putchar((pr % 10) + '0'));
}

int main() {
  freopen("A.in", "r", stdin), freopen("A.out", "w", stdout);
  GetData();
  for (int i = 1; i <= n; i++) {
    if (w[i] == C) {
      e[u[i]] = max(e[u[i]], v[i]);
    } else if (u[i] == A) {
      mn[w[i]] = max(mn[w[i]], v[i]);
    } else if (v[i] == B) {
      mx[w[i]] = max(mx[w[i]], u[i]);
    }
  }
  for (int i = A; i; i--) {
    e[i] = max(e[i], e[i + 1]);
  }
  for (int i = C; i; i--) {
    mx[i] = max(mx[i], mx[i + 1]), mn[i] = max(mn[i], mn[i + 1]);
  }
  for (int i = 1, cur = A; i <= B; i++) {
    for (; cur && e[cur] < i; cur--) {
    }
    k[i] = cur;
  }
  for (int i = 1, lx = A, ly = B; i <= C; i++) {
    for (; lx > mx[i]; cnt += B - ly - max(0, e[lx] - ly), lx--) {
    }
    for (; ly > mn[i]; cnt += A - lx - max(0, k[ly] - lx), ly--) {
    }
    ans += cnt;
  }
  print(p * A * B * C - ans), cout << '\n';
  return 0;
}

#B. B

令 \(dp_{i,j}\) 为前 \(i\) 道工序有 \(j\) 个物品优于当前物品，由于每次只会删掉一个值，\(dp_{i,j}\) 只会更新到 \(dp_{i+1,j},dp_{i+1,j-1}\)，所以可以直接美剧当前物品大力转移即可

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

using namespace std;
using LL = long long;

const int kMaxN = 3e2 + 5;
const LL kP = 1e9 + 7;

int n;
LL p[kMaxN], ans, l[kMaxN][kMaxN], r[kMaxN][kMaxN], dp[kMaxN][kMaxN];

LL P(LL x, LL y, LL ret = 1) {
  for (; y; (y & 1) && ((ret *= x) %= kP), (x *= x) %= kP, y >>= 1) {
  }
  return ret;
}

int main() {
  freopen("B.in", "r", stdin), freopen("B.out", "w", stdout);
  cin >> n;
  for (int i = 1; i < n; i++) {
    cin >> p[i];
  }
  for (int i = 1; i < n; i++) {
    l[i][0] = 1;
    for (int j = 1; j <= n - i + 1; j++) {
      r[i][j] = l[i][j - 1] * (j == n - i + 1 ? 1 : p[i]) % kP;
      l[i][j] = l[i][j - 1] * (kP + 1 - p[i]) % kP;
    }
    for (int j = 2; j <= n - i + 1; j++) {
      (r[i][j] += r[i][j - 1]) %= kP;
    }
  }
  for (int i = 1; i <= n; i++) {
    fill(dp[0], dp[n + 2], 0), dp[1][i] = 1;
    for (int j = 1; j < n; j++) {
      for (int k = 1; k <= i; k++) {
        if (dp[j][k]) {
          (dp[j + 1][k - 1] += dp[j][k] * r[j][k - 1] % kP) %= kP;
          (dp[j + 1][k] += dp[j][k] * (kP + 1 - r[j][k]) % kP) %= kP;
        }
      }
    }
    (ans += i * dp[n][1] % kP) %= kP;
  }
  cout << ans << '\n';
  return 0;
}

#C. C

由于 \(b\) 单调不升，如果 \([l,r]\) 内 \(k\) 的出现次数小于 \(b_{r-l+1}\)，则 \([l,r]\) 的多有包含 \(k\) 的子区间一定不合法

所以我们可以对于每一个出现次数不够的数直接割开进行分治，但是这样复杂度可能会被卡

我们尽量让割开的点靠近中点就可以将复杂度降成 \(O(n\log n)\) 所以我们枚举所有要断开的点，只断开最靠近中点的一个即可

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

using namespace std;

const int kMaxN = 1e6 + 5;

int n, a[kMaxN], b[kMaxN], ans;
unordered_map<int, int> mp;

void Calc(int l, int r) {
  if (r < l || r - l + 1 <= ans) {
    for (int i = l; i <= r; i++) {
      mp[a[i]]--;
    }
    return;
  }
  if (r == l) {
    return mp[a[l]]--, (b[1] == 1) && (ans = max(ans, 1)), void();
  }
  int *p = &a[l], *q = &a[r], e = -1;
  for (; p <= q; p++, q--) {
    if (mp[*p] < b[r - l + 1]) {
      e = p - a;
      break;
    }
    if (mp[*q] < b[r - l + 1]) {
      e = q - a;
      break;
    }
  }
  if (!~e) {
    ans = max(ans, r - l + 1);
    for (int i = l; i <= r; i++) {
      mp[a[i]]--;
    }
    return;
  }
  if (e <= (l + r) / 2) {
    for (int i = l; i <= e; i++) {
      mp[a[i]]--;
    }
    Calc(e + 1, r);
    for (int i = l; i < e; i++) {
      mp[a[i]]++;
    }
    Calc(l, e - 1);
  } else {
    for (int i = e; i <= r; i++) {
      mp[a[i]]--;
    }
    Calc(l, e - 1);
    for (int i = e + 1; i <= r; i++) {
      mp[a[i]]++;
    }
    Calc(e + 1, r);
  }
}

int main() {
  freopen("C.in", "r", stdin), freopen("C.out", "w", stdout);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i], mp[a[i]]++;
  }
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
  }
  Calc(1, n);
  cout << ans << '\n';
  return 0;
}

#D. D

人机线段树合并区间，题解和 std 都没看懂，先咕咕咕