ZOJ 1003 Crashing Balloon(dfs)

ZOJ 1003 Crashing Balloon

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

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


#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;
}

关于 “ZOJ 1003 Crashing Balloon(dfs)” 的 9 个意见

  1. 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 🙂

  2. 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.

发表回复

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