题解：CF1327D Infinite Path

这类有类似置换操作的题，第一反应应该是直接建图。后面默认是从

p_i

到

i

连边建图。

现在我以样例2为例举个例子。

下图分别是是

p^1

，

p^2

，

p^3

中的一个环。

发现规律了吗？对于图

p^k

的某个环来说，其每条边都相当于是图

p^1

向前走了

k

步。设此环在

p^1

中的长为

m

，

m

和

k

最大公约数为

d

，则环上模

d

同余的点在

p^k

上一定在同一个环上。

那么思路就非常简单了。先找环，然后枚举最大公约数

d

，找出这个环上所有新环是否颜色相同，更新答案。

Code

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
int n,p[N],c[N];
bool v[N];
int cnt;
vector<int>circle[N];
int ans,m,a[N];
void dfs(int x){//找环
	if(v[x])return ;
	v[x]=1;
	circle[cnt].push_back(c[x]);
	dfs(p[x]);//因为其实(i,pi)连边建图和(pi,i)连边建图等价，所以这么写较为简便
}
int num[N];
void work(){
	for(int d=1;d<=m;d++){
		if(m%d!=0)continue;
		for(int i=0;i<d;i++)num[i]=0;
		for(int i=1;i<=m;i++){
			int x=i%d;
			if(num[x]==0)num[x]=a[i];
			else if(num[x]!=a[i])num[x]=-1;
		}
		bool p=0;
		for(int i=0;i<d;i++){
			if(num[i]!=-1){p=1;break;}
		}
		if(p){
			ans=min(ans,d);
			return ;
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int T;cin>>T;
	while(T--){
		cin>>n;
		for(int i=1;i<=n;i++)cin>>p[i];
		for(int i=1;i<=n;i++)cin>>c[i];
		ans=1145141919810ll;
		for(int i=1;i<=n;i++)v[i]=0;
		cnt=0;
		for(int i=1;i<=n;i++){
			if(!v[i]){
				cnt++;circle[cnt].clear();
				dfs(i);
			}
		}
		for(int i=1;i<=cnt;i++){
			m=circle[i].size();
			ans=min(ans,m);
			for(int j=1;j<=m;j++)a[j]=circle[i][j-1];
			work();
		}
		cout<<ans<<"\n";
	}
	return 0;
}

题解：CF1327D Infinite Path

文章操作

Code

相关推荐

评论

题解：CF1327D Infinite Path