251115noip模拟赛总结

wendywu · 2025-11-15 16:15:31 · 个人记录

80 + 100 + 20 + 24 = 224：）
没想到T2都过了，结果T1炸了qwqwqwqwqwq
wssb！！！

A - mexdnc

wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wszrr！！！

最初的序列的mex叫做mm

如果m = 0就判一下有没有0

如果m < mm，就输出2

如果m = mm，就输出1

如果m >最大能搞出来的，就输出-1

然后就贪心地分出mex最大的，在m里面减掉

但是这样会炸，所以要把每次选的最大的的mex值预处理出来，作前缀和，然后二分

然后我就通过了所有的样例，提交

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 1e5 + 5;

LL t, n, q, a[N], b[N][3];

int main () {
  // freopen("mexdnc2.in", "r", stdin);
  // freopen("mexdnc.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  for (cin >> t; t--;) {
    cin >> n >> q;
    fill(a, a + n + 1, 0);
    for (int i = 1, aa, bb; i <= n; i++) {
      cin >> aa >> bb;
      if (aa > n) continue;
      a[aa] = bb;
      if (aa != 0) {
        a[aa] = min(a[aa], a[aa - 1]);
      }
    }
    a[n + 1] = 0;
    int cnt = 0;
    for (LL i = n; i >= 0; i--) {
      if (a[i] > a[i + 1]) {
        cnt++;
        b[cnt][0] = b[cnt - 1][0] + (i + 1) * (a[i] - a[i + 1]);
        b[cnt][1] = b[cnt - 1][1] + a[i] - a[i + 1];
        b[cnt][2] = i + 1;
        // cout << b[cnt][0] << ' ' << b[cnt][1] << '\n';
      }
    }
    for (LL m; q--;) {
      cin >> m;
      if (m == 0) {
        if (a[0]) {
          cout << "-1\n";
        } else {
          cout << "1\n";
        }
        continue;
      }
      if (m < b[1][0] / b[1][1]) {
        cout << "2\n";
        continue;
      }
      if (m == b[1][0] / b[1][1]) {
        cout << "1\n";
        continue;
      }
      if (b[cnt][0] < m) {
        cout << "-1\n";
        continue;
      }
      if (b[cnt][0] == m) {
        cout << b[cnt][1] << '\n';
        continue;
      }
      int l = 1, r = cnt, qwq = cnt;
      while (l <= r) {
        int mid = l + r >> 1;
        if (b[mid][0] > m) {
          qwq = mid;
          r = mid - 1;
        } else {
          l = mid + 1;
        }
      }
      LL tmp = (m - b[qwq - 1][0]) / b[qwq][2] + ((m - b[qwq - 1][0]) % b[qwq][2] ? 1 : 0);
      tmp += b[qwq - 1][1];
      cout << tmp << '\n';
    }
  }
  return 0;
}

获得了高达80pts的高分！！！（全班第5低qwq

然后发现是漏了一种情况，就是没有0但m > 0
加了一个

if (!a[0]) {
  cout << "-1\n";
  continue;
}

就过了qwq

wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wssb！！！
wszrr！！
wszrr！！
wszrr！！
wszrr！！
wszrr！！

B - guess

死磕了2h终于写出来了：）

看完题之后有20min完全不知道出题人在说什么

终于看懂了题意之后完全没有烧烤的方向。然后突然想到了区间dp，但是看到数据范围就直接放弃了这个想法

但是区间dp是唯一的思路，直接放弃不太好，还是觉得像dp。于是就想到，每个区间有用的信息其实只有长度，和从哪一端进入区间

所以设计状态f[i][0/1]表示在一个长度为i的区间内，从左端/右端进入，最少花多少代价找到最难找的点

转移就是：

f[i][0] = min(f[i][0], max(f[j][1], f[i - j][0]) + d[j]);
f[i][1] = min(f[i][1], max(f[j][0], f[i - j][1]) + d[j]);

但是脑子已经被T2榨干了，导致当我正确理解题意时已经只剩80min了qwq

T2都烧烤了那么久，T3要是能过我就是zrr，所以直接打纯暴力

犹豫了1s改用树剖还是用倍增求LCA，树剖代码太长，但是当初学倍增LCA的恐怖经历最终击败了我

树剖，启动！

