专栏文章

2025-11-15 NOIP模拟赛总结

lliuyi0905
生活·游记参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min7mhou
此快照首次捕获于
2025/12/01 21:53
3 个月前
此快照最后确认于
2025/12/01 21:53
3 个月前
查看原文

前言

炸了。50+0+20+0=7050 + 0 + 20 + 0 = 70 😭 还好不是最后一名
打的洛谷比赛，【LGR-250】洛谷 NOIP 2025 模拟赛，感觉要掉等级分了呜呜呜，都怪 cutezrr

A

最开始看了好久没发现做法，后来想了一下才发现有单调性。
可以设 f(x)f(x) 表示将原序列分成 xx 段可以得到的最大 mex⁡\operatorname{mex} 和。很显然，对 mex⁡\operatorname{mex} 和为 ∀m∈[1,f(x)]\forall m \in [1, f(x)] 都必定可以用 xx 段求出来（一点也不显然，脑抽了想了好久才发现），于是可以使用二分求出 f(x)f(x)。
不知道为什么，我以为答案不超过 nn，就用了一个数组存下 f(x)f(x)，然后在答案数组上二分。于是乎大样例直接挤掉了，才发现 1≤bi≤1091 \le b_i \le 10^9 😮
突然感觉 f(x)f(x) 在 [2,∞)[2, \infty) 上并没有单调性，想了好一会才发现是有的。于是直接改成了二分答案，时间复杂度 O(qlog⁡2n)\mathcal{O}(q \log^2 n)，感觉非常悬😖
确实寄掉了，5050 分 TLE。把 long long 去掉后直接 AC，气死我了🤬
缺零分治 / mexdncCPP
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 1e5 + 5;
LL t, n, m, q, a[N], b[N], s[N];
LL C(int i) {
  int l = 0, r = n + 1;
  for (int o; l + 1 < r;)
    b[o = l + r >> 1] >= i ? l = o : r = o;
  return 1ll * i * l + s[n] - s[l];
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n >> q, a[0] = -1, b[0] = 1e9;
    for (int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    if (a[1]) {
      for (LL x; q; q--)
        cin >> x, cout << (x ? -1 : 1) << "\n";
    } else {
      for (int i = 1; i <= n; i++)
        a[i] != a[i - 1] + 1 && (b[i] = 0), b[i] = min(b[i - 1], b[i]);
      partial_sum(b + 1, b + n + 1, s + 1);
      for (m = 1; m < n && a[m + 1] == a[m] + 1; m++);
      for (LL x; q; q--) {
        cin >> x;
        if (!x || x == m) {
          cout << (x ? 1 : -1) << "\n";
        } else {
          int l = 1, r = b[1] + 2;
          for (int o; l + 1 < r;)
            C(o = l + r >> 1) >= x ? r = o : l = o;
          cout << (r != b[1] + 2 ? r : -1) << "\n";
        }
      }
    }
  }
  return 0;
}

B

没看 老师我错了

C

最开始看题，发现 O(n2)\mathcal{O}(n^2) 的暴力很好写，估计有 2020 分。再看了看，感觉那个 di≤20d_i \le 20 的好像也很好写，直接记录时间戳+区间加，算贡献。还感觉是一条链的时候也感觉很好写，估计是可以直接计算的。m≤2m \le 2 貌似也不难，这不 6060 分随便到手。
真正开始写才发现不太对，暴力是 O(Tn2log⁡n)\mathcal{O}(T n^2 \log n) 的，这不直接 T 了吗？饿啊！写了个枚举 LCA⁡\operatorname{LCA} 算贡献的，可惜写炸了，没调出来。又想了好久发现可以对于每个点 ii，O(n)\mathcal{O}(n) 预处理 LCA⁡(i,j)\operatorname{LCA}(i, j)，之后再计算。
还有 di≤20d_i \le 20 的，发现并不是很好弄，只想到算 f(i+d)f(i + d) 可以视为在 ii 加一个 2d2^d，但不太好处理，也暂时放弃。m≤2m \le 2 的也突然没想到，也只好放弃了。
链的写着写着也发现不太好弄，但是 1∼n1 \sim n 的链比较好处理，轻松写了出来，可一直不知道为什么错了，小的数据全都过了，大的数据全都错了，直到比赛结束也没调出来😭 T2 T4 都没时间看了
只有 2020 分，太惨了。
树上求值 / treeCPP
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 2e5 + 5;
LL n, _, h, M, a[2][21], c[2 * N], d[N], q[N], fa[N];
bool f[N];
vector<int> e[N];
void D(int u, int p) {
  d[u] = d[p] + 1, fa[u] = p;
  for (int v : e[u]) v != p && (D(v, u), 1);
}
void S(int u, int fa, int k) {
  f[u] && (k = u), q[u] = k;
  for (int v : e[u]) v != fa && (S(v, u, k), 1);
}
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1, u, v; i < n; i++) {
    cin >> u >> v;
    e[u].push_back(v), e[v].push_back(u);
  }
  for (cin >> _; _; _--) {
    cin >> h >> M;
    for (int i = 0; i < 2; i++)
      for (int j = 0; j < 21; j++) cin >> a[i][j];
    for (int i = 1; i <= 2 * n; i++) {
      c[i] = 1;
      for (int j = 0; j < 21; j++)
        c[i] = c[i] * a[(i >> j) & 1][j] % M;
    }
    D(h, 0);
    LL s = 0;
    for (LL i = 1, x; i <= n; i++) {
      fill(f + 1, f + n + 1, 0);
      for (int x = i; x; x = fa[x]) f[x] = 1;
      S(h, 0, 0), x = 0;
      for (int j = 1; j <= n; j++) x = (x + c[j + d[q[j]]]) % M;
      s ^= i * x;
    }
    cout << s << "\n";
  }
  return 0;
}

D

没看

总结

下次不要在一道题上浪费太多时间，要合理安排。该开 long long 的变量开，不该开的地方不开，不然常熟太大直接 T 掉了😱

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...