算法
(差分约束系统)
注意到
$A_{L_i}, A_{L_i + 1}, \cdots, A_{R_i}$ 中至少有 $X_i$ 个 $1$ 等价于 $A_{L_i}, A_{L_i + 1}, \cdots, A_{R_i}$ 中至多有 $(R- L + 1) - X_i$ 个 $0$
于是原问题就变成了求满足条件的且 $0$ 出现的次数最多的序列。
记 $S_i$ 表示前 $i$ 个数中至多有多少个 $0$
根据题意可以得到如下不等式组
$ \begin{cases} S_{i + 1} \leqslant S_{i} + 1\\\ S_i \leqslant S_{i + 1}\\\ S_{R} \leqslant S_{L - 1} + (R- L + 1) - X \end{cases} $
这个不等式组显然满足差分约束系统的结构。
下面考虑建图:
- $S_{i + 1} \leqslant S_{i} + 1$ 可以化作 $i \to i + 1$,且边权为 $1$ 的有向边
- $S_i \leqslant S_{i + 1}$ 可以化作 $i + 1 \to i$,且边权为 $0$ 的有向边
- $S_{R} \leqslant S_{L - 1} + (R- L + 1) - X$ 化作 $L - 1 \to R$,且边权为 $(R- L + 1) - X$ 的有向边
然后以点 $1$ 作为起点跑一遍 Dijkstra
即可。
最后第 $i$ 个数为对 $(S_i - S_{i - 1})$ 取反,这里$S_i$ 表示 $S[1 \dots i]$ 中至多有多少个 $0$,$(S_i - S_{i - 1})$ 只有 $0$ 和 $1$ 两种可能。
另外,这题似乎卡 SPFA
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::vector;
using P = std::pair<int, int>;
using std::greater;
using std::priority_queue;
struct Edge {
int to, cost;
Edge(int to = 0, int cost = 0): to(to), cost(cost) {}
};
int main() {
int n, m;
cin >> n >> m;
vector<vector<Edge>> g(n + 1);
rep(i, n) g[i].emplace_back(i + 1, 1);
rep(i, n) g[i + 1].emplace_back(i, 0);
rep(i, m) {
int l, r, x;
cin >> l >> r >> x;
--l;
g[l].emplace_back(r, (r - l) - x);
}
const int INF = 1001001001;
vector<int> dist(n + 1, INF);
priority_queue<P, vector<P>, greater<P>> q;
dist[0] = 0;
while (q.size()) {
auto [d, v] = q.top(); q.pop();
if (dist[v] != d) continue;
for (Edge e : g[v]) {
int nd = d + e.cost;
if (dist[e.to] <= nd) continue;
dist[e.to] = nd;
q.emplace(nd, e.to);
}
}
vector<int> ans(n);
rep(i, n) ans[i] = !(dist[i + 1] - dist[i]);
rep(i, n) cout << ans[i] << " ";
return 0;
}