首页 > 代码库 > USTC OJ — 1013 Gizilch（搜索，中等题）
USTC OJ — 1013 Gizilch（搜索，中等题）
1. 题目描述
本题是一道有趣的游戏题，题目背景的描述很是啰嗦，略去不谈。
具体的游戏规则可描述如下：
两个人A和B，A报一个正整数a，B报一个正整数b。其中较大的那个人的游戏角色是擂主，较小的那个人的游戏角色是挑战者。比如：
a = 342, b = 49，显然a > b，那么A就是擂主，B就是挑战者。
那么挑战获胜／失败的规则是什么呢？
我们知道对于任意正整数n，我们都可以把它因子分解，并且可能存在很多中分解形式。比如：
n = 20时，就可以对其因子分解为如下几种形式：
n = 20 * 1 = 10 * 2 = 5 * 4 = 5 * 2 * 2
这里的挑战规则就是：
挑战成功：如果擂主的所有分解形式中，挑战者都存在一种分解，两个分解中存在相同的因子。
挑战失败：如果对于挑战者的所有分解，擂主存在一种分解，该分解中的所有因子都不存在于挑战者的分解中。
2. 算法设计
枚举挑战者的所有因子分解，对每一个分解，枚举擂主的因子分解。
我们用一个标记数组f 来记录某一个因子i 是否已经存在于挑战者的因子分解中，如果存在，f[i] = 1，否则f[i] = 0.
对于f[i] = 1的因子i，我们不可以使用它来分解擂主。
这样依次下去，直到找到一个case：擂主的因子分解顺利完成，那么我们就可以确定擂主获胜，挑战失败。
如果直到枚举完成，也没有找到这样一个case，我们就说擂主落败，挑战成功。
枚举的过程采用深度优先搜索遍历。
（注意： 每一个因子只可以出现一次，也就是说因子分解不可以分解成如:20 = 5 * 2 * 2 的形式）
3. AC Code
1 #include <stdio.h> 2 #include <string.h> 3 #define N 105 4 #define MIN(a, b) ((a>b)?b:a) 5 #define MAX(a, b) ((a>b)?a:b) 6 7 int h, l; 8 int f[N]; 9 int is_h_can_be_divided, is_h_divided;10 11 int dfs(int n);12 13 int main()14 {15 int a, b;16 int dfs_ret;17 int winner;18 19 // freopen("in.txt", "r", stdin);20 while ( EOF != scanf("%d%d", &a, &b) )21 {22 23 l = MIN(a, b);24 h = MAX(a, b); 25 26 // f[i] = 0, 初始时，所有1～n都没有被占用27 memset(f, 0, sizeof(f));28 is_h_divided = 0;29 is_h_can_be_divided = 0;30 31 dfs_ret = dfs(l);32 33 // 如果h不能按规则分解，h胜利34 if ( 0 == is_h_can_be_divided )35 winner = h;36 // 如果h能按规则分解，但37 else if ( 1 == is_h_can_be_divided & 1 == dfs_ret )38 winner = h;39 else40 winner = l;41 printf("%d\n", winner);42 43 }44 return 0;45 }46 47 int dfs(int n)48 {49 int n_size;50 int i;51 52 // n == 1时，标识该数分解结束53 if ( 1 == n )54 {55 // is_h_divided 作为h的分解结束标记56 if ( 0 == is_h_divided )57 {58 is_h_can_be_divided = 1;59 is_h_divided = 1;60 if ( dfs(h) )61 return 1;62 else // h没有分解完，并且无法继续分解63 {64 is_h_divided = 0;65 return 0;66 }67 }68 return 1;69 }70 71 // 分解n的过程72 n_size = 100 < n ? 100 : n;73 for ( i = 2; i <= n_size; ++i )74 {75 // n % i == 0 <=> i是n的因子76 // f[i] == 0 <=> i还没有被占用，即保证不会出现20 = 2 * 2 * 5 (i=2)77 if ( 0 == n % i && 0 == f[i] )78 {79 f[i] = 1;80 if ( dfs(n/i) ) return 1;81 f[i] = 0;82 }83 }84 return 0;85 }
USTC OJ — 1013 Gizilch（搜索，中等题）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。