本文主要是介绍ZOJ 1003 Crashing Balloon 搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：100个气球，气球上标有1-100的号码，每踩一个气球，则自己的得分可以乘以该气球的标号（初始得分为1，每个气球只能踩一次）。
题解：假如a>b，求出a，b所有可能的分解情况（分解为1-100的数的乘积）。然后比对，只要存在一种分解情况，使得a的因子中不含b的因子，a就是可能的。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;#define lint long long
#define MAXN 101
lint a, b;
bool used[MAXN];
int f1[MAXN][MAXN];
int f2[MAXN][MAXN];void dfs(int k, lint mul, int f[][MAXN])
{if(k == 1 || mul == 1){if(mul == 1){f[0][0]++;int cnt = f[0][0];for(int i = 1; i <= 100; i++)if(used[i]) f[cnt][++f[cnt][0]] = i;}return;}if(mul % k == 0){used[k] = true;dfs(k - 1, mul / k, f);}used[k] = false;dfs(k - 1, mul, f);
}bool cmp(int i, int j)
{for(int k = 1; k <= f1[i][0]; k++)for(int t = 1; t <= f2[j][0]; t++)if(f1[i][k] == f2[j][t]) return false;return true;
}bool judge()
{if(f1[0][0] == 0 && f2[0][0] == 0)return true;if(f1[0][0] == 0 && f2[0][0] != 0)return false;if(f1[0][0] != 0 && f2[0][0] == 0)return true;for(int i = 1; i <= f1[0][0]; i++)for(int j = 1; j <= f2[0][0]; j++)if(cmp(i, j)) return true;return false;
}void print()
{printf("f1: %d\n", f1[0][0]);for(int i = 1; i <= f1[0][0]; i++){for(int j = 1; j <= f1[i][0]; j++)printf("%d ", f1[i][j]);printf("\n");}printf("f2: %d\n", f2[0][0]);for(int i = 1; i <= f2[0][0]; i++){for(int j = 1; j <= f2[i][0]; j++)printf("%d ", f2[i][j]);printf("\n");}printf("\n");
}int main()
{while(scanf("%lld %lld", &a, &b) != EOF){if(a < b) swap(a, b);if(a == b || a <= 100) { printf("%lld\n", a); continue; }memset(f1, 0, sizeof(f1));memset(f2, 0, sizeof(f2));memset(used, 0, sizeof(used));dfs(100, a, f1);memset(used, 0, sizeof(used));dfs(100, b, f2);if(judge()) printf("%lld\n", a);else printf("%lld\n", b);//print();}return 0;
}
另一种解法:
#include<cstdio>
#include<algorithm>
using namespace std;bool f1, f2;void dfs(int numa, int numb, int k)
{if(numb == 1){f2 = true;if(numa == 1) f1 = true;/*在numb分解完成的情况下，查看numa是否可以分解。这样可以保证某些公因子被numb用了，便不能再被numa用*/}if(k == 1 || (f1 && f2)) return;if(numa % k == 0) dfs(numa / k, numb, k - 1); //因子k,被a用不被b用if(numb % k == 0) dfs(numa, numb / k, k - 1); //因子k,被b用不被a用dfs(numa, numb, k - 1); //因子k,既不被a用也不被b用
}int main()
{int a, b;while(scanf("%d%d",&a,&b) != EOF){if(a < b) swap(a, b);f1 = f2 = false;dfs(a, b, 100);if(!f1 && f2) printf("%d\n",b);else printf("%d\n",a);}return 0;
}
这篇关于ZOJ 1003 Crashing Balloon 搜索的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
