2025.11.15 模拟赛

缺零分治

贪心 二分 前缀和

首先可以先对原序列进行处理。$a$ 肯定是要变成从 $0$ 开始慢慢递增的（每次增加 $1$），后面的都可以不要了，反正放到哪个可重集都不会改变 $\text{mex}$。$b$ 的话，对于 $(i,j)$ 满足 $a_i>a_j$，那么也要 $b_i\le b_j$，否则 $b_i$ 多的那一部分不可能会改变 $\text{mex}$ 的大小（直观理解就是 $a_i$ 要连续递增，$b_i$ 要连续单调不增（增了就用前缀 $\min$ 解决））。

肯定是先要进行贪心的。对于 $m$，最简单的模拟方式是每次选择最大可能构造出来但是大小不超过 $m$ 的 $\text{mex}$。显然 $m$ 的值非常大，一步一步减肯定会 TLE。

最浅显的优化方式就是每次选择最大 $\text{mex}$ 之后直接选择多次，这样单次询问就可以做到 $\mathcal{O}(n)$。多组询问仍然不好搞。考虑离线下来排序，用单调性一起做，但是发现使用了更高的 $\text{mex}$ 值所有更小的数量都要减掉，然而维护了这个就不能批量搞了（因为大家都不一样）。

所以考虑快速做减法的操作。维护后缀和 $p_i$ 表示把 $[i,n]$ 中所有 $a_i$ 可以表示出的 $\text{mex}=a_i+1$ 都拿来用，能搞出的最大和。那么有递推式 $p_i=p_{i+1}+(a_i+1)\times (b_i-b_{i+1})$。$a_i+1$ 表示拿 $[0,a_i]$ 前缀能搞出来的 $\text{mex}$，$b_i-b_{i+1}$ 是因为 $a_{i+1}$ 和后面的用了 $b_{i+1}$ 个 $a_i$。

这样，我们可以通过二分快速进行减法操作，找到最小的 $x$ 满足 $p_x\le m$。现在的 $m\leftarrow m-p_x$ 后，已经无力减掉 $x-1$ 的全部 $\text{mex}$ 了，但是可以减去部分。计算 $\lfloor \frac{m}{a_{x-1}+1}\rfloor$ 并累加至答案当中。最后 $m$ 连 $x-1$ 都减不了了，如果还 $\ne 0$ 的话，直接答案 $+1$ 即可。

时间复杂度 $\mathcal{O}(q{\log }_{2}n)$。

const LL kMaxN = 1e5 + 5;
 
LL a[kMaxN], b[kMaxN], sub[kMaxN], t, n, q;
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  for (cin >> t; t; t--) {
    cin >> n >> q;
    for (LL i = 1; i <= n; i++) {
      cin >> a[i] >> b[i];
    }
    for (LL i = 1; i <= n; i++) {
      if (i == 1 && a[i] != 0 ||
          i != 1 && a[i] != a[i - 1] + 1) {
        n = i - 1;
        break;
      }
    }
    b[0] = 1e18;
    for (LL i = 1; i <= n; i++) { 
      b[i] = min(b[i - 1], b[i]);
    }
    b[n + 1] = sub[n + 1] = 0;
    for (LL i = n; i >= 1; i--) {
      sub[i] = sub[i + 1] + (a[i] + 1) * (b[i] - b[i + 1]);
    }
    for (LL m; q; q--) {
      cin >> m;
      if (n == 0) {
        cout << (m == 0 ? 1 : -1) << '\n';
        continue;
      }
      if (m == 0) {
        cout << "-1\n";
        continue;
      }
      if (m <= a[n] + 1) {
        cout << 1 + (m != a[n] + 1) << '\n';
        continue;
      }
      if (m - sub[1] > 0) {
        cout << "-1\n";
        continue;
      }
      LL p = -1;
      for (LL l = 1, r = n + 1; l <= r; ) {
        LL mid = (l + r) / 2;
        if (sub[mid] <= m) {
          p = mid;
          r = mid - 1;
        } else {
          l = mid + 1;
        }
      }
      LL use = b[p];
      m -= sub[p];
      if (m > 0) {
        use += m / (a[p - 1] + 1);
        m %= a[p - 1] + 1;
        if (m > 0) {
          use++;
        }
      }
      cout << use << '\n';
    }
  }
  return 0;
}

猜数游戏

背包dp 序列dp

• [c] 赛时半个小时没读懂题，后面思考得过于复杂了，实际上很简单。$n\le 10^5$ 真是太有诱惑性了，小可爱出题人居然给时间复杂度 $\mathcal{O}\left(T{n}^2\right)$（而且还是标解）。

赛后发现就是 ZRR 题目。

首先看到数据范围就很像 DP。设 $d{p}_i$ 表示长度为 $i$ 的子问题的答案（原问题是长度为 $n$，这里即 $1$ 跳到 $i$），那么有 $d{p}_i=\underset{j=1}{\overset{i-1}{\min }}\max (d{p}_j,d{p}_{i-j})+v_j$，其中 $j$ 表示跳一步长度为 $j$ 的最小花费。直观来看，就是枚举 $j$ 表示从 $[1,i]$ 左边或右边掏掉 $j$ 的，然后用 $v_j$ 的代价补上。

