2025.9.2 模拟赛

正负 1

首先，把所有空白的格子都涂成 $1$ 肯定是最可能满足条件的，如果这都不行肯定是无解的。但是题目要求的是字典序最小的解，然后看样例很显然是 $- 1$ 排在 $1$ 前面的，并且对于越前面的一个数，可以填 $- 1$ 一定会填上 $- 1$ ，不行才会填 $1$ 。

所以我们可以对每一个空着的数首先均填上 $1$ ，然后从前往后依次枚举，看一看每一个数能否改成 $- 1$ ，从前往后保证字典序最小。判断能否改成 $- 1$ 就是 $O (m)$ 枚举一下限制，如果每个包含了当前枚举的数的限制都比实际要求的 $k_{i}$ 大至少 $2$ 时，就可以把这个数改成 $- 1$ 了。区间查询和、单点修改采用树状数组实现，时间复杂度 $O (nm lo g_{2} n)$ 。

但是这样子会超时，所以我们需要转变思路。一个数想要变成 $- 1$ ，需要满足 $m$ 个限制才可以，判断限制的过程很慢，因此我们反过来，每个数先暂时填上 $- 1$ ，然后对于每个限制再将限制区域内的一些 $- 1$ 改成 $1$ 即可。

修改成 $1$ 的 $- 1$ 肯定是越往后越好，这样子才可以保证字典序最小。但是这样子就会引起一个问题，如果当前限制的区间不满足条件，我把它后端的若干个 $- 1$ 改成 $1$ 了，但是下面又来了一个新的区间，在上个区间前面但有交汇，把交汇处的若干个 $- 1$ 变成了 $1$ ，导致后面的区间实际的值比要求的 $k_{i}$ 要大，那么原来我们在区间后端改成的 $1$ 就没用了，反而使答案字典序不是最小，导致 WA。

所以我就想出了一个绝佳的策略，便是把所有限制离线下来然后按照 $r_{i}$ 从小到大的顺序处理，这样子先处理的区间就会影响后面的区间，使得不会修改多余的 $1$ 。

至于如何把区间尾端的若干个 $- 1$ 改成 $1$ ，我使用一个线段树维护段内最大 $- 1$ 下标，同时维护段内和和可以改成 $1$ 的 $- 1$ 的数量。每次先判断能否满足条件，如果可以就循环找区间内最后一个 $- 1$ 并修改。由于最多一共就 $n$ 的 $- 1$ 给你修改，因此时间复杂度 $O ((lo g_{2} m + lo g_{2} n) m + n lo g_{2} n)$ 。

此外，这道题目使用优先队列贪心也是另外一种解法，但是我觉得我的解法更简单自然。

#include <iostream>
#include <algorithm>
 
using namespace std;
 
const int kMaxN = 1e5 + 5;
 
struct Node {
  int id, sum, cnt;  // 最大可改 -1 编号，目前实际的和，目前 -1 的数量
} tr[4 * kMaxN];
 
struct Limit {
  int l, r, k;
} q[kMaxN];
 
int a[kMaxN], n, m;
 
void pushUp(int p) {
  tr[p].id = max(tr[2 * p].id, tr[2 * p + 1].id);
  tr[p].sum = tr[2 * p].sum + tr[2 * p + 1].sum;
  tr[p].cnt = tr[2 * p].cnt + tr[2 * p + 1].cnt;
}
 
void modify(int p, int l, int r, int x, int val) {
  if (l == r) {
    if (!val) {  // 暂时填 -1
      tr[p] = Node {l, -1, 1};
    } else {
      tr[p] = Node {-1, val, 0};
    }
    return;
  }
  int m = (l + r) / 2;
  if (x <= m) {
    modify(2 * p, l, m, x, val);
  } else {
    modify(2 * p + 1, m + 1, r, x, val);
  }
  pushUp(p);
}
 
int querySum(int p, int l, int r, int s, int t) {
  if (s <= l && r <= t) {
    return tr[p].sum;
  }
  int m = (l + r) / 2, res = 0;
  if (s <= m) {
    res += querySum(2 * p, l, m, s, t);
  }
  if (m < t) {
    res += querySum(2 * p + 1, m + 1, r, s, t);
  }
  return res;
}
 
int queryCnt(int p, int l, int r, int s, int t) {
  if (s <= l && r <= t) {
    return tr[p].cnt;
  }
  int m = (l + r) / 2, res = 0;
  if (s <= m) {
    res += queryCnt(2 * p, l, m, s, t);
  }
  if (m < t) {
    res += queryCnt(2 * p + 1, m + 1, r, s, t);
  }
  return res;
}
 
