c++&oi

SDOI-07-DAY2

昨天晚上做了一下,结果真的被虐爆了,考完之后毫无感觉,直接睡觉。。。
第一题超恶心,不仅要输出结果还要输出方案,打了半个小时草稿,
连计算方案的算法也没搞出来,只以为是搜索了,但因为后面两天没时间写了。。。
最后手算1~16输出,10分。。。
第二题:二进制的高精度Stein算法,一开始以为数字只会变小,就按照读入顺序存的
结果挂掉。。重写,因各种原因挂掉。。50
第三题,并查集,做过的,AC。
结果160,勉强第四。
如果第三题没有做过,就要100-,10+了。。。
PS:神奇地发现总分上升到第二。。。几个只会做水题的同学悲剧了。可以见得,多试对于选拔选手是有一定好处的。

好吧,总结一下。
首先是考试策略问题。
第一题的确是搜索,裸的ID-DFS就可以AC(写了不超过10分钟。。),完全不需要数学方法。。。
当然我看到了一个比我的程序10多倍的搜索程序,正在研究中。
 
裸的ID-DFS


快我10的代码(pas)

第二题,一者是算法不全面(有可能就是错的),使代码过长。
            二者比较函数,写错了。。。
stein算法核心代码:
        int t=equal(a,b);
        if(t==2){gcd(b,a);return;}
        else if(t==0){copy(ans,b);return;}
        if(b[0]==1&&b[1]==1){copy(ans,b);return;}
        if((b[0]==1||b[0]==0)&&b[1]==0){copy(ans,a);return;}
        //
        if(!(b[1]&1)&&!(a[1]&1)){div2(a),div2(b),gcd(a,b),tim2(ans);return;}
        if((b[1]&1)&&(a[1]&1)){sub(a,b),gcd(a,b);return;}
         //这一类有两种方法gcd(a,b)=gcd((a+b)/2,(a-b)/2)  或 gcd(a,b)=gcd(a-b,b)实现起来差距巨大
        if(!(b[1]&1)&&(a[1]&1)){div2(b),gcd(a,b);return;}
        if((b[1]&1)&&!(a[1]&1)){div2(a),gcd(a,b);return;}
完整代码

第三题,并查集,运用拆点法,把它拆成,本身的集合和相对的集合两个部分。然后很水的。。
第二题不会fin的读入,所以用freopen,这个复制过来的。。。

posted on 2012-04-08 18:00 zyn.cpp 阅读(197) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2012年4月>
25262728293031
1234567
891011121314
15161718192021
22232425262728
293012345

导航

统计

常用链接

留言簿

随笔档案(57)

文章档案(13)

搜索

最新评论

阅读排行榜

评论排行榜