首页 > 代码库 > cf #254 (Div. 2)

cf #254 (Div. 2)

a题

#include<stdio.h>#include<string.h>char c[101][101];int main(){    long n,m,i,j;    scanf("%ld%ld",&n,&m);    gets(c[0]);    for(i=1;i<=n;i++)        gets(c[i]);    for(i=1;i<=n;i++)        {            for(j=0;j<m;j++)                if(c[i][j]==-)                    printf("-");                else                {                    if((i%2)^(j%2))                        printf("W");                    else                        printf("B");                }            printf("\n");        }    return 0;}
View Code

b题 其实就是每个联通快的节点数减1,dfs,并查集都可以。

#include <iostream>#include <stdio.h>#include <math.h>#include <string.h>using namespace std;int p[100];int n, m;int find(int x) {    int s;    for(s = x; p[s] >= 0; s = p[s]);    while(s != x)     {        int tmp = p[x];        p[x] = s;        x = tmp;    }    return s;}int unionSet(int a, int b) {    int t1 = find(a);    int t2 = find(b);    int tmp = p[t1] + p[t2];    if(p[t1] > p[t2])     {        p[t1] = t2;        p[t2] = tmp;    }    else     {        p[t2] = t1;        p[t1] = tmp;    }}int main() {    while(scanf("%d%d", &n, &m) != EOF)     {        int a, b;        for(int i = 0; i <= n; i++)         {            p[i] = -1;        }        for(int i = 0; i < m; i++)         {            scanf("%d%d", &a, &b);            int r1 = find(a);            int r2 = find(b);            if(r1 != r2)             {                unionSet(a, b);            }        }        int mul = 0;        for(int i = 1; i <= n; i++)         {            if(p[i] < 0)             {                mul -= (p[i]+1);            }        }        __int64 ans = pow(2.0, mul);                printf("%I64d\n", ans);    }    return 0;}
View Code

c题 求最小密度子图,这个在当时学最大密度子图的时候想过,其实就是一条边两个点,因为再添加一条边之后的密度要小于这两部分中最大的那个。

#include <stdio.h>int n,m;double vval[550],eval[500000];int main(){    double ans=0;    int i,j,u,v;    scanf("%d%d",&n,&m);    for(i=1;i<=n;i++) scanf("%lf",&vval[i]);    for(i=1;i<=m;i++)    {        scanf("%d%d%lf",&u,&v,&eval[i]);        if((vval[u]+vval[v])/eval[i]>ans)            ans=(vval[u]+vval[v])/eval[i];    }    printf("%.9lf\n",ans);    return 0;}
View Code