int queryId(int p, int l, int r, int s, int t) {
  if (s <= l && r <= t) {
    return tr[p].id;
  }
  int m = (l + r) / 2, res = -1;
  if (s <= m) {
    res = max(res, queryId(2 * p, l, m, s, t));
  }
  if (m < t) {
    res = max(res, queryId(2 * p + 1, m + 1, r, s, t));
  }
  return res;
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    modify(1, 1, n, i, a[i]);
    if (!a[i]) {
      a[i] = -1;
    }
  }
  for (int i = 1; i <= m; i++) {
    cin >> q[i].l >> q[i].r >> q[i].k;
  }
  sort(q + 1, q + m + 1, [](const Limit &a, const Limit &b) {
    return a.r < b.r;
  });
  bool ans = 1;
  for (int i = 1; i <= m; i++) {
    int sum = querySum(1, 1, n, q[i].l, q[i].r);
    int cnt = queryCnt(1, 1, n, q[i].l, q[i].r);
    if (sum + 2 * cnt < q[i].k) {
      ans = 0;
      break;
    }
    while (sum < q[i].k) {
      int p = queryId(1, 1, n, q[i].l, q[i].r);
      modify(1, 1, n, p, a[p] = 1);
      sum += 2;
    }
  }
  if (!ans) {
    cout << "Impossible\n";
    return 0;
  }
  for (int i = 1; i <= n; i++) {
    cout << a[i] << ' ';
  }
  return 0;
}

随机左移

状压dp 组合数学

最开始我想到的是反过来操作，把 $p$ 进行 $m$ 次前缀循环右移操作，最后变成 $1 \sim n$ 的排列，但是后来我去写第三题了，这题也没有继续想，代码都没有写。

其实对于 $n \leq 5, m \leq 5000$ 的 $10$ 分数据，由于排列只有 $n! = 120$ 种，实际上可以直接做一个 $O (n! \times m)$ 的 dp 模拟操作的，但是我没有写。。。

序列变换

线段树

按照正常人的操作来说，终止状态应该是只有一个的。所以我在这个基础之上搞了非常多的暴力、式子但是最后都壮烈牺牲了。

首先这道题目有单点修改和区间查询，区间查询虽然需要进行一连串的操作，但是应该是有规律可以找的。于是我就最开始瞎写了一个式子，然后样例都过不了……后面我又改进了式子。令 $k$ 为 $[l, r)$ 中最后一个偶数下标，如果没有答案为 $0$ ，有的话答案为 $k - l + 1$ 。我想的是先把 $k$ 通过操作一改成 $0$ 了之后用二号操作把前面的也搞成 $0$ 抛到后面，前面一个是 $0$ 了又能继续二操作，一直这么搞最后 $[l, k]$ 都是 $0$ 。但是对于 1 1 2 2 的数据，当进行一、二操作之后变为 1 0 0 5 后，此时把 $1$ 抛到后面仍然只有 $2$ 个 $0$ ，所以我又进行了优化，如果 $[l, k]$ 中有 $d$ 个奇数的话，答案就是 $k - l + 1 - d$ ，但是因为不太清楚的原因 WA 了。

然后我就没有渴望 AC 了，转去写暴力。最开始我写的是线性往后枚举每一个元素，依次对该元素进行两种操作，但是会比标准答案小。XBC 的方法是不停地循环，直到无法进行任何操作，但是我没写这一步，遗憾炸裂，进行多次小修改了之后仍然是 WA。不停循环的时间复杂度是 $O (n^{2} q)$ 的，因为最多只会进行 $n$ 次循环，可以通过 $15$ 分。

删除线段

状压dp 线段树

首先我想到了状压，把当前还剩下哪些线段状压起来，时间复杂度 $O (n^{2} n)$ ，可以通过 $5$ 分，然后我就不会了。主要是不知道如何让状态脱离对剩下线段的依赖，贪心我也想不到一个好的策略，于是就挂分了。

总结

总分： $100 + 0 + 0 + 5 = 105$ 。

首先我太菜了，后三题都不会。但是我暴力打的也不行，具体来说是第二题应该打的 $10$ 分没有写，然后第三题暴力循环 $15$ 分没有注意到，最后最后一题没有过多的思考只有 $5$ 分，下次应该注意暴力奇技淫巧的使用，正确获得更多暴力分。

Haokee Note

Explorer

2025.9.2 模拟赛

正负 1

随机左移

序列变换

删除线段

总结

Graph View

Table of Contents