首页 > > 程序设计 > C/C++ >

『ACM C++』HDU杭电OJ | 1416 - Gizilch （DFS -…

2019-02-28 07:50:30来源：博客园阅读 ()

　　从周三课开始总算轻松了点，下午能在宿舍研究点题目啥的打一打，还好，刚开学的课程还算跟得上，刚开学的这些课程也是复习以前学过的知识，下半学期也不敢太划水了，被各种人寄予厚望之后瑟瑟发抖，只能努力前行了~自己好多地方还做得不够好，真的是要提升的方面太多了，加油吧~

今日兴趣新闻：

网易回应裁员：公司确实正在进行结构性优化

链接：https://baijiahao.baidu.com/s?id=1626619207432301200&wfr=spider&for=pc

偶尔反新闻经常看到这些大公司的裁员，谷歌、微软、华为、百度都出现过大幅度的裁员，现在网易也开始了，这会不会加剧了未来毕业职业出口的紧张呢？

------------------------------------------------题目----------------------------------------------------------

Gizilch

Problem Description

The game of gizilch has very simple rules. First 100 grapes are labeled, in nontoxic ink, with the numbers 1 to 100. Then, with a cry of ``GIZILCH!'', the referee fires the grapes up into the air with a giant gizilcher. The two players, who each start with a score of ``1'', race to eat the falling (or, shortly thereafter, fallen) grapes and, at the same time, multiply their scores by the numbers written on the grapes they eat. After a minute, the hungry squirrels are let loose to finish the remaining grapes, and each contestant reports his score, the product of the numbers on the grapes he's eaten. The unofficial winner is the player who announces the highest score.
Inevitably, though, disputes arise, and so the official winner is not determined until the disputes are resolved. The player who claims the lower score is entitled to challenge his opponent's score. The player with the lower score is presumed to have told the truth, because if he were to lie about his score, he would surely come up with a bigger better lie. The challenge is upheld if the player with the higher score has a score that cannot be achieved with grapes not eaten by the challenging player. So, if the challenge is successful, the player claiming the lower score wins.
So, for example, if one player claims 343 points and the other claims 49, then clearly the first player is lying; the only way to score 343 is by eating grapes labeled 7 and 49, and the only way to score 49 is by eating a grape labeled 49. Since each of two scores requires eating the grape labeled 49, the one claiming 343 points is presumed to be lying.
On the other hand, if one player claims 162 points and the other claims 81, it is possible for both to be telling the truth (e.g. one eats grapes 2, 3 and 27, while the other eats grape 81), so the challenge would not be upheld.
Unfortunately, anyone who is willing to referee a game of gizilch is likely to have himself consumed so many grapes (in a liquid form) that he or she could not reasonably be expected to perform the intricate calculations that refereeing requires. Hence the need for you, sober programmer, to provide a software solution.

Input

Pairs of unequal, positive numbers, with each pair on a single line, that are claimed scores from a game of gizilch.

Output

Numbers, one to a line, that are the winning scores, assuming that the player with the lower score always challenges the outcome.

Sample Input

343 49
3599 610
62 36

Sample Output

49 
610 
62

------------------------------------------------题目----------------------------------------------------------

（一）原题大意：

　　　　原意说的是有一到一百个葡萄，有两个人去吃这些葡萄，每个葡萄上面有数字，每个人吃到的葡萄乘积之和就是自己的答案，获得最大的数就是胜利，但有人为了胜利会假报自己的数字，让你去识破他。

　　　　简单来说，就是一个游戏：

　　　　有两个人玩游戏A、B人，A和B都报一个数，其中最大的人是被挑战者，最小的那个人是挑战者，然后两人的数通过因式分解，若挑战者中总存在一种分解，是被挑战者总有的因子，那么说明被挑战者说谎，判挑战者胜利。

　　　　举例：

　　　　A = 343 B = 49 显然A>B，那么A是被挑战者，B是挑战者，正常来说较小的人不说假话，因为如果他要说假话为何不往大的数说呢，好让自己赢。

　　　　所以对A、B进行因式分解，对于B来说，你只能吃49才能得到，所以A不能再使用49了，但是A可以因式分解成49 * 7，所以可以看得出来A说了假话，判B胜利~

（二）题目分析：

　　　　这道题有点小难度对于新手的我来说，查阅了一些解法加之自己的理解，是需要用到递归的DFS深搜方法去实现的。

　　　　首先建立一个数组，用来存储100个葡萄，value为0则说明还没被吃，1说明已经吃过不能再吃了，通过这种方法来判断A、B是否有因子重复。

　　　　然后对挑战者进行因式分解，得到挑战者的因式分解，然后再对被挑战者进行因式分解，如果被挑战者能够顺利的因式分解，那么被挑战者获胜，否则挑战者获胜。

　　　　后面我会简单整理一下深搜笔记~

（三）代码分块：

　　　　第一步：分清挑战者和被挑战者：

        if(a>b)
        {
            attacker = b;
            victim = a;
        }
        else
        {
            attacker = a;
            victim = b;
        }

　　　　第二步：对挑战者进行因式分解：

result_dfs = dfs(attacker);

　　　　这里需要自己定义dfs深搜函数，那么下面开始定义深搜dfs：

　　　　第三步：dfs函数构造：分解因式：

    if(number > 100) size = 100;
    else size = number;
    
    for(i = 2 ; i<= size ; i++)
    {
        if( number %i == 0 && already[i] == 0)
        {
            already[i] = 1;
            if(dfs( number / i ) == 1) return 1;
            already[i] = 0;
        }
    }

　　　　第四步：dfs函数构造：判断挑战者和被挑战者的因式分解情况：

    if(number == 1)
    {
        if(vic_divided == 0)
        {
            vic_divided = 1;
            vic_divide = 1;
            if(dfs(victim) == 1) return 1;
            else{
                vic_divided = 0;
                return 0;
            }
        }
        return 1;
    }

　　　　第五步，根据dfs返回的结果判断胜负：

        if(vic_divided == 1 && result_dfs == 1 || vic_divide == 0)    winner = victim;
        else winner = attacker;

（四） AC代码：

#include<stdio.h>
#include<string.h>

int attacker,victim;
int vic_divided,vic_divide;
int already[101];


int dfs(int number)
{
    int i,size;
    
    if(number == 1)
    {
        if(vic_divided == 0)
        {
            vic_divided = 1;
            vic_divide = 1;
            if(dfs(victim) == 1) return 1;
            else{
                vic_divided = 0;
                return 0;
            }
        }
        return 1;
    }
    
    if(number > 100) size = 100;
    else size = number;
    
    for(i = 2 ; i<= size ; i++)
    {
        if( number %i == 0 && already[i] == 0)
        {
            already[i] = 1;
            if(dfs( number / i ) == 1) return 1;
            already[i] = 0;
        }
    }
    return 0;
}

int main()
{
    int a,b,result_dfs,winner;
    while(scanf("%d %d",&a,&b) != EOF)
    {
        vic_divide = vic_divided = 0;
        memset(already, 0, sizeof(already));
        if(a>b)
        {
            attacker = b;
            victim = a;
        }
        else
        {
            attacker = a;
            victim = b;
        }
        
        result_dfs = dfs(attacker);
        
        if(vic_divided == 1 && result_dfs == 1 || vic_divide == 0)    winner = victim;
        else winner = attacker;
        
        printf("%d\n",winner);
    }
    return 0;
 }