C题就是一个简单的模拟。首先给每一个人两个。然后把剩下的都给一个人就好了。

给的时候蛇形给。

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<iostream>

#include<vector>

#include<queue>

using namespace std;

#define LL __int64

#define maxn 330000

int main()

{

    int n,m,k;

    while(~scanf("%d%d%d",&n,&m,&k))

    {

        int leap=1;

        int stx=1;

        int sty=1;

        int ms=n*m-(k*2)+2;

        printf("%d",ms);

        while(ms--)

        {

            printf(" %d %d",stx,sty);

            sty+=leap;

            if(sty<1||sty>m)

            {

                if(sty<1)sty=1;

                if(sty>m)sty=m;

                stx++;leap=-leap;

            }

        }

        cout<<endl;

        k--;

        while(k--)

        {

            printf("%d ",2);

            printf("%d %d ",stx,sty);

            sty+=leap;

            if(sty<1||sty>m)

            {

                if(sty<1)sty=1;

                if(sty>m)sty=m;

                stx++;leap=-leap;

            }

            printf("%d %d\n",stx,sty);

            sty+=leap;

            if(sty<1||sty>m)

            {

                if(sty<1)sty=1;

                if(sty>m)sty=m;

                stx++;leap=-leap;

            }

        }

    }

    return 0;

}

D：首先依据环。把每个环分成一组。记录下此时至少须要交换all次，才干回归到恒等排列。

1。假设all大于p。

那么我们就应该把all降低。

对于一个环。随意两个点交换都能够把环分成两份。all-1；

对于每次降低，我们寻找环的最小值最小的环，然后在这个环中寻找最小值，然后交换这两个点。

2，假设all小于p。那么我们应该把all增大。

那么我们就能够把1号节点和随意节点交换。来达到增大all的目的。

注意，1号节点不和本身的环交换。

而且1号节点和随意一个环仅仅交换一次。

#include<stdio.h>

#include<string.h>

#include<algorithm>

#include<iostream>

#include<vector>

#include<queue>

using namespace std;

#define LL __int64

#define maxn 3300

int a[maxn];

int b[maxn];

int vis[maxn];

vector<int>vec;

vector< vector<int> >ans;

struct list

{

    int x,y;

} node;

vector<list>pr;

bool cmp(vector<int>a,vector<int>b)

{

    return a[0]<b[0];

}

struct listt

{

    int x;

    int index;

    int l,r;

    friend bool operator <(const listt &a,const listt &b)

    {

        return a.x>b.x;

    }

}tt;

priority_queue<listt>que;

int main()

{

    int n,m;

    while(~scanf("%d",&n))

    {

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

        {

            scanf("%d",&a[i]);

            b[i]=a[i];

        }

        scanf("%d",&m);

        memset(vis,0,sizeof(vis));

        vec.clear();

        ans.clear();

        int all=0;

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

        {

            if(vis[i])continue;

            int j=i;

            vec.clear();

            while(b[j]!=j&&vis[j]==0)

            {

                vec.push_back(j);

                vis[j]=1;

                j=b[j];

            }

            if(vec.size())

            {

               // sort(vec.begin(),vec.end());

                ans.push_back(vec);

                all+=vec.size()-1;

            }

        }

        sort(ans.begin(),ans.end(),cmp);

        pr.clear();

        if(all<=m)

        {

            all=m-all;

            if(ans.size()==0)

            {

                node.x=1;

                for(int i=2; i<=all+1; i++)

                {

                    node.y=i;

                    pr.push_back(node);

                }

            }

            else

            {

                node.x=1;

                int j=0;

                if(ans[0][0]==1)j++;

                for(int i=2; i<=n&&all>0; i++)

                {

                    if(b[i]==i)

                    {

                        all--;

                        node.y=i;

                        pr.push_back(node);

                    }

                    if(ans.size()>j&&ans[j][0]==i)

                    {

                        all--;

                        node.y=i;

                        j++;

                        pr.push_back(node);

                    }

                }

            }

        }

        else

        {

            int qian=all;

            all=all-m;

            int i=0;

            while(!que.empty())que.pop();

            for(i=0;i<ans.size();i++)

            {

                tt.index=i;

                tt.x=ans[i][0];

                que.push(tt);

            }

            while(all)

            {

                tt=que.top();

                que.pop();

                i=tt.index;

                node.x=ans[i][0];

                int minn=9999;

                int st=0;

                for(int j=1;j<ans[i].size()&&all>0;j++)

                {

                    if(minn>ans[i][j])

                    {

                        minn=ans[i][j];

                        st=j;

                    }

                }

                node.y=minn;

                all--;

                pr.push_back(node);

                vec.clear();

                minn=9999;

                vec.push_back(ans[i][st]);

                for(int j=1;j<st;j++)

                {

                    vec.push_back(ans[i][j]);

                }

                if(vec.size()>1)

                {

                    ans.push_back(vec);

                    tt.index=ans.size()-1;

                    tt.x=vec[0];

                    que.push(tt);

                }

                vec.clear();

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

                for(int j=st+1;j<ans[i].size();j++)

                {

                    vec.push_back(ans[i][j]);

                }

                if(vec.size()>1)

                {

                    ans[i]=vec;

                    tt.index=i;

                    tt.x=vec[0];

                    que.push(tt);

                }

                i++;

            }

        }

        cout<<pr.size()<<endl;

        for(int i=0; i<pr.size(); i++)

        {

            printf("%d %d\n",pr[i].x,pr[i].y);

        }

    }

    return 0;

}