环链问题

Posted Sep 8, 2023 Updated Mar 16, 2024

By 9 min read

模型

此类问题大多与拓扑序有关，可以拆成三种集合，环，环上带若干条链(基环树)，单条链(只有点数n>边数m存在)

例题

F. Selling a Menagerie

题意：
c[i]表示i的价值，当i在a[i]前面出现时，i的贡献价值为2*c[i]，否则为c[i],求一个顺序使总价值最大，所有a[i],i<=n
思路：
i向a[i]连边,先做个拓扑序,剩下还有数说明有环，在环内找出最小的c[i],当前i在该环排最后即可(题目中集合可分为三种：1.单个环，2.单条边，3.一个环和若干条指向它的边（环指向边不可能存在）)

  
void solve(){
	int n;
	cin>>n;
	vector<int> a(n+1),c(n+1),deg(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		deg[a[i]]++;
	}
	for(int i=1;i<=n;i++)cin>>c[i];
	vector<int> ans;
	vector<bool> vis(n+1);
	auto dfs=[&](auto self,int u)->void{
		if(--deg[a[u]]==0&&!vis[a[u]]){
			vis[a[u]]=1;
			ans.pb(a[u]);
			self(self,a[u]);
		}
	};
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		if(deg[i]==0){
			vis[i]=1;
			ans.pb(i);
			dfs(dfs,i);
		}
	}
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		vector<int> b,C;
		for(int j=i;!vis[j];j=a[j]){
			b.pb(j);
			C.pb(c[j]);
			vis[j]=1;
		}
		int p=min_element(all(C))-C.begin();
		for(int j=0;j<b.size();j++){
			ans.pb(b[(j+1+p)%b.size()]);
		}
	}
	for(auto it:ans)cout<<it<<" ";
	cout<<"\n";
}

D. Cyclic Operations

题意：
给定数组n初始化为0，另外一个数组a(每个数都小于等于n)，和整数k；可以进行无数次下列操作：

做一个数组长度为k， $ [b_1,b_2,b_3,…,b_k] $, $ a_{b{i}}=a_{b_{(i+1)mod(n+1)}} $

可以使数组等于数组a
思路：连边 $i \to a_i $,对于每个集合中的环的个数必须等于k，否则输出NO，连在环上的链可以通过环(在环内再进行一次循环)，消除影响；当k=1时单独考虑，此时不能存在边，必须每个元素自环

  
void solve(){
	int n,m;
	cin>>n>>m;
	vector<int> a(n+1),deg(n+1);
	for(int i=1;i<=n;i++){
		cin>>a[i];
		deg[a[i]]++;
	}
	if(m==1){
		for(int i=1;i<=n;i++){
			if(a[i]!=i){
				cout<<"NO\n";
				return;
			}
		}
		cout<<"YES\n";
		return;
	}
	vector<bool> vis(n+1);
	auto dfs=[&](auto self,int x)->void{
		if(--deg[a[x]]==0&&!vis[a[x]]){
			vis[a[x]]=1;
			self(self,a[x]);
		}
	};
	for(int i=1;i<=n;i++){
		if(deg[i]==0&&!vis[i]){
			vis[i]=1;
			dfs(dfs,i);
		}
	}
	for(int i=1;i<=n;i++){
		if(vis[i])continue;
		int cnt=1;
		vis[i]=1;
		for(int j=a[i];!vis[j];j=a[j]){
			vis[j]=1;
			cnt++;
		}
		if(cnt!=m){
			cout<<"NO\n";
			return;
		}
	}
	cout<<"YES\n";
}

置换环

$ i->a[i] $连边
$ 每个环变为正序的操作数为siz_环-1 $
$ 总操作数为n-cnt_环 $

$ 在置换环中，总有一种方法，用一次调换两个元素，使得一个元素自环，其他成环 $

CF1768D Lucky Permutation

求只有一个逆序对的最小操作数若相邻两数在一个环中，操作数减1，否则加1

map<int,bool> mp;
int cnr;
bool flag;
void dfs(int u){
  if(vis[u])return;
  vis[u]=1;
  mp[u]=1;
  int v=a[u];
  if(mp[u-1]||mp[u+1])flag=1;
  dfs(v);
}
signed main(){
  cin>>t;
  while(t--){
      memset(vis,0,sizeof(vis));
      cur=0,flag=0;
      cin>>n;
      for(int i=1;i<=n;i++)cin>>a[i];
      for(int i=1;i<=n;i++){
          if(!vis[i]){
              cur++;
              mp.clear();
              dfs(i);		
          }
      }
      if(flag)cout<<n-cur-1<<"\n";
      else cout<<n-cur+1<<"\n";
  }
}

CF1677C

题意：
给定一个序列a,b,需要构造一个数组nums,每次赋值若a[i]==b[i]==x，则需满足nums[a[i]]==nums[b[i]],最大化$ \sum_{i=n}^N |nums_{(i+1)\%n}-nums_{i}| $
思路：

