ZJU-1003 Crashing Balloon dfs，

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3

题意（难以描述）：A，B两个人从1~100选数乘起来比谁的大（不能选重复的或者对方选的）。数小的人如果发现数大的人在撒谎，则他可以获胜。（当然都没撒谎大数赢，都撒谎了也是大数赢233）而他判断大数撒谎的方法就是找到自己选的一个数，是构成大数所必须的。/*给你两个数，由1~100选取不重复的数乘起来得到的。如果小的那个数包含了某个大数必须包含的因子，则*/

题解：从1到100枚举构成AB的方法，然后按这个逻辑判断：（A>B)

if能构成B {

　　　　if能构成A：cout<<A;

　　　　else cout<<B;

　　　　　　}

　　else cout<<B;

练搜索题时看到的一段超简单代码。

判断超简单：

将三个cout用两个flag来简化：具体实现如下。

搜索超简单：

从100 到 1 不断除 A或除 B 能除进就按除掉的数继续dfs；

dfs结构很漂亮：结尾用dfs代替了循环，开头判断即使结束递归。

ac代码

#include<cstdio>

#include<algorithm>

#include<iostream>

using namespace std;

int fa, fb;

void dfs(int a, int b, int k) {

    if (b == ) {

        fb = ;

        if (a == )

            fa = ;

    }

    if (k ==  || (fa&&fb))return;

    if (a%k == )dfs(a / k, b, k - );

    if (b%k == )dfs(a, b/k, k - );

    dfs(a, b, k - );

}

int main() {

    int a, b;

    while (cin >> a >> b) {

        if (a < b)swap(a, b);

        fa = fb = ;

        dfs(a, b, );

        if (fa ==  && fb == ) cout << b << endl;

        else cout << a << endl;

    }

}

巴特西

ZJU-1003 Crashing Balloon dfs，

最新文章

热门文章