[loj 2391]「JOISC 2017 Day 1」港口设施

题目链接

https://loj.ac/problem/2391

题解

Subtask 2

容易发现,当 \(A_i \lt A_j \lt B_i \lt B_j\) 时,\(i,j\) 不能安排在同一个栈中。

如果在两个不能放在同一个栈的元素间连一条边,容易发现这是一个二分图染色的模型。

设最后形成了 \(x\) 个连通分量,因为每个连通分量都有两种染色方案,所以总方案数为 \(2^x\)。

当然,如果有一个连通分量不是二分图,则染色无法进行,答案就是零。

暴力枚举点对连边可以做到 \(O(n^2)\) 的时间复杂度,从而得到 \(22\) 分。

Subtask 4

上面做法的瓶颈在于连的边太多了。我们需要降低边的规模。

先将所有区间按左端点升序排序,然后按右端点从小到大的顺序考虑每一个元素。

容易发现每个元素能连的边,在数组里是一个连续的区间。

我们设第一次连边的范围是 \([l_1,r_1]\),第二次连边的范围是 \([l_2,r_2]\)。

如果这两个范围有重叠部分,则重复向重叠部分连边可能会形成偶环。偶环是不影响结果的,所以第一次连边结束后,第二次连边只需向重叠部分的其中一个点连边即可。

详细来说,设 \(nxt_i\) 表示连完这个点后下一个要连的点。

以上面为例,第一次连边结束后,第一次连的边的 \(nxt\) 指针都会指向 \(r_1\) 后面的那个元素。

可以证明,这样做的时间复杂度为 \(O(n \log n)\),可以通过本题。

#include <cstring>
#include <iostream>
#include <vector>
#define MOD 1000000007
using namespace std;
int p[2000005],vis[1000005],col[1000005];
vector<int> e[1000005];
int fa[2000005],nxt[1000005];
int cnt;
int find(int x)
{
 return fa[x]==x?x:fa[x]=find(fa[x]);
}
bool dfs(int u,int c)
{
 col[u]=c;
 for(auto v:e[u])
  if(col[v]==col[u])return false;
  else if(col[v]==-1)
  {
   if(!dfs(v,c^1))return false;
  }
 return true;
}
int main()
{
 int n;
 cin>>n;
 for(int i=1;i<=n;i++)
 {
  int l,r;
  cin>>l>>r;
  p[l]=p[r]=i;
 }
 for(int i=1;i<=n+1;i++)
  fa[i]=i,nxt[i]=i;
 for(int i=1;i<=2*n;i++)
  if(!vis[p[i]])
   vis[p[i]]=++cnt;
  else
  {
   int id=vis[p[i]],t;
   fa[id]=find(id+1);
   for(int j=fa[id];j<=cnt;j=t)
   {
    e[id].push_back(j);
    e[j].push_back(id);
    t=find(nxt[j]+1);
    nxt[j]=cnt;
   }
  }
 memset(col,-1,sizeof(col));
 int ans=1;
 for(int i=1;i<=n;i++)
  if(col[i]==-1)
  {
   if(dfs(i,0))ans=ans*2%MOD;
   else ans=0;
  }
 cout<<ans<<endl;
 return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据