注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

2012NBUT暑期集训热身赛  

2012-06-30 09:34:38|  分类: 比赛 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

 只做出了部分的题目,继续加油~~

 

Problem BBirdlike Angry Pig

题目链接:http://acm.nbut.cn/Problem/view.xhtml?id=1173

      

       一道与运算的题目,就是把输入的数据全部与一遍。但由于可能存在一种不存在鸟猪但是却在与运算中能出来与原来一样的数,比如说有三个编号(7, 63, 63),那么它们一遍的结果是7。但是这不能说明鸟猪的编号就是7,因为63 & 63根本不等于7。也就是说,我们在出结果之后,还需要验算一遍,是不是存在鸟猪

  这题比赛的时候木有考虑到那个特殊的情况,一直WA=  =

       下面是我的代码:

 

 

#include<iostream>

using namespace std;

int main()

{

    int n, id, sum, min;

   

    while (scanf("%d", &n) != EOF)

    {

       min = sum = 2147483647;

        while (n --)

       {

           scanf("%d", &id);

          

           if (min > id)

           {

              sum = sum & min;

              min = id;

           }

           else

              sum = sum & id;

       }

       if(min == sum) printf("%d\n", min);

       else   printf("CAUTION: NO BIRDLIKE\n");

    }

    return 0;

}


Problem EExchange Rate

题目链接:http://acm.nbut.cn/Problem/view.xhtml?id=1176

 

可以看出这是一道利用floyd算法求最短路。求的是一种货币在必须交换一次的前提下损耗的最小值。自身不能交换。所以用三重循环就可以了。

  下面是我的代码:

 

#include<iostream>

using namespace std;

 

double Dis[200][200];

 

void floyd(int n)

{

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

    {  

        for( int j = 0;j < n;j ++)

        {

            if(Dis[j][i] > 0)

            {

                for( int k = 0;k < n;k ++)

                {

                    if( Dis[i][k] > 0)

                    {

                         if ( Dis[i][k] + Dis[j][i] < Dis[j][k] || Dis[j][k] < 0)

                        {

                            Dis[j][k] = Dis[i][k] + Dis[j][i];

 

                         }

                    }

                }

            }      

        }

    }

}

 

int main()

{

    int i, j, k;

    int n, m;

   

    while(scanf("%d", &n)!=EOF)

    {

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

        {

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

            {

                scanf("%lf", &Dis[i][j]);

            }

        }

        floyd(n);

        for(i = 0; i < n; i ++)printf("%.2lf\n", Dis[i][i]);

    }

    return 0;

}


Problem FFarmland

题目链接:http://acm.nbut.cn/Problem/view.xhtml?id=1177

 

本题也是几何题里面赤裸裸的凸包问题。要让依琳种的田最大,其实就是求一个凸包,这样就保证了最大面积。一开始模板找的不好,用测试数据一比较才发现多了几组数据。改了半天

下面是我的代码:

 

 #include<cstring>

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

#define MAXN 100009

#define esp 1e-4

 

struct point

{

    double x,y;

    int idx;

    void input(int i)

    {

       idx=i;

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

    }

}p[MAXN];

 

double dis(struct point a,struct point b)

{

    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

double dir(struct point a,struct point b,struct point p)

{

    //ab叉乘ac

    //ac相对ab为逆时针,则叉乘为正(右手)

    // ac相对ab为顺时针,则叉乘为负(左手)

    struct point p1,p2;

    p1.x=b.x-a.x;  p1.y=b.y-a.y;

    p2.x=p.x-a.x;  p2.y=p.y-a.y;

    return p1.x*p2.y-p2.x*p1.y;

}

int n;

point s[MAXN];

int top;

 

int cmp(struct point a,struct point b) //按照极角排序

{

    double d=dir(p[0],a,b);

    if(d==0)

       return dis(a,p[0])<dis(b,p[0]);

    return d>0;

}

 

void solve()

{

    int i,j,k;

    k=0;

    for(i=1;i<n;i++)//找出最左下角的点

    {

       if(p[i].y<p[k].y)

           k=i;

       else if(p[i].y==p[k].y && p[i].x<p[k].x)

           k=i;

    }

    swap(p[0],p[k]);

    sort(p+1,p+n,cmp);

    s[0]=p[0]; s[1]=p[1]; s[2]=p[2];

    top=2;

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

    {

       //判断s[top]是否在sp[i]的左侧

       //当加上等于0时,点可以在凸包的线上

       while(dir(s[top-1],p[i],s[top])>=0 && top>0)

           top--;

       s[++top]=p[i];

    }

}

int cmp1(point a,point b) {

    return a.idx<b.idx;

}

int main()

{

    //freopen("C:\\Users\\moerben\\Documents\\C-Free\\Temp\\data.in","r",stdin);

    //freopen("C:\\Users\\moerben\\Documents\\C-Free\\Temp\\data1177(3).out","w",stdout);

    while(~scanf("%d",&n))

    {

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

           p[i].input(i);   

       solve();

       sort(s,s+top+1,cmp1);

       for(int i=0;i<=top;i++) {

           if(i) printf(" ");

           printf("%d",s[i].idx);

       }

       puts("");

    }

}

 

 

Problem IIllusionary Kindergarten Examination

题目链接:http://acm.nbut.cn/Problem/view.xhtml?id=1179

这题比较水。题目的意思是数“圈”的个数。像0是一个圈,2没有圈,8是两个圈什么的用枚举就行。

 

#include<iostream>

#include<string>

using namespace std;

int main()

{

    string _num;

 

    while(cin>>_num)

    {

       int count = 0;

       for(int i = 0;i < _num.length();i ++)

       {

           if(_num[i] == '0')

           count++;

           if(_num[i] == '6')

           count ++;

           if(_num[i] == '8')

           count = count + 2;

           if(_num[i] == '9')

           count ++;

       }

       cout<<count<<endl;

    }

}

 



  评论这张
 
阅读(97)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018