$v_j$ 求的方式可以通过完全背包搞。注意需要用到负数下标，所以需要设置偏移。时间复杂度 $\mathcal{O}(T{n}^2)$。

const LL kMaxN = 2e4 + 5, kM = 1e4;
 
LL a[kMaxN], b[kMaxN], wyy[kMaxN], zrr[kMaxN], c, t, n, m;
 
int main() {
  for (cin >> c >> t; t; t--) {
    cin >> n >> m;
    for (LL i = 1; i <= m; i++) {
      cin >> a[i];
    }
    for (LL i = 1; i <= m; i++) {
      cin >> b[i];
    }
    fill(begin(wyy), end(wyy), 1e18);
    fill(begin(zrr), end(zrr), 1e18);
    wyy[kM] = 0;
    for (LL i = 1; i <= m; i++) {
      for (LL j = a[i]; j <= 2 * kM; j++) {
        wyy[j] = min(wyy[j], wyy[j - a[i]] + b[i]);
      }
      for (LL j = 2 * kM - a[i]; j >= 0; j--) {
        wyy[j] = min(wyy[j], wyy[j + a[i]] + b[i]);
      }
    }
    zrr[1] = 0;
    for (LL i = 2; i <= n; i++) {
      for (LL j = 1; j < i; j++) {
        zrr[i] = min(zrr[i], max(zrr[j], zrr[i - j]) + wyy[kM + j]);
      }
    }
    cout << (zrr[n] == 1e18 ? -1 : zrr[n]) << '\n';
  }
  return 0;
}

树上求值

字典树 启发式合并

采用暴力。遍历每个节点 $x$，对 $\text{lca}$ 为 $x$ 的节点对累加贡献。有两种可能的 $\text{lca}$ 存在方式：

• $(x,y)$ 当中一个存在于另一个的子树当中。
• $(x,y)$ 当中 $x$ 和 $y$ 分别存在于 $\text{lca}$ 的不同儿子的子树当中。

这些贡献是很好累加的。需要注意 $(x,x)$ 的贡献，会被加两次，需要减掉。时间复杂度 $\mathcal{O}(n^2)$，成功获得 $20$ 分。

LL calc(LL x) {
  LL res = 1;
  for (LL i = 0; i <= 20; i++) {
    res = res * a[i][x & 1] % mod;
    x >>= 1;
  }
  return res;
}
 
LL summary(LL lca, LL x, LL f) {
  LL res = val[x + d[lca]];
  for (LL i : e[x]) {
    if (i != f) {
      res = (res + summary(lca, i, x)) % mod;
    }
  }
  return res;
}
 
void add(LL x, LL f, LL s) {
  sum[x] = (sum[x] + s) % mod;
  for (LL i : e[x]) {
    if (i != f) {
      add(i, x, s);
    }
  }
}
 
void dfs(LL x, LL f) {
  d[x] = d[f] + 1;
  for (LL i : e[x]) {
    if (i != f) {
      dfs(i, x);
    }
  }
  add(x, f, val[x + d[x]]);
  sum[x] = (sum[x] + summary(x, x, f)) % mod;
  sum[x] = (sum[x] - val[x + d[x]] + mod) % mod;
  for (LL i : e[x]) {
    if (i == f) {
      continue;
    }
    LL s = summary(x, i, x);
    for (LL j : e[x]) {
      if (j == f || j == i) {
        continue;
      }
      add(j, x, s);
    }
  }
}

夜里亦始终想念着你

数学

我采用的暴力+特殊性质，r可以得到 $36$ 分。

• 对于 $n\le 20$，采用暴力 dfs 计算所有可能得到的最终局面，再做子集 DP 即可。时间复杂度 $\mathcal{O}(2^{n}q)$。
• 对于保证奇数位置必有棋子的，偶数位置可以随便跳。对于最终的集合，我们枚举它有多少个选中了偶数位置，奇数位置就直接用 $2$ 的幂算即可。需要配合前缀和处理。

void dfs(LL x) {
  // 记忆化搜索
}
 
LL dp() {
  // 子集 DP
}
 
f (n <= 20) {
  dfs(mask(s));
  cout << dp() << '\n';
  for (LL x; q; q--) {
    cin >> x;
    s[x] = ((s[x] - '0') ^ 1) + '0';
    fill(begin(f), end(f), 0);
    dfs(mask(s));
    cout << dp() << '\n';
  }
  return 0;
}
init();
LL wyy = 0, zrr = 0;
for (LL i = 1; i <= n; i++) {
  if (i % 2 == 0) {
    wyy++;
    cnt += s[i] == '1';
  } else {
    zrr++;
  }
}
ans[0] = 1;
for (LL i = 1; i <= wyy; i++) {
  ans[i] = (ans[i - 1] + comb(wyy, i)) % kMod;
}
LL base = pow(2, zrr);
cout << ans[cnt] * base % kMod << '\n';
for (LL x; q; q--) {
  cin >> x;
  s[x] = ((s[x] - '0') ^ 1) + '0';
  cnt -= s[x] == '0';
  cnt += s[x] == '1';
  cout << ans[cnt] * base % kMod << '\n';
}

总结

总分：$100+0+20+36=156$。

T2 想得太复杂了，下次应该多思考不同的思路。