专栏文章

AT_agc056_c [AGC056C] 01 Balanced 题解

OOIer_Tan
AT_agc056_c题解参与者 3已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mipbx1r0
此快照首次捕获于
2025/12/03 09:29
3 个月前
此快照最后确认于
2025/12/03 09:29
3 个月前
查看原文
差分约束好题啊，前两天教练刚讲了，然后模拟赛就出这道。
然而教练卡 SPFA 失败了 /ng。

思路

注意到将答案序列中的 0→−10\to-1 后，限制可以被转化为 suml−1=sumrsum_{l-1}=sum_r，以及根据相邻两项之差有 ∣sumi−1−sumi∣≤1\lvert sum_{i-1}-sum_i\rvert\le1，然后再将这个绝对值拆开，差分约束的形式就出来了：
{suml−1−sumr≤0sumr−suml−1≤0sumi−1−sumi≤1sumi−sumi−1≤1⋯\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/10/1，因此直接 01BFS 即可。
时间复杂度 O(n+m)O(n+m)。

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

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

代码

CPP
#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 ;
}

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...