ZOJ 1003 Crashing Balloon(dfs)

于 2011年02月8日 发布在 未分类 跳到评论

ZOJ 1003 Crashing Balloon

踩气球,气球上的分值为1-100间的数,参赛者的初始分数为1,每踩一个气球就把气球的分数乘以自己的分数,得到比分,最后选手会声明自己的比分,但是有的人可能计算错误,所以最后的分数可能不正确,判断一下两个分数是否能产生….

刚接触acm的时候就看到这个题了..当时是什么思路也没有,现在又看还是不会,我总是想着把,所有的分解情况都列出来再进行比较,但是貌似不可行.今天忍不住偷偷看了别人的代码(貌似我已经几个月没有看过别人的代码了),顿时就震精了,为什么我想不到呢? :cry:


#include<iostream>
using namespace std;
int aa,bb;
void dfs(int a,int b,int n)
{
    if(b==1)
    {
        if(a==1) aa=1;

        bb=1;
    }
    if( n > 100 ||  aa==1 && bb==1  )
        return;
    if(b%n==0) dfs(a,b/n,n+1);//除或不除,他就在那里,一直递归....
    if(a%n==0) dfs(a/n,b,n+1);
    dfs(a,b,n+1);
}

int main(void)
{
    int a,b,t;
    while( cin >> a >> b )
    {
        if(a < b)
        {t=a;a=b;b=t;}

        aa=bb=0;
        dfs(a,b,2);
        if(aa==1)
            cout << a;
        else if(bb==1)
            cout << b;
        else
            cout << a;
        cout << endl;
    }
    return 0;
}

本文共有 9条评论 | 沙发:文章评论

  1. ZXY说道:

    忍不住…姐,你需要脑子再灵活点哈~

  2. laoda说道:

    这个代码的确很牛X,不过在你点开无数blog,发现都是同一段代码时,会觉得很悲催……

  3. facebook chips说道:

    i’m generally bouncing across the net almost all of the afternoon thus I usually tend to peruse substantially, which is not generally a beneficial thing as the majority of the internet resources I look at are constructed of pointless rubbish copied from different websites a million times, but I gotta give you props this blog is really half decent and also boasts a bit of genuine information, so cheers for splitting the phenomena of simply replicating other people’s sites :)

  4. moms chips说道:

    Hmm it appears like your blog ate my first comment (it was extremely long) so I guess I’ll just sum it up what I submitted and say, I’m thoroughly enjoying your blog. I as well am an aspiring blog writer but I’m still new to everything. Do you have any helpful hints for rookie blog writers? I’d genuinely appreciate it.

  5. ii说道:

    很好奇一个case:
    input:4 8
    output:8
    这算不算一个bug?
    求教

留下评论!

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)