CF(441D Valera and Swaps)置换群

题意：1-n的一个排列 p1, p2, ..., pn，f(p)的定义是此排列要交换最少的数对能够回到原排列1,2,3,4...n。给一个排列p。要将其变换成f值为m的排列，问至少要交换几个数对，并输出字典序最小的那组答案。

解法：处理出全部的置换群，求出环数k，此时f值为n-k。然后推断n-k和m的大小，分为两种操作

1、加环，这个是在随意元素个数大于1的环内交换随意两个数都能够做到加环

2、减环，交换随意两个环的随意两个元素。就能够做到将两个环连接起来

题目要求是输出字典序最小，那么就暴力搞。

代码：

/******************************************************

* author:xiefubao

*******************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <iostream>

#include <cstring>

#include <cstdlib>

#include <cstdio>

#include <queue>

#include <vector>

#include <algorithm>

#include <cmath>

#include <map>

#include <set>

#include <stack>

#include <string.h>

//freopen ("in.txt" , "r" , stdin);

using namespace std;

#define eps 1e-8

#define zero(_) (abs(_)<=eps)

const double pi=acos(-1.0);

typedef long long LL;

const int Max=3010;

const int INF=1000000007;

vector<int> vec[Max];

int all=0;

int num[Max];

bool rem[Max];

int m;

int n;

int yinggai;

void make(int t)

{

    if(rem[t])

        return ;

    rem[t]=1;

    vec[all].push_back(t);

    make(num[t]);

}

struct point

{

    int p1,p2;

} points[Max];

bool operator<(point a,point b)

{

    if(a.p1!=b.p1)

        return a.p1<b.p1;

    return a.p2<b.p2;

}

void solve()

{

    all=0;

    memset(rem,0,sizeof rem);

    vec[0].clear();

    for(int i=1; i<=n; i++)

    {

        if(!rem[i])

            make(i),all++,vec[all].clear();

    }

    for(int i=0; i<all; i++)

        sort(vec[i].begin(),vec[i].end());

}

int main()

{

    scanf("%d",&n);

    for(int i=1; i<=n; i++)

        scanf("%d",num+i);

    solve();

    yinggai=n-all;

    //cout<<"  "<<yinggai<<endl;

    scanf("%d",&m);

    cout<<abs(yinggai-m)<<endl;

    if(m>yinggai)

    {

        vector<int> help;

        for(int i=0; i<all; i++)

        {

            if(vec[i][0]!=1)

                help.push_back(vec[i][0]);

        }

        sort(help.begin(),help.end());

        bool b=1;

        printf("1 %d",help[0]);

        for(int i=1; i<m-yinggai; i++)

            printf(" 1 %d",help[i]);

        cout<<endl;

    }

    else  if(m<yinggai)

    {

        int t=yinggai-m;

             //cout<<"fdas";

       for(int i=0;i<t;i++)

       {

           solve();

           pair<int,int > p(Max,Max);

           for(int i=0;i<all;i++)

           {

             if(vec[i].size()>1&&vec[i][0]<p.first)

             {

                 p.first=vec[i][0];

                 p.second=vec[i][1];

             }

           }

           swap(num[p.first],num[p.second]);

           if(i==0)

           printf("%d %d",p.first,p.second);

           else

           printf(" %d %d",p.first,p.second);

       }

    }

    return 0;

}