置换群题目汇总

浅浅的花香味﹌ 2022-08-07 17:36 242阅读 0赞

首先介绍一下什么是置换群，不说一些繁琐的概念。  
首先给你一个序列，假如：  
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序列置换][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;
    }
    还有一道比较牛的题目，用到扩展欧几里得，还没有做出来，后面更新

[nyoj900]: http://acm.nyist.net/JudgeOnline/problem.php?pid=900
[poj3270 Cow Sorting]: http://poj.org/problem?id=3270