置换

发表于 | 评论数： | 阅读次数： | 阅读次数：
本文字数： 2.2k | 阅读时长 ≈ 4 分钟

置换

感觉这类的题目就是找循环节，找到循环节就方便计算了，当然循环节应该是暴力寻找吧…………

置换群 poj 1721

题意：

给你一个数组a[]，对数组a进行排序，排序的规则是这样的：第i个位置的数变成a[a[i]]，现在给你一个已经按照这个规则排完s次的数组，问你原数组是什么样的

题解：

这是个置换群，当你进行排序时，你会发现这个是循环的，因此这道题就是找循环节，找到循环节之后就很简单了……

循环节怎么找，当然是暴力找了，每交换一次比较一次，知道找到循环节

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
using namespace std;
#define ll long long
const int N = 1e3 + 5;
int a[N],b[N],c[N];
int n;
void change()
{
	for(int i=1;i<=n;i++){
		b[i]=c[c[i]];
	}
	for(int i=1;i<=n;i++){
		c[i]=b[i];
	}
}

int same()
{
	for(int i=1;i<=n;i++){
		if(a[i]!=b[i]) return 0;
	}
	return 1;
}

int main()
{
	int s;
	cin>>n>>s;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		c[i]=a[i];
	}
	int sum=0;
	while(1){
		sum++;
		change();
		if(same()) break;
	}
	int num=sum-s%sum;
	while(num--){
		change();
	}
	for(int i=1;i<=n;i++) cout<<b[i]<<endl;
	return 0;
}

置换的幂 poj 3128

一个置换平方了之后长度为奇数的循环节长度不变，长度为偶数的循环节变成长度相等的两个
所以判断平方之后的长度为偶数的循环节个数是否为偶数就行了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <cstring>
#include <string>
#include <queue>
using namespace std;
#define ll long long
const int N = 30;
int a[N];
int b[N];
int ans[N];
int vis[N];

void init(int n)
{
	queue<int>q;
	while(!q.empty()) q.pop();
	for(int i=1;i<=n;i++) b[i]=i;
	for(int i=1;i<=n;i++) ans[i]=0;
	for(int i=1;i<=n;i++) vis[i]=0;
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		int sum=0;
		while(1){
			b[i]=a[b[i]];
			q.push(b[i]);
			sum++;
			if(b[i]==i) break;
		}
		while(!q.empty()){
			vis[q.front()]=1;
			q.pop();
		}
		ans[sum]++;
	}
}

int main()
{
	int t;
	cin>>t;
	string s;
	while(t--){
		cin>>s;
		int size=s.size();
		for(int i=0;i<size;i++){
			a[i+1]=s[i]-'A'+1;
		}
		init(s.size());
		int flag=1;
		for(int i=1;i<=size;i++){
			if(i%2) continue;
			if(ans[i]%2){
				flag=0;
				break;
			}
		}
		if(flag) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}