带花树略解

2019-09-07

右上角的时间不是文章的发布时间，更不是文章的最后修改时间。真实的文章修改记录请查看 https://github.com/Wallbreaker5th/Wallbreaker5th.github.io

带花树是一种用于解决一般图最大匹配的算法，利用了匈牙利算法的思想。

前置知识

匈牙利算法
BFS 树
并查集

定义

奇环/偶环：长度为奇数/偶数的环。
花（blossom）：在 BFS 过程中，遍历到的边与 BFS 树边构成的奇环；
柄（stem）：从 BFS 树根到奇环中深度最浅的点的路径；
蒂（tip）：奇环中在柄上的那个点。

算法思路

首先我们考虑匈牙利算法在 BFS 时如何工作：

当我们搜索到点 $u$，对于边 $(u,v)$：

如果 $v$ 没有被匹配，证明我们得到了一条增广路径；
- 此时我们将增广路径上的每条边翻转，并结束 BFS；
如果 $v$ 不在树中，继续 BFS；
如果 $v$ 在树中，并且 $(u,v)$ 使图中出现偶环，忽略它；
“$v$ 在树中，并且 $(u,v)$ 使图中出现奇环”（即图中出现了花）是不可能的，因为这是二分图。

more >>

展开全文 >>

题解-CF1200B-Block Adventure

2019-08-22

右上角的时间不是文章的发布时间，更不是文章的最后修改时间。真实的文章修改记录请查看 https://github.com/Wallbreaker5th/Wallbreaker5th.github.io

题目链接

采用贪心策略

假如该列不够高，我们只能往上摞

否则我们将尽可能多的方块挖掉，扔进背包

注意：挖掉的方块数量不能超过该列高度（因为这个 WA 了两次）

中途一旦方块不够用就 GG 了

#include<bits/stdc++.h>
using namespace std;
 
int getint(){
    int ans=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')f=-1;
        c=getchar();
	}
    while(c>='0'&&c<='9'){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans*f;
}
int h[1010];
int main(){
	int t=getint();
	while(t--){
		long long n=getint(),m=getint(),k=getint();
		for(int i=0;i<n;i++){
			h[i]=getint();
		}
		bool ok=1;
		for(int i=0;i<n-1;i++){
			if(h[i]<h[i+1]-k)m-=h[i+1]-h[i]-k;
			else m+=min((long long)h[i],h[i]-h[i+1]+k);
			if(m<0)ok=0;
			//cout<<"? " <<m<<endl;
		}
		puts(ok?"YES":"NO");
	}
	return 0;
}

展开全文 >>

题解-CF1200D-White Lines

2019-08-22

右上角的时间不是文章的发布时间，更不是文章的最后修改时间。真实的文章修改记录请查看 https://github.com/Wallbreaker5th/Wallbreaker5th.github.io

题目链接

这里介绍一种 $O(\text{玄学})$（应该是 $O(n(n-k)\log k)$？）的做法

当时想到此做法时：计算器算一下 $n^2\log n$ 好像过不了？写一下试一下
写完之后：试一下极端数据，跑了 2s+怕是过不了，交一发试一下（一不小心忘取消 freopen，还好挂在样例不扣分，再交一次）
过了 Pretest 之后：这都能 PP？坐等 FST。
第二天一看：Accepted

考虑枚举橡皮擦的位置，并分别求出橡皮擦在每个位置时，行和列分别会增加多少个 WL(White Line(s)，下同)

这里以计算行上增加的 WL 为例：

先预处理出每一（有黑色的）行的黑色段的左端与右端

枚举橡皮擦在哪几行，将这几行的黑色段的左端与右端排序。然后从左往右枚举橡皮擦的位置，并维护指针 $pl,pr$，集合 $s$。

当橡皮擦移动到一个新位置时，右移 $pl$ 扫过所有已经退出橡皮擦范围的（行的黑色段的）左端，并从集合 $s$ 中删除这一行（如果 $s$ 中没有这一行就打上标记，代表这一行不可能变成 WL）；然后右移 $pr$ 扫过所有已经进入橡皮擦范围的（行的黑色段的）右端，假如这一行没有标记，便将这一行插入集合 $s$。

最后枚举每一格取 $\max$ 即可

下面代码有些乱，set<pair<int,pair<int,bool> > >e 可以直接排序维护，set<int> s 可以直接用一个数组记录 tag：

#include<bits/stdc++.h>
using namespace std;
 
