## 缺零分治
#贪心 #二分 #前缀和
首先可以先对原序列进行处理。$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\gets m-p_x$ 后，已经无力减掉 $x-1$ 的全部 $\text{mex}$ 了，但是可以减去部分。计算 $\left\lfloor\cfrac{m}{a_{x-1}+1}\right\rfloor$ 并累加至答案当中。最后 $m$ 连 $x-1$ 都减不了了，如果还 $\ne 0$ 的话，直接答案 $+1$ 即可。
时间复杂度 $\mathcal O(q\log_2 n)$。
```cpp
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(Tn^2\right)$（而且还是标解）。
赛后发现就是 ZRR 题目。
首先看到数据范围就很像 DP。设 $dp_i$ 表示长度为 $i$ 的子问题的答案（原问题是长度为 $n$，这里即 $1$ 跳到 $i$），那么有 $dp_i=\min\limits_{j=1}^{i-1}\max(dp_{j},dp_{i-j})+v_j$，其中 $j$ 表示跳一步长度为 $j$ 的最小花费。直观来看，就是枚举 $j$ 表示从 $[1,i]$ 左边或右边掏掉 $j$ 的，然后用 $v_j$ 的代价补上。
$v_j$ 求的方式可以通过完全背包搞。注意需要用到负数下标，所以需要设置偏移。时间复杂度 $\mathcal O(Tn^2)$。
```cpp
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$ 分。
```cpp
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^nq)$。
- 对于保证奇数位置必有棋子的，偶数位置可以随便跳。对于最终的集合，我们枚举它有多少个选中了偶数位置，奇数位置就直接用 $2$ 的幂算即可。需要配合前缀和处理。
```cpp
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 想得太复杂了，下次应该多思考不同的思路。