NO IMAGE

首先介紹一下什麼是置換群,不說一些繁瑣的概念。
首先給你一個序列,假如:
s = {1 2 3 4 5 6}
然後給你一個變換規則
t = {6 3 4 2 1 5}
就是每一次按照t規則變換下去
比如這樣
第一次:6 3 4 2 1 5
第二次:5 4 2 3 6 1
第三次:1 2 3 4 5 6
發現經過幾次會變換回去,在變換下去就是迴圈的了,這就是一個置換群。
我們可以這樣表示一個置換群,比如按照上面變化規則
1->6->5->1 那麼這些是一個輪換
2->3->4->2 這些是一個輪換
所以可以寫為
t = { {1 6 5},{ 2 3 4 } },然後就衍生出了一些這樣的題目
1: nyoj900序列置換
就是求置換群的的一個迴圈,那麼很明顯,我們求出置換群中的所有輪換的元素個數,求最小公倍數即可,注意這個題目會超int,坑…
AC程式碼:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 300;
const int inf = 0x3f3f3f3f;
typedef long long LL;
int next[N];
bool ok[N];
LL gcd(LL a,LL b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=1;i<=n;i  )
{
scanf("%d",&next[i]);
}
LL ans = 1;
memset(ok,false,sizeof(ok));
for(int i=1;i<=n;i  )
{
if(ok[i]==false)
{
int tmp = i;
LL cnt = 1;
ok[i] = true;
while(next[tmp]!=i)
{
cnt  ;
tmp = next[tmp];
ok[tmp] = true;
}
LL css = gcd(ans,cnt);
ans = (ans*cnt)/css;
}
}
printf("%lld\n",ans);
}
return 0;
}

2:poj3270 Cow Sorting
題意是給你一個序列s = {a1,a2……an},然後可以任意交換其中兩個元素 i , j 的位置,代價是位ai aj,然後讓你把這個序列變成有序,求最小代價

思路:對置換群的巧妙應用
首先我們求出所有輪換,對於一個輪換,我們用其中最小的元素去交換得到其他的顯然是最優的方案。
例如,數字是8 4 5 3 2 7
明顯,目標狀態是2 3 4 5 7 8,能寫為兩個輪換:(8 2 7)(4 3 5)。
觀察其中一個輪換,要使交換代價最小,應該用迴圈裡面最小的數字2,去與另外的兩個數字,7與8交換。這樣交換的代價是:
sum – min (len – 1) * min
化簡後為:
sum (len – 2) * min
其中,sum為這個迴圈所有數字的和,len為長度,min為這個環裡面最小的數字。
.考慮到另外一種情況,我們可以從別的迴圈裡面調一個數字,進入這個迴圈之中,使交換代價更小。例如初始狀態:1 8 9 7 6
可分解為兩個迴圈:(1)(8 6 9 7),明顯,第二個迴圈為(8 6 9 7),最小的數字為6。我們可以抽調整個數列最小的數字1進入這個迴圈。使第二個迴圈變為:(8 1 9 7)。讓這個1完成任務後,再和6交換,讓6重新回到迴圈之後。這樣做的代價明顯是:
sum min (len 1) * smallest
其中,sum為這個迴圈所有數字的和,len為長度,min為這個環裡面最小的數字,smallest是整個數列最小的數字。
那麼就很明朗了。
AC程式碼:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 10010;
const int inf = 0x3f3f3f3f;
int pss[N];
int a[N];
bool ok[10*N];
int next[10*N];
int main()
{
int n;
while(~scanf("%d",&n))
{
memset(ok,true,sizeof(ok));
int mi = inf,ma = -1;
for(int i=1;i<=n;i  ){
scanf("%d",&pss[i]);
a[i] = pss[i];
mi = min(mi,pss[i]);
ma = max(ma,pss[i]);
ok[ pss[i] ] = false;
}
sort(a 1,a 1 n);
for(int i=1;i<=n;i  )
{
next[ a[i] ] = pss[i];
}
int ans = 0;
for(int i=1;i<=ma;i  )
{
if(ok[next[i] ] == false)
{
int num = i, tmpmi = i;
int cnt = 1,count = i;
ok[num] = true;
while(next[num]!=i)
{
num = next[num];
cnt  ;
count =num;
ok[num] = true;
tmpmi = min(tmpmi,num);
}
ans =min(count (cnt-2)*tmpmi,count tmpmi (cnt 1)*mi);
}
}
printf("%d\n",ans);
}
return 0;
}
還有一道比較牛的題目,用到擴充套件歐幾里得,還沒有做出來,後面更新