## 器材整理
#暴力 #枚举
本题我赛时第一次提交可以通过，后面改了代码重新提交导致 TLE。我的算法不能保证正确性。
首先看到题目，就很容易想到二分，因为我们很难寻找最小的答案，但是我们可以很简单地判断一个答案是否合法。不过之前 [[2025.7.30 模拟赛]] 的最后一题和这个很相像，那题答案是没有单调性的。
至于如何判断答案合法性，我们整一个 set 存储目前尚未选择的所有器材，然后每次在 set 中寻找小于等于剩余空间的器材，如果没找到就新开一个箱子装，最后判断需要的箱子数量是否小于等于 $k$。
写完二分，果不其然地 wa 了，答案偏大。然后我就不会了，但是过了二十分钟我灵感爆发：既然我二分出来的答案虽然不对但是离正确的答案很接近，那我为什么不以二分出来的答案为参考进行枚举呢？
于是我就往二分出来的答案下面枚举 $1000$ 个数，取满足条件的最小值，就这样过大样例了。但是在我写其它题目的时候，我仍然忧心忡忡，害怕我的算法会 wa。后来在比赛结束的前十分钟，我把 $1000$ 改成了 $2000$ 重新交了一遍。然后我就 TLE 了。
以下是我初版不会 TLE 可以 AC 的代码：
```cpp
#include <iostream>
#include <set>
using namespace std;
using LL = long long;
const LL kMaxN = 1005;
LL a[kMaxN], t, n, k, mx, res, ans;
multiset<LL> s;
bool check(LL x) {
s.clear();
for (LL i = 1; i <= n; i++) {
s.insert(a[i]);
}
LL now = 0, cnt = 1;
for (LL i = 1; i <= n; i++) {
auto p = s.upper_bound(x - now);
if (p != s.begin()) {
p--;
now += *p;
s.erase(p);
} else {
now = 0, cnt++;
auto p = s.upper_bound(x - now);
if (p == s.begin()) {
return 0;
}
p--;
now += *p;
s.erase(p);
}
}
return cnt <= k;
}
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
cin >> n >> k;
mx = 0;
for (LL i = 1; i <= n; i++) {
cin >> a[i];
mx = max(mx, a[i]);
}
for (LL l = mx, r = 1e9; l <= r; ) {
LL m = (l + r) / 2;
if (check(m)) {
res = m;
r = m - 1;
} else {
l = m + 1;
}
}
for (LL i = res; i >= max(mx, res - 1000); i--) {
if (check(i)) {
ans = i;
}
}
cout << ans << '\n';
}
return 0;
}
```
## 简单题
#贪心 #排序
首先这道题目对子串进行操作之后，它会变成 `#`，这就代表着这个子串在后面不会参与其它的操作，而我们要求的是最后的 `#` 的数量，因此 $f(s)$ 的值其实就是 $s$ 中 $0/1$ 段的数量。不难想到时间复杂度为 $\mathcal O(n^2)$ 的 dp。设 $dp_{i,j,0/1}$ 表示为前 $i$ 个字符中，有 $j$ 个 `1`，$f(s)$ 的最小值，按照题意转移即可。
但是本题 $2\le n\le 2\times 10^5$，dp 会 TLE 掉，并且状态似乎无法简化，这时候就要想到贪心。在贪心前，我们需要改变思路。我们可以先将所有的 `?` 设为 `0`，然后一个一个地将原来是 `?` 的 `0` 变成 `1`，在变化的过程中维护 $0/1$ 段的数量。
为了方便，以下我们将“把原来的 `?` 化成的 `0` 变成 `1`”的操作称为“升级”操作。
考虑一种简单的 **鼠目寸光** 的贪心是：维护每一个原来是 `?` 的 `0` 升级到 `1` 所带来的贡献（贡献是答案 $0/1$ 段的增量），每次对贡献值最小位置进行升级。贡献值只和左右邻居有关，因此我们进行操作之后还要顺带维护邻居的贡献值。每次取最小+快速删除插入指定元素，set 是一个不错的选择。
```cpp
// 计算最开始所有 ? 都是 0 的段数
int calc() {
int cnt = 1;
for (int i = 2; i <= n; i++) {
cnt += b[i] != b[i - 1];
}
return cnt;
}
// 计算一个 0 升级到 1 的贡献，即新段数-旧段数
int delta(int x) {
return ((b[x - 1] != '1') + (b[x + 1] != '1')) -
((b[x - 1] != '0') + (b[x + 1] != '0'));
}
// 统计最初 1 的数量，记录 ? 的位置
for (int i = 1; i <= n; i++) {
if (s[i] == '1') {
ori++;
} else if (s[i] == '?') {
v.push_back(i);
}
}
// b 是将所有 ? 变成 0 的版本
b = s;
for (int i : v) {
b[i] = '0';
}
fill(ans, ans + n + 1, -1); // 初始化答案为 -1
now = calc(); // 最初的答案
ans[ori] = now;
// 放入所有贡献
for (int i : v) {
q.emplace(cur[i] = delta(i), i);
}
// 进行 0 到 1 的升级操作
for (int i = 1; i <= v.size(); i++) {
auto p = *q.begin(); // 取贡献值最小的
now += p.first; // 累加贡献
ans[ori + i] = now; // 记录答案
b[p.second] = s[p.second] = '1'; // 标记以被升级
// 对左邻居的贡献重计算
if (s[p.second - 1] == '?') {
q.erase(make_pair(cur[p.second - 1], p.second - 1));
q.insert(make_pair(cur[p.second - 1] = delta(p.second - 1), p.second - 1));
}
// 对右邻居的贡献重计算
if (s[p.second + 1] == '?') {
q.erase(make_pair(cur[p.second + 1], p.second + 1));
q.insert(make_pair(cur[p.second + 1] = delta(p.second + 1), p.second + 1));
}
q.erase(p);
}
```
这个算法当然是错误的，譬如 `0?0???0` 的数据，此时先选择右边的 `?` 进行升级是更优的，因为段数最开始 $+2$ 之后就一直不变直到右边耗完；而如果我们先选择左边的 `?` 进行升级了话，段数 $+2$ 了之后还要选择右边的，这时段数会重新 $+2$，当然是不优的。
此时我们就思考了，是不是如果贡献值一样的话，所在的连续的一段 `?` 长度越长越优呢？也不一定，比如 `1?1???1` 的数据，此时先升级左边的段数立马就能 $-2$，而若是先升级右边的得升级 $3$ 次才能让段数 $-2$。
那我们是不是要进行分类讨论，讨论一段两侧是都是 $1$，还是都是 $0$，还是一边是 $1$ 一边是 $0$ 呢？真是太复杂了，好渴鹅肯定不会写。但是，最近我们都一直在强调“一段连续的 `?`”，我们的最优操作是否是围绕着一段一段进行的呢？
---
**证明——最优操作一定是一段一段进行升级的**：（这里默认每一段长度大于 $1$）当我们对于全 `0` 的一段原本是 `?` 的未升级的段首次进行升级时，段数一定不会减少的[^1]；初次升级之后接下来对同一段升级的若干次，如果没有把这一段填满的话，段数是不会改变的[^2]；如果将这一段填满成 $1$ 了，段数是一定不会增加的[^3]。经过我们的讨论，不难发现：开新的一段不会当前段数不会更小，逮着一段专门升级，升级完了段数不会更大。因此最优操作一定是一段一段进行升级的。
[^1]: 如果段左边和右边都是 $0$ 时，初次升级段数会 $+2$；如果段左边和右边一 $0$ 一 $1$，选择 $1$ 的那边升级，初次升级段数不会改变；如果段左边和右边都是 $1$ 时，初次升级段数不会改变。
[^2]: 每次都升级和上一次升级的相邻的那个，段数不会改变。
[^3]: 如果段左边和段右边都是 $1$，填满后两侧会连起来，段数 $-2$；否则段数不变。
接下来我们就需要考虑对于每一段，应该按照什么样的方式升级才是最优的。
我们对于每一段的升级，搞三个变量 `fir`、`len` 和 `las`，分别表示初次升级的贡献、段的长度和升级完毕后的贡献。贡献计算方式在角标中优详细说明。
然后对于每一段进行排序，首先按照 `fir` 排，越小越好，因为这是第一次升级之后可以立马带来的贡献；其次按照 `las` 排，越小越好，因为这是升级完毕之后可以延迟带来的贡献；最后是按照 `len` 排，如果 `las` 是负数那么当然是越先满足越好，`len` 小的排前面，否则 `len` 大的排前面让 `las` 的增量尽量在后面加上，保证最优。
最后按照排序后的顺序枚举每一段进行升级即可。时间复杂度 $\mathcal O(n\log_2 n)$。
```cpp
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;
const int kMaxN = 2e5 + 5;
struct Node {
int fir, len, las;
};
int ans[kMaxN], t, n, ori, now;
string s, b;
vector<int> v;
vector<Node> c;
// 计算初始答案
int calc() {
int cnt = 1;
for (int i = 2; i <= n; i++) {
cnt += b[i] != b[i - 1];
}
return cnt;
}
// 获取每一段的信息
void getLen() {
for (int i = 1, j; i <= n; ) {
if (s[i] != '?') { // 如果不是 ? 就不用找了
i++;
continue;
}
for (j = i; s[j] == '?'; j++) { } // 找到第一个不是 ? 的下标，[i,j) 就是段
// 计算该段贡献
c.push_back(Node{2 * (s[i - 1] == '0' && s[j] == '0'),
j - i,
2 * -(s[i - 1] == '1' && s[j] == '1')});
i = j;
}
}
void solve() {
cin >> n >> s;
s = " " + s; // 下标从 1 开始
c.clear(); // 清空段
getLen(); // 获取段
ori = count(s.begin() + 1, s.begin() + n + 1, '1'); // 获取原始 1 数量
fill(ans, ans + n + 1, -1); // 初始化答案为 -1
b = s; // b 是将所有 ? 变成 0 的版本
for (int i = 1; i <= n; i++) {
if (s[i] == '?') {
b[i] = '0';
}
}
now = calc(); // 初始贡献
ans[ori] = now; // 记录答案
// 对段进行排序
sort(c.begin(), c.end(), [](const Node &a, const Node &b) {
if (a.fir != b.fir) {
return a.fir < b.fir;
}
if (a.las != b.las) {
return a.las < b.las;
}
return a.las < 0 ? a.len < b.len : a.len > b.len;
});
// 按照排序后顺序枚举
for (auto &i : c) {
now += i.fir; // 升级一次就有的贡献
for (int j = 1; j < i.len; j++) { // 记录答案
ans[++ori] = now;
}
now += i.las; // 升级完才有的贡献
ans[++ori] = now; // 记录答案
}
// 输出答案
for (int i = 0; i <= n; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
}
int main() {
cin.tie(0)->sync_with_stdio(0);
for (cin >> t; t; t--) {
solve();
}
return 0;
}
```
## 异或可达
#并查集 #线段树
不会正解，所以我打的是暴力。
用并查集维护连通块，对于每个询问枚举每一条边，若满足条件就进行并查集合并，最后单个连通块内的任意两个元素都是可以到达的，计算组合数并累加。
## ABBA
#序列dp
本来写了一个 dp 的，但是会 wa，遂改成大爆搜吗，然后第一个点都能 TLE，于是就趋势了。
## 总结
总分：$55+100+20+0=175$。
花了太多时间在调 T2 的错误的贪心上，结果最后十分钟就重写出了正确的贪心；第一题本来能过的最后乱改导致 TLE；数据结构掌握不过关，不会 T3；时间搭配不合理，没时间写 T4 $\mathcal O(n^3)$ dp。总结：代码能跑不要乱动。