容易想到$ a_i \to b_i $ 连边，形成若干个环
对于每个环的赋值,贪心的话肯定是一大一小放,但是这有个问题如果是奇数环,则最后填的数是不会影响整个环的贡献的,如果继续贪心选，那么当前这个数在下一个环中可能会有更大贡献，这就导致答案不对(比如当前最后一个奇数位置选了6 ，然后下一个环选5 2;但是如果当前不选6，则下一个环的贡献为6 2明显更优),因此对于每个奇数环，都减1让它变成偶数环，直接模拟即可
进一步发现，定义山峰为a[i-1]<=a[i]>=a[i+1],山谷为a[i-1]>=a[i]<=a[i+1],其他为山坡,设当前位置数字为x，有以下贡献
- $ 2 \cdot x ,山峰 a_i-a_{i-1} + a_{i+1}-a_i =2*a_i-()$
- $ -2 \cdot x,山谷 a_i-a_{i-1} + a_{i+1}-a_i =()-2*a_i $
- $ 0 山坡|a_i-a_{i-1}|+|a_{i+1}-a_i|=()符号相反所以抵消$ 因此只需计算山峰(山坡大小),设大小为a，则由等差数列公式可推出答案为$ 2a(n-a) $
  P6193 [USACO07FEB] Cow Sorting G
  题意：
  给定长度为n的数组，交换X和Y的代价为X+Y，问变为正序的最小花费
  思路：
看到排序升序，最小交换花费(次数),想到置换环
题目所给的序列并不是permulation,因此使用置换环就需要离散化
对于每个环，因为每次操作都可以让一个元素自环(还原到排序后的位置),因此可以顺着环的最小数字走，则除了最小数字其他数字只贡献一次，而最小数字贡献次数为交换次数
但这并不一定最优，当环中最小数很大时，先将环的最小数与整个序列的最小数换一下，将环中元素排好后再换回来

因此取上面两种情况的min值

  
struct node{
  int val;
  int pos;
  bool operator<(const node&tmp)const{
      return val<tmp.val;
  }
};
struct M{
  int val,x;
};
void solve(){
  int n;
  cin>>n;
  vector<int> adj(n+1),vis(n+1);
  vector<node> e(n+1);
  vector<M> a(n+1); 
  for(int i=1;i<=n;i++){
      cin>>e[i].val;
      e[i].pos=i;
  }
  sort(e.begin()+1,e.end());
  for(int i=1;i<=n;i++){
      a[e[i].pos].val=i;
      a[e[i].pos].x=e[i].val;
  }
  for(int i=1;i<=n;i++){
      adj[i]=a[i].val;
  }
  //for(int i=1;i<=n;i++)cout<<adj[i]<<" \n"[i==n];
  int cnt=0,ans=0;
  for(int i=1;i<=n;i++){
      if(vis[i])continue;
      int x=i;
      int d1=1e15,sum=0;
      int c=0;    
      while(!vis[x]){
          vis[x]=1;
          c++;
          sum+=a[x].x;
          //cout<<sum<<"\n";
          d1=min(d1,a[x].x);
          x=adj[x];
          //cout<<x<<" ";
      }
      if(c==1)continue;
      //cout<<sum<<" "<<d1<<"\n";
      sum-=d1;
      c--;
      int res1=sum+c*d1;
      int res2=1e15;
      if(d1!=e[1].val)res2=(d1+e[1].val)*2+sum+c*e[1].val;
      ans+=min(res1,res2);
  }
  cout<<ans<<"\n";
}

CF1690F Shifting String

给定一个字符串s和序列，每次操作，当前位置i的字符会换成a[i]位置的字符,求最小操作数使其还原
思路：

很明显也是一个置换环的题型
对于单个环来讲
- 如果环内元素都不相同，那么此时最小操作数就是环数
- 如果环内元素有相同的，那么就不一定了，因为n=200所以可以暴力 $ O(n^2) $ 判断
总操作数就是所有环的操作数的最小公倍数

总复杂度:$ O(n^3logn) $

  
void solve(){
  int n;
  string s;
  cin>>n>>s;
  s=" "+s;
  vector<int> adj(n+1),a(n+1);
  vector<bool> vis(n+1);
  for(int i=1;i<=n;i++){
      cin>>a[i];
      adj[i]=a[i];
  }
  ll ans=1;
  for(int i=1;i<=n;i++){
      if(vis[i])continue;
      int x=i;
      ll cnt=0;
      string tmp="";
      while(!vis[x]){
          vis[x]=1;
          tmp+=s[x];
          cnt++;
          x=adj[x];
      }
      ll res=0;
      for(int len=1;len<=cnt;len++){
          string c="";
          for(int j=len,k=1;k<=cnt;k++,j++)c+=tmp[j%cnt];
          if(c==tmp){
              res=len;
              break;
          }
      }
      ans=ans*res/__gcd(ans,res);
  }
  cout<<ans<<"\n";
}

图论

置换环环链拓扑

This post is licensed under CC BY 4.0 by the author.