Codeforces ラウンド #277.5 (ディビジョン 2) ソリューション Report_html/css_WEB-ITnose

まだ4つの料理しか知りません。 。悲しい。 。 。

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: 指定された長さと桁の合計...

欲張りな質問。

順番に記入してください。

コードは次のとおりです:

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