AGC056C 题解

· · 题解

直接做不好做，考虑将条件转化。令 d_i 为 1\sim i 中 0 的个数减去 1 的个数。
容易发现，想要最小化原串的字典序，其实就是让 0 尽可能多，也就是让 d_i 尽可能大。这就转化为如何使得 d_i 的字典序最大。

我们发现，给定的条件 (l_i,r_i) 可以表述为 d_{r_i} = d_{l_i - 1}，因为 [l_i,r_i] 段中 0,1 个数是相等的，体现在 d_i 上就是 [l_i,r_i] 段有 0 的贡献。
同时根据定义可得 \forall \ 1< i \le n,\ |d_i - d_{i-1}| = 1。这与 \forall \ 1< i \le n,\ |d_i - d_{i-1}| \le 1 等价。

列出我们已知的条件：

  1. \forall \ 1\le i \le m, \ d_{l_i - 1} = d_{r_i}
  2. \forall \ 1< i \le n,\ |d_i - d_{i-1}| \le 1

条件的特殊性启发我们采用差分约束系统求解本题，同时差分约束系统也可以很好地满足使 d_i 字典序最大的需要。
对 1. 条件建 (l_i - 1, r_i)，边权为 0 的双向边；对 2. 条件建 (i - 1, i)，边权为 1 的双向边。
由于边权的特殊性，我们可以通过 01bfs 求解所有 d_i。这给出了构造方案。

总时间复杂度 O(n +m)。

\text{code : } 
#include <bits/stdc++.h>
using namespace std; 
template <typename T> void get(T & x) {
    x = 0; char ch = getchar(); bool f = false; while (ch < '0' or ch > '9') f = f or ch == '-', ch = getchar();
    while ('0' <= ch and ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar(); f && (x = -x); 
} template <typename T, typename ... Args> void get(T & a, Args & ... b) { get(a); get(b...); }
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
const int N = 1e6 + 10;
int n, m, l, r; 
vector <pair<int,int> > g[N];

int dis[N];
deque<int> que;
void bfs(int st) {
    memset(dis, -1, sizeof dis);
    dis[st] = 0; que.push_back(st); 
    while (que.size()) {
        int u = que.front(); que.pop_front();
        for (auto [v, w] : g[u]) {
            if (dis[v] == -1) {
                dis[v] = dis[u] + w;
                if (w == 0) que.push_front(v);
                else que.push_back(v);
            }
        }
    }
}

int main() {
    get(n, m); 
    rep(i,1,m) get(l, r), g[r].emplace_back(l - 1, 0), g[l - 1].emplace_back(r, 0);
    rep(i,1,n) g[i - 1].emplace_back(i, 1), g[i].emplace_back(i - 1, 1);
    bfs(0);
    rep(i,1,n) cout << (dis[i] < dis[i - 1]);
}