还是只会4道。。sad。。。
A：SwapSort
用一个数组存储排好序之后。然后从头开始依次将需要交换的与本来应该在这个位置的交换，最多交换n-1次。
代码如下；
立即学习“前端免费学习笔记（深入）”；
#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;int a[4000], b[4000], c[4000], d[4000];int main(){ int i, j, n, pos, cnt; while(scanf("%d",&n)!=EOF) { cnt=0; for(i=0;i<n;i++) { scanf("%d",&a[i]); b[i]=a[i]; } sort(b,b+n); for(i=0;i<n;i++) { if(a[i]!=b[i]) { for(j=i+1;j<n;j++) { if(a[j]==b[i]) { pos=j; break; } } swap(a[i],a[pos]); c[cnt]=i;d[cnt++]=pos; } } printf("%d\n",cnt); for(i=0;i<cnt;i++) { printf("%d %d\n",c[i],d[i]); } } return 0;}B： BerSU Ball
立即学习“前端免费学习笔记（深入）”；
二分图最大匹配裸题。
代码如下：
立即学习“前端免费学习笔记（深入）”；
#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;int link[200], vis[200], n, m, a[200], b[200];int head[200], cnt;struct node{ int u, v, next;}edge[100000];void add(int u, int v){ edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++;}int dfs(int u){ int i; for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(!vis[v]) { vis[v]=1; if(link[v]==-1||dfs(link[v])) { link[v]=u; return 1; } } } return 0;}void hungary(){ int i, ans=0; memset(link,-1,sizeof(link)); for(i=0;i<n;i++) { memset(vis,0,sizeof(vis)); if(dfs(i)) ans++; } printf("%d\n",ans);}int main(){ int i, j; while(scanf("%d",&n)!=EOF) { for(i=0;i<n;i++) { scanf("%d",&a[i]); } scanf("%d",&m); for(i=0;i<m;i++) { scanf("%d",&b[i]); } memset(head,-1,sizeof(head)); cnt=0; for(i=0;i<n;i++) { for(j=0;j<m;j++) { if(abs(a[i]-b[j])<=1) { add(i,j); } } } hungary(); } return 0;}C： Given Length and Sum of Digits...
立即学习“前端免费学习笔记（深入）”；
贪心水题。
按照顺序依次填充。
代码如下：
立即学习“前端免费学习笔记（深入）”；
#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64const int INF=0x3f3f3f3f;int a[1000], b[1000];int main(){ int m, s, i, j, x; while(scanf("%d%d",&m,&s)!=EOF) { if(m*9<s) { printf("-1 -1\n"); continue ; } if(s==0) { if(m==1) printf("0 0\n"); else printf("-1 -1\n"); continue ; } x=s-1; for(i=m; i>=2; i--) { if(x>=9) { a[i]=9; x-=9; } else if(x>=0&&x<9) { a[i]=x; x=0; } } a[1]=x+1; x=s; for(i=1;i<=m;i++) { if(x>=9) { b[i]=9; x-=9; } else if(x>=0&&x<9) { b[i]=x; x=0; } } for(i=1;i<=m;i++) { printf("%d",a[i]); } printf(" "); for(i=1;i<=m;i++) { printf("%d",b[i]); } puts(""); } return 0;}D： Unbearable Controversy of Being
立即学习“前端免费学习笔记（深入）”；
枚举起点，分别进行BFS找到距离为2的点，然后记录到达这个点的次数，若次数大于2，说明存在，根据组合数来求解。
代码如下：
立即学习“前端免费学习笔记（深入）”；
#include <iostream>#include <cstdio>#include <string>#include <cstring>#include <stdlib.h>#include <math.h>#include <ctype.h>#include <queue>#include <map>#include <set>#include <algorithm>using namespace std;#define LL __int64LL vis[4000], ans;int head[4000], cnt, n;struct node{ int u, v, next;}edge[50000];void add(int u,int v){ edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++;}void bfs(int x){ int i; queue<int>q; for(i=head[x];i!=-1;i=edge[i].next) { q.push(edge[i].v); } while(!q.empty()) { int u=q.front(); q.pop(); for(i=head[u];i!=-1;i=edge[i].next) { int v=edge[i].v; if(v!=x) vis[v]++; } } for(i=1;i<=n;i++) { if(vis[i]>=2) ans+=vis[i]*(vis[i]-1)/2; }}int main(){ int m, i, j, u, v; scanf("%d%d",&n,&m); ans=0; memset(head,-1,sizeof(head)); cnt=0; while(m--) { scanf("%d%d",&u,&v); add(u,v); } for(i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); bfs(i); } printf("%I64d\n",ans); return 0;}立即学习“前端免费学习笔记（深入）”；
