CF R638 div2 F Phoenix and Memory 贪心线段树构造 Hall定理

LINK：Phoenix and Memory

这场比赛标题好评都是以凤凰这个单词开头的有凤来仪吧.

其实和Hall定理关系不大。

不过这个定理有的时候会由于先简述一下。

对于一张二分图左边集合为S 右边集合为T 那么有完备匹配时最大匹配数为 min(|S|,|T|).

这里不妨假设|S|<=|T|.

若存在完备匹配那么对于任意集合\(s\in S\)都有s连出的边>=|s|.

这个定理是一张二分图具有完备匹配的充分必要条件。

先证明必要性：如果不存在那么一定有点无法匹配到。

再证明充分性：反证法,如果满足这个条件但是形不成完备匹配考虑S中那个没有被匹配的点w w一定有向外发出的未匹配边考虑如果这条边的另一端的点如果被匹配了那么另外一端的点的对应匹配点还应该有至少一条出边一直往复

可以发现一定有增广路的存在。

这道题可以看成一张二分图保证有解那么必然满足Hall定理。(不过没什么用。

考虑先求出一个合法解点匹配线段问题考虑贪心。

将线段按照左端点进行排序后逐步分配位置当前位置必然要分配给右端点最近的那个这样给后面的局面不会带来更差的结果。

考虑是否存在两组解或多组解。进一步分析有两组解的性质。

对比这两组解可以发现我们刚才求出的解和另外一组解一些位置进行了互换可以发现这是形成大小至少为2的置换.

考虑如果存在>2的置换那么必然最后一个点要连上它之前的点可以发现连上之前较近的点也是合法的。

所以不断进行规约必然存在大小为2的置换也就是说如果有多组解必然存在有两个位置上的数字交换位置就可以得到。

至此需要求出是否位置上的i,j可以进行换位不妨假设 i<j 那么必然存在 aj<=i<j<=bi

考虑枚举j求出这样的一个i 在j~n处查询之前的所有bi 看他们的最大的i值即可因为此时i必然<j 且最大更容易满足条件。

可以利用线段树解决这个问题。

const int MAXN=200010;

int n;

struct wy{int x,y,id;}t[MAXN];

int p[MAXN],a[MAXN],b[MAXN],w[MAXN];

multiset<pii>s;

multiset<pii>::iterator it;

int sum[MAXN<<2];

inline int cmp(wy a,wy b){return a.x<b.x;}

inline int ask(int p,int l,int r,int L)

{

	if(L<=l)return sum[p];

	int mid=(l+r)>>1;

	if(L>mid)return ask(yy,mid+1,r,L);

	return max(ask(zz,l,mid,L),ask(yy,mid+1,r,L));

}

inline void change(int p,int l,int r,int x,int w)

{

	if(l==r){sum(p)=max(sum(p),w);return;}

	int mid=(l+r)>>1;

	if(x<=mid)change(zz,l,mid,x,w);

	else change(yy,mid+1,r,x,w);

	sum(p)=max(sum(zz),sum(yy));

	return;

}

signed main()

{

	freopen("1.in","r",stdin);

	get(n);

	rep(1,n,i)get(a[i]),get(b[i]),t[i]=(wy){a[i],b[i],i};

	sort(t+1,t+1+n,cmp);

	int flag=0;

	rep(1,n,i)

	{

		while(flag+1<=n&&t[flag+1].x==i)

		{

			s.insert(mk(t[flag+1].y,t[flag+1].id));

			++flag;

		}

		it=s.begin();

		p[(*it).S]=i;

		w[i]=(*it).S;

		s.erase(it);

	}

	rep(1,n,i)

	{

		int ww=ask(1,1,n,i);

		if(ww>=a[w[i]])

		{

			puts("NO");

			rep(1,n,j)put_(p[j]);

			puts("");

			swap(p[w[ww]],p[w[i]]);

			rep(1,n,j)put_(p[j]);

			return 0;

		}

		change(1,1,n,b[w[i]],i);

	}

	puts("YES");

	rep(1,n,j)put_(p[j]);

	return 0;

}

巴特西

CF R638 div2 F Phoenix and Memory 贪心线段树构造 Hall定理

最新文章

热门文章

巴特西

CF R638 div2 F Phoenix and Memory 贪心 线段树 构造 Hall定理

最新文章

热门文章

CF R638 div2 F Phoenix and Memory 贪心线段树构造 Hall定理