Codeforces Round #277.5 (Div. 2) Solution Report_html/css_WEB-ITnose

Still only know 4. . sad. . .

A: SwapSort

Use an array to store the sorted data. Then start from the beginning and swap what needs to be swapped with what should be at this position, up to n-1 times.

The code is as follows;

#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

Bipart graph maximum matching naked question.

The code is as follows:

#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...

Greedy water problem.

Fill in order.

The code is as follows:

#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

Enumerate the points and perform BFS to find the distance is 2 point, and then record the number of times it reaches this point. If the number is greater than 2, it means it exists. Solve it based on the number of combinations.

The code is as follows:

#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;}