但是写的时候我感觉我就是个zrr，就求个LCA写了93行qwq

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 2e5 + 5;

LL n, f[N * 2], d[N], son[N], top[N], fa[N];
LL a[2][25], mod, rt, t, sz[N];
vector <int> v[N];

void dfs1 (int x, int ff) {
  fa[x] = ff;
  d[x] = d[ff] + 1;
  sz[x] = 1;
  son[x] = 0;
  for (int i : v[x]) {
    if (i == ff) continue;
    dfs1(i, x);
    sz[x] += sz[i];
    if (sz[i] > sz[son[x]]) {
      son[x] = i;
    }
  }
}

void dfs2 (int x, int t) {
  // cout << x << ' ' << t << '\n';
  top[x] = t;
  if (son[x]) {
    dfs2(son[x], t);
  }
  for (int i : v[x]) {
    if (i == fa[x] || i == son[x]) continue;
    dfs2(i, i);
  }
}

void qwq () {
  for (int i = 1; i <= n * 2; i++) {
    f[i] = 1;
    for (int j = 0; j < 21; j++) {
      f[i] *= a[(i >> j) & 1][j];
      f[i] %= mod;
    }
  }
}

int lca (int x, int y) {
  for (; top[x] != top[y];) {
    if (d[top[x]] < d[top[y]]) swap(x, y);
    x = fa[top[x]];
  }
  return d[x] < d[y] ? x : y;
}

int main () {
  // freopen("tree3.in", "r", stdin);
  // freopen("tree.out", "w", stdout);
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  for (int i = 1, x, y; i < n; i++) {
    cin >> x >> y;
    v[x].emplace_back(y);
    v[y].emplace_back(x);
  }
  for (cin >> t; t--;) {
    cin >> rt >> mod;
    for (int i = 0; i < 2; i++) {
      for (int j = 0; j <= 20; j++) {
        cin >> a[i][j];
      }
    }
    qwq();
    dfs1(rt, 0);
    // for (int i = 1; i <= n; i++) {
    //   cout << sz[i] << ' ' << son[i] << ' ' << fa[i] << '\n';
    // }
    dfs2(rt, rt);
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
      LL s = 0;
      for (int j = 1; j <= n; j++) {
        s += f[j + d[lca(i, j)]];
        s %= mod;
      }
      s *= i;
      ans ^= s;
    }
    cout << ans << '\n';
  }
  return 0;
}

还是树剖写起来顺手：）

用倍增的都是zrr

D - miss

哎呀，只剩40min了！

直接写特殊性质，因为奇数位置始终有棋子，所以答案会乘2^{(n + 1)/2}

然后偶数位可以随便动，就算一下C的前缀和就好了

#include <bits/stdc++.h>
#define LL long long

using namespace std;

const int N = 5e5 + 5, mod = 1e9 + 7;

LL n, q, qwq[N][2], c[N];
string s;

LL qpow (LL x, LL y) {
  LL ret = 1;
  for (; y; y >>= 1) {
    if (y & 1) {
      (ret *= x) %= mod;
    }
    (x *= x) %= mod;
  }
  return ret;
}

LL C (LL x, LL y) {
  return qwq[x][0] * qwq[x - y][1] % mod * qwq[y][1] % mod;
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> q >> s;
  s = ' ' + s;
  LL sum = 0;
  for (int i = 1; i <= n; i++) {
    if (i & 1) continue;
    sum += s[i] - '0';
  }
  qwq[0][0] = qwq[0][1] = 1;
  for (LL i = 1; i <= n; i++) {
    qwq[i][0] = qwq[i - 1][0] * i % mod;
    qwq[i][1] = qpow(qwq[i][0], mod - 2);
  }
  for (int i = 0; i <= n / 2; i++) {
    c[i] = C(n / 2, i);
    c[i] += c[i - 1];
    c[i] %= mod;
  }
  LL tmp = qpow(2, (n + 1) / 2);
  cout << tmp * c[sum] % mod << '\n';
  for (int x; q--;) {
    cin >> x;
    if (s[x] == '0') {
      s[x] = '1';
      sum++;
    } else {
      s[x] = '0';
      sum--;
    }
    cout << tmp * c[sum] % mod << '\n';
  }
  return 0;
}

T1，漏掉了一种情况

T2，对最短路算法的时间复杂度不熟