本文主要是介绍Codeforces Round #277.5 (Div. 2) 解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
还是只会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 __int64
const 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");elseprintf("-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 __int64
LL 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;
}这篇关于Codeforces Round #277.5 (Div. 2) 解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
