【文文殿下】 Teleporters 传送器 题解

【文文殿下】 Teleporters 传送器 题解

一个结论：“从出发点开始走绝对不会出现死循环”。
考虑如何证明这个结论（这会直接提示正解）：
我们对数轴分段，对于任意一个传送门，把当前段分成两段。
对于每一段（除了第一段）我们总会有一个到达这个段的方法：走一个传送门。这个传送门的位置是这个段左边第一个传送门，我们查看这个传送门通向哪里，然后把那个点与这个点连一条有向边。
对于每一段（除了最后一段）我们总会有一个离开这个段的方法，和上面类似建图。
我们考虑，我们在行走过程中，由于第一个段没有入度，所以我们绝对不会回到第一个段。
由于最后一个段没有出度，所以我们绝对不会向其他地方循环。
由于除了开头和结尾的特殊段，其他任何段有且仅有一个入度和出度，所以我们一定会从一号段到达最后一个段离开。
证毕。
我们发现，除了从一号点到最后一个点是一条简单路径，其他的点一定在一个环里（可以画图理解）。
考虑我们新加一个传送门，会导致这张有向图如何变化？
我们有三种加的方式：

• 一：用一对传送门把两个不在同一个连通块的点链接。
  这会直接导致有两个点一分为二，然后他们所在的连通块合并。
  如果我们合并路径和环，我们会得到一个更长的路径。
  如果我们合并环和环，我们会得到一个更大的环。
  
• 二：用一对传送门链接同一个连通块里两个点。
  这会直接导致这个连通块一分为二。这对答案没有任何帮助。
  
• 三：这对传送门放在某对传送门的内部，这会导致我们永远无法访问到这个传送门，所以他单独成一个点。

题解显而易见，我们把所有环从大到小排序。
然后从大到小，用传送门把他们用方法一连到我们的路径里。
如果连完以后，传送门还有剩余，我们可以不断做方法三和方法一，把他们累加到答案里。
细节：如果只剩一个传送门，我们就把他加在末尾。
时间复杂度(O(nlogn))
进一步优化：
我们发现复杂度瓶颈在于排序，但是由于排序的值非常小，我们使用桶排序。
时间复杂度到达理论下届：(O(n))
但是我懒得写线性的，下面给出(O(nlogn))的代码，吸氧能过。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e6+10;
struct qwq {int inc,out;
}s[maxn];
struct QQQ {int l,r;
}L[maxn];
struct QAQ {int v,bl,type;const bool operator < (const QAQ& rhs) const {return v<rhs.v;}
}v[maxn];
int n,m,cnt,ind[maxn];
int sz[maxn],ans,tot;
bool vis[maxn];
int find(int x) {return lower_bound(v+1,v+1+cnt,(QAQ){x,0,0})-v;
}
void dfs(int cur,int pos) {while(!vis[cur]) {vis[cur]=1;sz[pos]++;int nxt;if(v[cur].type) nxt = find(L[v[cur].bl].l+1);else nxt=find(L[v[cur].bl].r+1);cur = nxt;}
}
int main() {scanf("%d%d",&n,&m);for(int i=1;i<=n;++i) {scanf("%d%d",&L[i].l,&L[i].r);v[++cnt].v=L[i].l;v[cnt].bl=i;v[cnt].type=0;v[++cnt].v=L[i].r;v[cnt].bl=i;v[cnt].type=1;}sort(v+1,v+1+cnt);int cur = 1;while(cur!=cnt+1) {vis[cur]=1;++ans;int nxt;if(v[cur].type) nxt = find(L[v[cur].bl].l+1);else nxt=find(L[v[cur].bl].r+1);cur = nxt;}vis[cur]=1;for(int i=1;i<=cnt;++i) {if(!vis[i]) {dfs(i,++tot);}}
#ifdef DEBUGprintf("%dn",ans);printf("%dn",tot);for(int i=1;i<=tot;++i) printf("%d ",sz[i]);
#endifsort(sz+1,sz+1+tot,greater<int>());for(int i=1;i<=tot&&m;++i) {ans+=2;--m;ans+=sz[i];}if(m) {if(m&1) --m,++ans;ans+= 2*m;}printf("%dn",ans);return 0;
}

转载于:.html