【LOJ2391】港口设施

2023-10-30 04:18

文章标签 设施港口 loj2391

本文主要是介绍【LOJ2391】港口设施，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目传送门

题目描述
题目译自 JOISC 2017 Day1 T2「港湾設備 / Port Facility」

JOI 港口虽然很小，却非常繁忙。
JOI 港口放置集装箱的结构可视为两个本质不同的栈。每天从船上卸下的集装箱会被压入某个栈，而被运出港口的集装箱则从栈顶弹出。
今天 JOI 港口会迎来个集装箱，它们在今天内会被运出港口。今天出入口有条记录，每条记录都表示一个集装箱到港或离港。
第个集装箱的到港记录为，离港记录为。
我们把个集装箱分别放在哪个栈称为一个方案。求放置集装箱的方案数。

输入格式
第一行有一个整数。在接下来的行中，第行有两个整数，用空格分隔。

输出格式
一个整数，表示放置集装箱的方案数。

样例

样例输入 1

样例输出 1

样例说明 1
为了方便叙述，将这两个栈分别称为 A 和 B 。
四种方案分别为：ABAA（第个集装箱放在 A，第个集装箱放在 B，以此类推），ABAB，BABA，BABB。

首先我们根据样例1画出

分析
观察上图，我们可以发现，当两个箱子进入港口和离开港口的区间向交叉（并不包含），则他们必定是不能存在同一个栈内的，因为这样无法实现所要求的出入栈顺序（仔细思考一下）。
于是我们可以将符合这个条件的两个箱子都连起来，表示这两个箱子必须分开。这不就是二分图吗？那我们就由此建立二分图：
我们发现这个二分图种有两个连通块，每个连通块都有两种染色方案（如1-2-3可以染成A-B-A或者B-A-B)，因此这个二分图总的染色方案有2^2种，即箱子有4种放置方案。

解体思路
先对符合要求的点进行连边，再进行染色，如果不是二分图，则不符合要求直接输出0；若是二分图，计算二分图内连通块的数量n，答案即为2^n。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N=10000005;
const int mod=1e9+7;
vector<int> e[N];//存边 
int col[N];//各箱子颜色 
int nxt[N],fa[N],le[N],id[N<<1],a[N],cnt;//nxt和fa用于防止重复连边 筛去包含的情况 
int n;									//le表示箱子到达位置,a存到达顺序 
ll ans=1;								//id存各个时刻进入或出去的箱子 //可以对每个维护一个nxt表示向右最大的同色的位置//从左往右用并查集维护
void qm(int a,int b)//快速幂
{while(b>0){if(b%2==1)ans=(ans*a)%mod;b=b/2;a=(1ll*a*a)%mod;}
}inline int find(int x)
{return fa[x]==x?x:fa[x]=find(fa[x]);
}inline void addedge(int u,int v){//加边 e[u].push_back(v),e[v].push_back(u);
}int dfs(int u){//染色 for(int i=0;i<e[u].size();i++){int v=e[u][i];if(col[v]!=0&&col[v]==col[u])return 0;if(col[v]==0){col[v]=-col[u];if(!dfs(v))return 0;}}return 1;
}int main(){int l,r;cin>>n;for(int i=1;i<=n;i++){scanf("%d%d",&l,&r);id[l]=id[r]=i;}for(int i=1;i<=n;i++)nxt[i]=i,fa[i]=i;//初始化nxt fa fa[n+1]=n+1;for(int i=1;i<=2*n;i++){int p=id[i];if(!le[p])a[++cnt]=p,le[p]=cnt; else{//已有左端点，进行加边操作 int u=le[p];fa[u]=find(u+1);for(int j=fa[u],k;j<=cnt;j=k)addedge(a[j],p),k=find(nxt[j]+1),nxt[j]=cnt;}}int cnt=0;memset(col,0,sizeof(col));for(int i=1;i<=n;i++)//对各连通块染色 if(col[i]==0){col[i]=1;if(dfs(i))cnt++;else {puts("0");return 0;}}qm(2,cnt);cout<<ans;return 0;
}