Codeforces Round #252 (Div. 2)-C,D_html/css_WEB-ITnose

Question C is a simple simulation. First, give each person two. Then just give the rest to one person.

Give in the shape of a snake when giving.

#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<vector>#include<queue>using namespace std;#define LL __int64#define maxn 330000int 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: First, divide each ring into a group according to the rings. Record that at least all exchanges are required to return to the identity arrangement.

1, if all is greater than p. Then we should reduce all.

For a ring, any exchange of two points can divide the ring into two parts, all-1;

For each reduction, we look for the ring with the smallest minimum value, and then Find the minimum value in this ring and then swap the two points.

2, if all is less than p. Then we should increase all.

Then we can exchange node 1 with any node to achieve the purpose of increasing all.

Note that node 1 does not exchange with its own ring. And node 1 only exchanges with any ring once.

#include<stdio.h>#include<string.h>#include<algorithm>#include<iostream>#include<vector>#include<queue>using namespace std;#define LL __int64#define maxn 3300int 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;}