:::info[Description] Link. :::
:::infoSolution 记 表示前 位中 的数量减去 的数量是多少，然后特殊处理一下 。题目的条件可以被刻画为：
- 。
- 对一组限制条件 而言必须满足 。
因此考虑差分约束建模。对一组限制条件 而言，其必须满足 ，可以建一组连接 两个点，边权为 的双向边。
然后对 的限制可以考虑先把限制放宽得到 ，这个是容易建模的，直接拆绝对值然后建 和 的权值为 的边即可。
然后从 号点跑一遍最短路得到 数组就是一组满足条件且字典序最小的 。考虑这个为什么是对的。因为每个位置都尽量让 的值大，也就是尽量选择 这个松弛操作，对应的就是贪心的能在当前位填 就填 因此确实可以满足字典序最小的条件。
直接跑 01-bfs 可以做到线性时间复杂度求解。 :::
:::success[Code]
namespace lowspeed_song {
inline void init() {
}
int dis[N];
vector<pair<int, int>> adj[N];
inline void sol([[maybe_unused]]int __testcase_id) {
int n, m; cin >> n >> m;
for (int i = 1; i <= m; ++i) {
int l, r; cin >> l >> r;
adj[l - 1].emplace_back(r, 0);
adj[r].emplace_back(l - 1, 0);
} for (int i = 1; i <= n; ++i) adj[i].emplace_back(i - 1, 1), adj[i - 1].emplace_back(i, 1);
deque<int> q;
memset(dis, -0x3f, sizeof dis);
dis[0] = 0, q.emplace_back(0);
while (q.size()) {
int t = q.front(); q.pop_front();
for (auto &[g, w] : adj[t]) if (dis[g] < -inf / 2) {
dis[g] = dis[t] + w;
if (!w) q.emplace_front(g);
else q.emplace_back(g);
}
}
for (int i = 1; i <= n; ++i)
if (dis[i - 1] > dis[i]) cout << 1;
else cout << 0;
cout << '\n';
}
} // namespace lowspeed_song:::
难度：紫
鲜活指数：8
喜欢的话，留下你的评论吧～