[JOISC 2017 Day1] 港湾设备题解

FFTotoro · 2024-12-22 19:36:58 · 题解

模拟赛赛时想到的一种很简洁的做法，好想好写且只需要使用 std::set，故在此记录一下。

令 l_i 与 r_i 分别为集装箱 i 的进 / 出港时间，那么本题有十分简洁的结论：如果 \exist i\ne j 使得 l_i<l_j<r_i<r_j，那么这两个集装箱一定不能放在同一个栈内。于是 O(n^2) 做法就很简单了，只需要暴力枚举 i,j 并考虑建图：如果 i,j 不能在同一个栈内那么将 i,j 间连一条无向边；最终的图如果不是二分图必然无解，否则设连通块数量为 c，答案则为 2^c。

进一步地，对于每个集装箱，考虑其“在港时间”即 [l_i,r_i]：将所有集装箱按照 l_i 排序后依次加入，假设当前扫到了一个区间 [l_i,r_i]，那么先删除所有满足 r_j<l_i 的 j（称这个过程为剔除）：此时我们只需要考虑场上 r_j<r_i 的所有 j，它们可以与 i 进行连边。

考虑优化这个过程——这一些满足条件的 j 对应的 r_j 一定是当前存在于场上的所有 r 中一段连续的元素，于是将 i 对它们暴力连边后，仅取最小的 r_j 对应的 j 保留在场上（作为一个“代表元”），其他的扔进另一个容器 s 里头（称这个过程为挑选）。当这个代表元 j 在“剔除”过程中被删除时，用它在 s 中的后继（即最小的 r_k 使得 r_k>r_j 对应的 k）作为新的代表元，解法正确性就可以得到保证。

均摊一下上述所有的操作只会进行 O(n) 次，而我们使用 std::set 维护，所以时间复杂度为 O(n\log n)。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int p=1e9+7;
inline int qpow(int a,int b){
  int r=1;
  while(b){
    if(b&1)r=1ll*r*a%p;
    a=1ll*a*a%p,b>>=1;
  }
  return r;
}
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,q=0; cin>>n;
  vector<pii> a(n);
  for(auto &e:a){
    cin>>e.first>>e.second;
    e.first--,e.second--;
  }
  sort(a.begin(),a.end());
  set<pii> s1,s2;
  /* s1 为所有可以留在场上的元素：
     换句话说，就是包含了所有在“挑选”过程中保留或者没保留的所有元素；
     它的作用与上文中所述的“容器 s”的作用相同。
     s2 为所有的代表元和还没有被连边的元素。
  */
  vector<vector<int> > g(n);
  for(int i=0;i<n;i++){
    int l,r; tie(l,r)=a[i];
    while(!s1.empty()&&s1.begin()->first<l)s1.erase(s1.begin());
    // 清空容器 s 中应该被“剔除”的元素
    while(!s2.empty()&&s2.begin()->first<l){
      auto p=s1.lower_bound(*s2.begin());
      if(p!=s1.end())s2.emplace(*p);
      s2.erase(s2.begin());
    } // “剔除”代表元的过程，要从 s1 中找后继
    auto p=s2.begin();
    if(p!=s2.end()&&p->first<r){
      int ps=p->second;
      g[i].emplace_back(ps);
      g[ps].emplace_back(i);
      for(auto it=next(p);it!=s2.end()&&it->first<r;it=s2.erase(it)){
        g[i].emplace_back(it->second);
        g[it->second].emplace_back(i);
      } // “挑选”过程，暴力连边，并删除非代表元
    }
    s1.emplace(r,i),s2.emplace(r,i); // 将其加入
  }
  vector<int> c(n,-1);
  auto dfs=[&](auto &&self,int u)->void{
    for(int i:g[u]){
      if(c[i]<0)c[i]=!c[u],self(self,i);
      else if(c[i]==c[u])cout<<"0\n",exit(0);
    }
  }; // 二分图染色
  for(int i=0;i<n;i++)
    if(c[i]<0)c[i]=0,dfs(dfs,i),q++;
  cout<<qpow(2,q)<<endl;
  return 0;
}

[JOISC 2017 Day1] 港湾设备 题解

[JOISC 2017 Day1] 港湾设备题解