首页 > 其他 > 详细

codeforces#254DIV2解题报告

时间:2014-07-08 16:21:57      阅读:281      评论:0      收藏:0      [点我收藏+]

今天简直大爆发啊。。。吃了顿烧烤居然这么管事。。。。。本弱渣居然做出来了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;
}



codeforces#254DIV2解题报告,布布扣,bubuko.com

codeforces#254DIV2解题报告

原文:http://blog.csdn.net/scf0920/article/details/37399505

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!