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;
- }
来源: http://www.bubuko.com/infodetail-2494793.html