今天简直大爆发啊。。。

吃了顿烧烤竟然这么管事。

。

。

。。

本弱渣竟然做出来了3道，并且B题是我第一次在CF中用到算法。。（曾经最多也就是贪心。

。

。

）。

题目地址：codeforces#225

A题：

水题。。

不解释。。

5分钟1Y。

代码例如以下：

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include<algorithm>

using namespace std;

int main()

{

    int n, m, i, j;

    char s[200][200];

    scanf("%d%d",&n,&m);

    for(i=0;i<n;i++)

    {

        scanf("%s",s[i]);

    }

    for(i=0;i<n;i++)

    {

        for(j=0;j<m;j++)

        {

            if(s[i][j]=='-')

                {

                    printf("-");

                    continue ;

                }

            if((i+j)%2)

                {

                    printf("B");

                }

                else

                    printf("W");

        }

        printf("\n");

    }

    return 0;

}

B题：

这题第一次在CF中使用算法，刚開始还犹豫了一段时间，由于没见过在B题中就用到算法的，后来还是大胆的用上了。

。

。

并且还是并查集。。这题就是把能够反应的药品用并查集放在一块，这样分成了能够互不反应的几个集合。这种话，最少不能反应的就是每一个集合放进去的第一个，剩下的就是最多能够发生反应的药品数量。把数量求出来。如果是n，再求2^n就可以。

注意要用int64，第一次由于这个错了一次。

。不然就能进前100了。。。

sad。

。

代码例如以下：

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include<algorithm>

using namespace std;

int bin[100];

int find1(int x)

{

    return bin[x]==x?

x:bin[x]=find1(bin[x]);

}

void merge1(int x, int y)

{

    int f1, f2;

    f1=find1(x);

    f2=find1(y);

    if(f1!=f2)

    {

        if(f2>f1)

            bin[f2]=f1;

        else

            bin[f1]=f2;

    }

}

int main()

{

    int n, m, i, j, a[100], x, y, b[100], z, num, nn;

    __int64 s=1;

    scanf("%d%d",&n,&m);

    memset(a,0,sizeof(a));

    memset(b,0,sizeof(b));

    for(i=1;i<=n;i++)

        bin[i]=i;

        num=0;

        nn=0;

    while(m--)

    {

        scanf("%d%d",&x,&y);

        merge1(x,y);

        a[x]++;

        a[y]++;

    }

    for(i=1;i<=n;i++)

    {

        if(a[i])

        {

            z=find1(i);

            b[z]++;

            num++;

        }

    }

    for(i=1;i<=n;i++)

    {

        if(b[i])

        {

            nn++;

        }

    }

    z=num-nn;

    //printf("%d %d\n",num,nn);

    for(i=1;i<=z;i++)

    {

        s*=2;

    }

    printf("%I64d\n",s);

    return 0;

}

C题：

这题还是非常有意思的。。

第一次看完以为是什么最大密度子图。由于近期刷网络流，网络流的最小割能够求最大密度子图，可是还没学。。。。我还百度看了一会儿。

。

。后来想到能够贪心，先把两个点与相连的边值之比的最大值求出来，然后依次向外扩充，这样肯定可行，可是感觉非常麻烦。。并且复杂度有点悬。

。。但还是硬着头皮写了。然后当写完最大的那一边二点的值时。突然发现再往后扩充肯定越来越小。

。。然后自己YY了一下证明。。这样是能够证明的，于是果断提交。1Y~

代码例如以下：

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#include <math.h>

#include <ctype.h>

#include<algorithm>

using namespace std;

int main()

{

    int n, m, i, p[600], u, v, w;

    double max1=0, x;

    scanf("%d%d",&n,&m);

    for(i=1;i<=n;i++)

        scanf("%d",&p[i]);

    while(m--)

    {

        scanf("%d%d%d",&u, &v,&w);

        x=(p[u]+p[v])*1.0/w;

        if(max1<x)

        {

            max1=x;

        }

    }

    printf("%.15lf\n",max1);

    return 0;

}