2025.8.2 模拟赛

器材整理

本题我赛时第一次提交可以通过，后面改了代码重新提交导致 TLE。我的算法不能保证正确性。

首先看到题目，就很容易想到二分，因为我们很难寻找最小的答案，但是我们可以很简单地判断一个答案是否合法。不过之前 2025.7.30 模拟赛的最后一题和这个很相像，那题答案是没有单调性的。

至于如何判断答案合法性，我们整一个 set 存储目前尚未选择的所有器材，然后每次在 set 中寻找小于等于剩余空间的器材，如果没找到就新开一个箱子装，最后判断需要的箱子数量是否小于等于 $k$ 。

写完二分，果不其然地 wa 了，答案偏大。然后我就不会了，但是过了二十分钟我灵感爆发：既然我二分出来的答案虽然不对但是离正确的答案很接近，那我为什么不以二分出来的答案为参考进行枚举呢？

于是我就往二分出来的答案下面枚举 $1000$ 个数，取满足条件的最小值，就这样过大样例了。但是在我写其它题目的时候，我仍然忧心忡忡，害怕我的算法会 wa。后来在比赛结束的前十分钟，我把 $1000$ 改成了 $2000$ 重新交了一遍。然后我就 TLE 了。

以下是我初版不会 TLE 可以 AC 的代码：

#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$ 段的数量。不难想到时间复杂度为 $O (n^{2})$ 的 dp。设 $d p_{i, j, 0/1}$ 表示为前 $i$ 个字符中，有 $j$ 个 1， $f (s)$ 的最小值，按照题意转移即可。

但是本题 $2 \leq n \leq 2 \times 1 0^{5}$ ，dp 会 TLE 掉，并且状态似乎无法简化，这时候就要想到贪心。在贪心前，我们需要改变思路。我们可以先将所有的 ? 设为 0，然后一个一个地将原来是 ? 的 0 变成 1，在变化的过程中维护 $0/1$ 段的数量。

为了方便，以下我们将“把原来的 ? 化成的 0 变成 1”的操作称为“升级”操作。

考虑一种简单的 鼠目寸光 的贪心是：维护每一个原来是 ? 的 0 升级到 1 所带来的贡献（贡献是答案 $0/1$ 段的增量），每次对贡献值最小位置进行升级。贡献值只和左右邻居有关，因此我们进行操作之后还要顺带维护邻居的贡献值。每次取最小+快速删除插入指定元素，set 是一个不错的选择。

// 计算最开始所有 ? 都是 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$ 了，段数是一定不会增加的³。经过我们的讨论，不难发现：开新的一段不会当前段数不会更小，逮着一段专门升级，升级完了段数不会更大。因此最优操作一定是一段一段进行升级的。

接下来我们就需要考虑对于每一段，应该按照什么样的方式升级才是最优的。

我们对于每一段的升级，搞三个变量 fir、len 和 las，分别表示初次升级的贡献、段的长度和升级完毕后的贡献。贡献计算方式在角标中优详细说明。

然后对于每一段进行排序，首先按照 fir 排，越小越好，因为这是第一次升级之后可以立马带来的贡献；其次按照 las 排，越小越好，因为这是升级完毕之后可以延迟带来的贡献；最后是按照 len 排，如果 las 是负数那么当然是越先满足越好，len 小的排前面，否则 len 大的排前面让 las 的增量尽量在后面加上，保证最优。

最后按照排序后的顺序枚举每一段进行升级即可。时间复杂度 $O (n lo g_{2} n)$ 。

#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 $O (n^{3})$ dp。总结：代码能跑不要乱动。

如果段左边和右边都是 $0$ 时，初次升级段数会 $+ 2$ ；如果段左边和右边一 $0$ 一 $1$ ，选择 $1$ 的那边升级，初次升级段数不会改变；如果段左边和右边都是 $1$ 时，初次升级段数不会改变。 ↩
每次都升级和上一次升级的相邻的那个，段数不会改变。 ↩
如果段左边和段右边都是 $1$ ，填满后两侧会连起来，段数 $- 2$ ；否则段数不变。 ↩

Haokee Note

Explorer

2025.8.2 模拟赛

器材整理

简单题

异或可达

ABBA

总结

Graph View

Table of Contents

Haokee Note

Explorer

2025.8.2 模拟赛

器材整理

简单题

异或可达

ABBA

总结

Footnotes

Graph View

Table of Contents