int getint(){
    int ans=0,f=1;
    char c=getchar();
    while(c>'9'||c<'0'){
        if(c=='-')f=-1;
        c=getchar();
	}
    while(c>='0'&&c<='9'){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans*f;
}
bool a[2010][2010];
int rl[2010],rr[2010],cl[2010],cr[2010];//行（列）的黑色段的左（优、上、下端）
int rcnt[2010][2010],ccnt[2010][2010];//橡皮擦在此处时，行、列增加的 WL 数量
int main(){
	int n=getint(),k=getint();
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			char c=getchar();
			while(c>'Z'||c<'A')c=getchar();
			a[i][j]=(c=='B');
		}
	}
	memset(rl,0x3f,sizeof(rl));
	memset(cl,0x3f,sizeof(cl)); 
	int qaq=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(a[i][j]){
				cl[j]=min(cl[j],i);
				cr[j]=max(cr[j],i);
				rl[i]=min(rl[i],j);
				rr[i]=max(rr[i],j);
			}
		}
	}
	for(int i=0;i<n;i++){
		qaq+=(cl[i]>cr[i]);//本身就是 WL
		qaq+=(rl[i]>rr[i]);
	}
	for(int i=0;i<n-k+1;i++){
		set<pair<int,pair<int,bool> > >e;//所有行的黑色段的左（右）端点
		unordered_set<int>s,gg;//gg:被标记的集合
		for(int j=i;j<i+k;j++){
			if(rl[j]>rr[j])continue;//本身就是 WL 的行已经单独计算
			e.insert(make_pair(rl[j],make_pair(j,0)));
			e.insert(make_pair(rr[j],make_pair(j,1)));
			//cout<<"r "<<rl[j]<<" "<<rr[j]<<endl;
		}
		auto itl=e.begin(),itr=e.begin();//即题解中的 pl,pr
		for(int j=0;j<n-k+1;j++){
			//cout<<"?? "<<itr->first<<" "<<itl->first<<endl;
			while(itr!=e.end()&&(itr->second.second==0||itr->first<=j+k-1)){
				//if(itr->second.second)cout<<">. "<<itr->second.first<<endl;
				if(itr->second.second&&!gg.count(itr->second.first))
					s.insert(itr->second.first);
				++itr;//右移 pr
			}
			while(itl!=e.end()&&(itl->second.second==1||itl->first<j)){
				//if(!itl->second.second)cout<<"<. "<<itl->second.first<<endl;
				auto it=s.find(itl->second.first);
				if(itl->second.second==0&&it!=s.end())
					s.erase(it);
				else gg.insert(itl->second.first);
				++itl;//右移 pl
			} 
        //上面两个指针的处理顺序可以交换
			rcnt[i][j]=s.size();
			//cout<<"rcnt "<<i<<" "<<j<<" "<<rcnt[i][j]<<endl;
		}
	}
	for(int i=0;i<n-k+1;i++){//列同理
		set<pair<int,pair<int,bool> > >e;
		set<int>s,gg;
		for(int j=i;j<i+k;j++){
			if(cl[j]>cr[j])continue; 
			e.insert(make_pair(cl[j],make_pair(j,0)));
			e.insert(make_pair(cr[j],make_pair(j,1)));
		}
		auto itl=e.begin(),itr=e.begin();
		for(int j=0;j<n-k+1;j++){
			//cout<<"?? "<<itr->first<<" "<<itl->first<<endl;
			while(itr!=e.end()&&(itr->second.second==0||itr->first<=j+k-1)){
				//if(itr->second.second)cout<<">. "<<itr->second.first<<endl;
				if(itr->second.second&&!gg.count(itr->second.first))
					s.insert(itr->second.first);
				++itr;
			}
			while(itl!=e.end()&&(itl->second.second==1||itl->first<j)){
				//if(!itl->second.second)cout<<"<. "<<itl->second.first<<endl;
				auto it=s.find(itl->second.first);
				if(itl->second.second==0&&it!=s.end())
					s.erase(it);
				else gg.insert(itl->second.first);
				++itl;
			} 
			ccnt[j][i]=s.size();
			//cout<<"ccnt "<<j<<" "<<i<<" "<<ccnt[j][i]<<endl;
		}
	}
	int ans=0;
	for(int i=0;i<n-k+1;i++){
		for(int j=0;j<n-k+1;j++){
			//cout<<i<<" "<<j<<" "<<ccnt[i][j]<<" "<<rcnt[i][j]<<endl;
			ans=max(ans,ccnt[i][j]+rcnt[i][j]);
		}
	}
	cout<<ans+qaq;
	return 0;
}

展开全文 >>

破壁人五号

带花树略解

前置知识

定义

算法思路

题解-CF1200B-Block Adventure

题解-CF1200D-White Lines

放映室