2024/10/21 模拟赛总结

\(100+50+0+5=155\)，T3 三目没打括号太爽了

#A. 串串串

基本上就是前缀异或和板子

交换两个 \(0,1\) 不会改变奇偶性，所以可以直接疑惑判断

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

using namespace std;

const int kMaxN = 2e5 + 5;

int n, m, q, l1, r1, l2, r2, f[kMaxN], g[kMaxN];
string s, t;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("string.in", "r", stdin), freopen("string.out", "w", stdout);
  cin >> n >> m >> s >> t >> q, s = ' ' + s, t = ' ' + t;
  for (int i = 1; i <= n; i++) {
    f[i] = f[i - 1] ^ (s[i] - '0');
  }
  for (int i = 1; i <= m; i++) {
    g[i] = g[i - 1] ^ (t[i] - '0');
  }
  for (; q; q--) {
    cin >> l1 >> r1 >> l2 >> r2;
    cout << (f[r1] ^ f[l1 - 1] ^ g[r2] ^ g[l2 - 1]) << '\n';
  }
  return 0;
}

#B. 方格计数

考虑只需要枚举每条从原点的所有直线，然后直接向下向右移

于是就可以直接枚举步数上 dp 即可

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

using namespace std;
using LL = long long;
using DB = double;

const LL kP = 1e9 + 7;
const int kMaxN = 50 + 2, kMaxM = 500 + 2;

LL t, n, w, h, d, ans, dp[kMaxM][kMaxN], g, l, r;

DB dis(DB x, DB y, DB X, DB Y) {
  return sqrt((x - X) * (x - X) + (y - Y) * (y - Y));
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  freopen("count.in", "r", stdin), freopen("count.out", "w", stdout);
  for (cin >> t; t; t--, ans = 0) {
    cin >> n >> w >> h >> d;
    for (int x = 0; x <= h; x++) {
      for (int y = 0; y <= w; y++) {
        if (x == 0 && y == 0) {
          if (n == 1) {
            ans += (h + 1) * (w + 1);
          }
          continue;
        }
        if (__gcd(x, y) == 1) {
          LL s = min(1.0 * h / x, 1.0 * w / y);
          dp[0][1] = 1;
          for (int i = 1; i <= s; i++) {
            LL ls = floor(i - d * 1.0 / dis(0, 0, x, y));
            for (int j = 0; j <= ls; j++) {
              for (int k = 1; k <= n; k++) {
                (dp[i][k] += dp[j][k - 1]) %= kP;
              }
            }
          }
          for (int i = 1; i <= s; i++) {
            (ans += (dp[i][n] * (1 + (x && y)) * ((h - i * x + 1) % kP)) * (w - i * y + 1) % kP) %= kP;
          }
          fill(dp[1], dp[s + 1], 0);
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

#C. 树数树

几乎是可并堆板子，直接 DFS 乱合并就可以了

// BLuemoon_
#include <bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>

using namespace std;
using namespace __gnu_pbds;

const int kMaxN = 1e5 + 5;

int t, n;
vector<int> g[kMaxN];
__gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag> q[kMaxN];

void DFS(int u, int fa, int ret = 1) {
  for (int v : g[u]) {
    if (v != fa) {
      DFS(v, u), q[u].join(q[v]), q[v].clear();
    }
  }
  if (q[u].empty()) {
    q[u].push(1);
    return;
  }
  ret += q[u].top(), q[u].pop();
  if (q[u].empty()) {
    q[u].push(ret);
    return;
  }
  ret += q[u].top(), q[u].pop();
  q[u].push(ret);
}

int main() {
  freopen("tree.in", "r", stdin), freopen("tree.out", "w", stdout);
  for (cin >> t; t; t--) {
    cin >> n;
    for (int i = 1, u, v; i < n; i++) {
      cin >> u >> v;
      g[u].push_back(v), g[v].push_back(u);
    }
    DFS(1, 0);
    cout << q[1].top() << '\n';
    for (int i = 1; i <= n; i++) {
      g[i].clear(), q[i].clear();
    }
  }
  return 0;
}

#D. 序列

不会 BM 算法/kk/kk