【题解】AGC056C 差分约束 思维 建模

好题，考察了对差分约束较深的理解。 首先限制区间 $(l,r]$ 内恰好有 $\frac {r-l} 2$ 个 $1$，可以考虑将限制转化为前缀和数组上的限制，即 $S_r-S_l=\frac {r-l} 2$，又因为前缀和本身的限制关系 $S_{i}-S_{i-1}\in[0,1]$，可以得出一个差分约束的关系： $$ \left\{ \begin{aligned} &S_r-S_l=\frac {r-l} 2\\ &S_i\leq S_{i-1}+1\\ &S_{i-1}\leq S_i\\ \end{aligned} \right. $$ 直接将等于边拆成大于小于边做差分约束求字典序最小的 $S$，因为有负权边会被卡成 $O(n^2)$。 考虑将等号代表的关系使用一个代表元表示（$S_i=S_{del(i)} + c_i$），这样可以避免掉上面的负权边，但是第二类边可能会出现 $S_i+c_i\leq S_j+c_j$ 移项得到 $S_i\leq S_j+c_j-c_i$ 在 $c_i > c_j$ 时同样会出现负权边。 考虑如何避免负权边，之所以会出现负权边是因为第一类的传递关系中会涉及到量的改变，我们试图建立一种直接的等价类关系来描述第一类关系： 考虑式子拆开成一个左侧只和 $l$ 相关右侧只和 $r$ 相关的等式：$2S_r-r=2S_l-l$，这样我们就把传递关系改成了一种等价关系，定义 $x_i=2S_i-i$，则上面三个式子分别变成了： $$ \left\{ \begin{aligned} &x_i=x_j\\ &x_i\leq x_{i-1}+1\\ &x_{i-1}\leq x_i+1\\ \end{aligned} \right. $$ （当然还有 $x_i\neq x_{i-1}$，这个条件会在后面的差分约束中天然被满足） 所以直接将所有第一种关系相同的 $x_i$ 用同一个变量 $x_{del(i)}$ 表示，然后对所有代表变量解决差分约束问题。 同样的，我们只需要最小化 $x$ 的字典序就可以最小化 $S$ 的字典序，直接 bfs 跑差分约束即可，因为我们求的是字典序最小解，可以证明不会出现 $x_i=x_{i-1}$ 的情况。 接下来我们来证明使用差分约束系统构造出的解天然满足 $x_i\neq x_{i-1}$：首先缩起来的代表元素一定满足代表的都是奇偶性相同的元素，接下来这个差分约束系统只会对若干个奇数下标等价类的 $x$ 的和偶数下标等价类的代表元之间连权为 $1$ 的边，故我们构造出来的差分约束系统是一个有向的二分图（只在奇数代表元和偶数代表元之间有边），所以通过差分约束得到的最短路的奇偶性是确定的，只和下标奇偶性相关，故 $x_i$ 和 $x_{i-1}$ 奇偶性一定不同。 代码：（为方便使用了并查集进行缩等价类，复杂度会多一个 $n\alpha(n)$） ```cpp #include<bits/stdc++.h> #define ll long long #define all(x) x.begin(),x.end() #define rep(i,x,y) for(auto i(x);i<=(y);++i) #define Rep(i,x,y) for(auto i(x);i>=(y);--i) using namespace std; const int N = 1e6 + 20 ; int n , m , x[N] , fa[N] , ptr ; vector <int> ed[N] ; inline int find (int x) { while (x ^ fa[x]) x = fa[x] = fa[fa[x]] ; return x; } signed main ( ) { ios :: sync_with_stdio(false) , cin.tie(0) , cout.tie(0); cin >> n >> m ; iota (fa,fa+n+1,0); rep (i,1,m) { int l , r ; cin >> l >> r ; -- l ; int gl = find (l) , gr = find (r) ; if(fa[gl] ^ gr) fa[gl] = gr ; } rep (i,1,n) { ed[find(i)].emplace_back (find(i - 1)) ; ed[find(i - 1)].emplace_back (find(i)) ; } memset(x,-1,sizeof x); x[find(0)] = 0; vector <int> q = {find(0)} ; while (ptr < (int)q.size( )) { int u = q[ptr ++]; for (int v : ed[u]) { if (!~x[v]) { x[v] = x[u] + 1 ; q.emplace_back(v) ; } } } rep (i,1,n) if (x[find(i)] > x[find(i - 1)]) cout << 0 ; else cout << 1 ; return 0 ; } ```