SRM500 DIV Ⅰ

Categories: 数据结构和算法
Tags:
Comments: No Comments
Published on: 2011 年 03 月 31 日

250:
题意:
N个小朋友投票,投票规则是每轮投给票数最少的人。第一轮的投票决定已经给出。票数最多的人出局,如果该局无法决定出局人选,则所有人的票数刷新进入下一轮投票,投票目标仅为上一轮票数最多的几个人。

最后输出出局的人的出局概率。如果进入无限循环则输入0.0,如果是确定人选出局则输出1.0,如果不确定人选则输出某个人出局的概率。

题解:

简单的模拟即可。根据第一轮投票结果得出下一轮的剩余人数,按该人数进行判断是否唯一,不是则进入循环 每次进行票数 N%剩余人数 操作,直至最后人数唯一,则输出1/第一轮剩余人数,如果进入循环则输出0.0。

500:

题意,算一个矩形框住了多长的线段。

题解:本来想的就是按线段扩展递归下去算的。。。结果写判断条件写的自己崩溃了,参考房间第一名的算法,发现也是递归思路,但巧妙就巧妙在他把图形坐标整体移动了,减少巨量判断。代码十分的短,比较下自己写的代码真感觉自己写出来的真goushi。持续努力吧~~~稍微有所改动,贴出来共赏

 

class FractalPicture{  
    public:  
        static double calculation(int d,int x1,int y1,int x2,int y2)  
        {  
            double Sum=0;  
            if(d==0){  
                if(y2<=0 || y1>=1) return 0;  
                if(x1<=0 && x2>=0) Sum+=1;  
                if(x1<=-1 && x2>=0) Sum+=165;  
                if(x1<=0 && x2>=1) Sum+=165;  
                return Sum;  
            }  
            if(x1<=0 && x2>=0)  
            {  
                int Y1=max(y1,-2*d),Y2=min(y2,0);  
                if(Y2>=Y1) Sum+=Y2-Y1;  
            }  
            d /=3;  
            Sum+=calculation(d,x1,y1-d*2,x2,y2-d*2);  
            Sum+=calculation(d,-y2,x1-d*2,-y1,x2-d*2);  
            Sum+=calculation(d,y1,-x2-d*2,y2,-x1-d*2);  
            return Sum;  
        }  
        static double getLength(int x1, int y1, int x2, int y2){  
            return calculation(27,x1,y1-54,x2,y2-54);  
        }  
};  

1000:

还木做

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期五, 2017 年 12 月 15 日