AT_agc056_c [AGC056C] 01 Balanced 题解

· · 题解

差分约束好题啊，前两天教练刚讲了，然后模拟赛就出这道。

然而教练卡 SPFA 失败了 /ng。

思路

注意到将答案序列中的 0\to-1 后，限制可以被转化为 sum_{l-1}=sum_r，以及根据相邻两项之差有 \lvert sum_{i-1}-sum_i\rvert\le1，然后再将这个绝对值拆开，差分约束的形式就出来了：

\begin{cases} sum_{l-1}-sum_{r}\le0\\ sum_{r}-sum_{l-1}\le0\\ sum_{i-1}-sum_i\le1\\ sum_{i}-sum_{i-1}\le1\\ \cdots \end{cases}

然后注意到边权全都为 0/1，因此直接 01BFS 即可。

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

感性理解最短路就是字典序最小

注意到我们的起始点是 sum_0=0，并且每次都是使得 sum_i 尽量小，因此可以得出按照最短路求得的就是字典序最小的答案。

代码

#include <bits/stdc++.h>

#ifndef CRT
#define endl '\n'
#endif

using namespace std ;

typedef long long ll ;
typedef unsigned long long ull ;
typedef long double ld ;

const ll N = 2e6 + 5 ;

ll n , m ;

struct node 
{
    ll v , w ;
    node () {} 
    node ( const ll & v , const ll &w ) : v ( v ) , w ( w ) {}
} ;

vector <node> edge [N] ;

ll cnt ;

ll b [N] ;

int main ()
{
#if not defined ( CRCC ) and not defined ( ONLINE_JUDGE )
    freopen ( "measure.in" , "r" , stdin ) ;
    freopen ( "measure.out" , "w" , stdout ) ;
#endif
    ios::sync_with_stdio ( 0 ) ;
    cin.tie ( 0 ) ;
    cout.tie ( 0 ) ;
    cin >> n >> m ;
    for ( ll i = 1 ; i <= m ; i ++ )
    {
        // cin >> q [i].l >> q [i].r ;
        ll l , r ;
        cin >> l >> r ;
        edge [l - 1].emplace_back ( r , 0 ) ;
        edge [r].emplace_back ( l - 1 , 0 ) ;
    }
    for ( ll i = 1 ; i <= n ; i ++ )
    {
        edge [i - 1].emplace_back ( i , 1 ) ;
        edge [i].emplace_back ( i - 1 , 1 ) ;
    }
    memset ( b , 0x3f , sizeof b ) ;
    deque <pair <ll,ll>> q ;
    q.emplace_front ( 0 , 0 ) ;
    b [0] = 0 ;
    while ( q.size () )
    {
        auto now = q.front () ;
        q.pop_front () ;
        for ( auto nxt : edge [now.first] )
        {
            if ( b [nxt.v] > b [now.first] + nxt.w )
            {
                if ( nxt.w )
                {
                    b [nxt.v] = now.second + 1 ;
                    q.emplace_back ( nxt.v , now.second + 1 ) ;
                }
                else
                {
                    b [nxt.v] = now.second ;
                    q.emplace_front ( nxt.v , now.second ) ;
                }
            }
        }
    }
    for ( ll i = 1 ; i <= n ; i ++ )
    {
        cout << ( b [i] - b [i - 1] < 0 ) ;
    }
    return 0 ;
}