题解 信息学奥赛一本通/AcWing 1118 分成互质组 DFS C++
题目
传送门
AcWing
1118. 分成互质组 - AcWing题库https://www.acwing.com/problem/content/1120/https://www.acwing.com/problem/content/1120/https://www.acwing.com/problem/content/1120/https://www.acwing.com/problem/content/1120/
https://www.acwing.com/problem/content/1120/信息学奥赛一本通
信息学奥赛一本通（C++版）在线评测系统https://ybt.ssoier.cn/problem_show.php?pid=1221https://ybt.ssoier.cn/problem_show.php?pid=1221https://ybt.ssoier.cn/problem_show.php?pid=1221https://ybt.ssoier.cn/problem_show.php?pid=1221https://ybt.ssoier.cn/problem_show.php?pid=1221
思路
怎么实现互质判断
互质的两个数，它们的最大公约数 (GCD) 为 1
不懂的话自己搜 "欧几里得算法/辗转相除法/求最大公约数"
模板代码
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }怎么判断一个数能否加入某个分组
有一种做法是分组不存各个数，而是存它们的乘积
如，判断 7 是否能加入 2，3，5，只要判断 7 与 2*3*5 = 30 是否互质
分组里存 2*3*5 = 30 就行了
但是这种做法局限性高，分组内数的乘积比较小才行，不然会爆整型
所以还是老老实实存各个数。判断一个数是否能加入某个分组，要遍历判断互质关系
为什么要搜索，贪心不可以做吗？
贪心还真不行，不妨试试
贪心思路：能入则入：如果一个数能放进已有的分组，就放进去，而不是新建分组
这样的贪心思路确实能过样例数据，但是不能过所有数据，如：n{ 4 }, arr{ 3,7,6,14 }
若 "能入则入"，则 3 >> 分组1，7 >> 分组1，6 >> 分组2，14 >> 分组3，这样要分 3 组
但这不是最优解，最优解是分 2 组：{ 3,14 }, { 7,6 }
通过这个数据我们不难发现，一个数放入一个分组，会影响后续的数放入这个分组
"能入则入" 可能会错过最优解，就像 7 和 3 放在一组，影响了 6 放入这个分组，错过了最优解
所以我们要搜索所有情况，对于当前的数，有如下分支
(1) 进入已有分组 0 (2) 进入已有分组 1 ...... (m) 另起一个分组，每种每支都要尝试枚举
DFS 问题，有思路但是写不出来可以画搜索树
代码
#include <vector>
#include <iostream>
using namespace std;
const int N = 12;
int n, num[N], ans;
vector<int> g[N];
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
bool check(int G, int x) //遍历判断互质
{
for (auto y : g[G])
if (gcd(num[x], y) != 1)
return false;
return true;
}
void DFS(int x, int cnt) //cnt 表示当前分组的数量，cnt-1 表示最后一个分组的下标。如果要新建分组，cnt 表示新建分组的下标
{
if (cnt >= ans) return; //最优性剪枝
if (x == n) { ans = cnt; return; } //最优性剪枝保证了 cnt < ans，可以直接更新而不用 ans = min(ans, cnt)
for (int i = 0; i < cnt; i++)
{
if (check(i, x)) //可行性剪枝
{
g[i].push_back(num[x]); //处理现场
DFS(x + 1, cnt);
g[i].pop_back(); //恢复现场
}
}
g[cnt].push_back(num[x]); //新建分组
DFS(x + 1, cnt + 1); //新建分组
g[cnt].pop_back(); //恢复现场
}
int main()
{
cin >> n;
for (int i = 0; i < n; i++) cin >> num[i];
DFS(0, 0);
cout << ans;
return 0;
}细节
分组用 vector 数组存，比用二维数组存省事儿得多。对自己好点，别没事儿折磨自己......
关于排列式搜索和组合式搜索
排列式搜索考虑顺序，一般通过多层嵌套实现，每层枚举范围为 [1, n]
通过标记数组避免重复选择。比较经典的题目有：递归实现排列型枚举
我以前还写过这个题的题解。。。
递归实现指数型、组合型、排列型枚举，按字典序输出-CSDN博客https://blog.csdn.net/qwq_ovo_pwp/article/details/141332402?spm=1001.2014.3001.5501https://blog.csdn.net/qwq_ovo_pwp/article/details/141332402?spm=1001.2014.3001.5501https://blog.csdn.net/qwq_ovo_pwp/article/details/141332402?spm=1001.2014.3001.5501https://blog.csdn.net/qwq_ovo_pwp/article/details/141332402?spm=1001.2014.3001.5501https://blog.csdn.net/qwq_ovo_pwp/article/details/141332402?spm=1001.2014.3001.5501当时刚学完C语言，初学算法没几天，比较菜
所以文章和代码写得不是很好，这个代码还能精简改善掉许多 (懒得再改了，凑合看吧)
组合式搜索不考虑顺序，一般通过多层嵌套实现，每层枚举范围不大于上层
即上层枚举 [i, n] 时该层枚举 (i, n] (左边可能是闭区间)
有时内层直接枚举外层的下一个，本题就是这样的 (DFS(x+1, ...))
在不考虑顺序时，排列型搜索的效率远低于组合型搜索
会重复搜索很多状态。本题搜索无顺序要求，故采用组合式搜索
就本题来说，这么搜索 (DFS(x+1, ...)) 为何能不重不漏地搜到所有情况
不理解的话画搜索树吧。可以发现对于每个数，每种分组情况都被枚举到了
满足条件时可以分到已有的任何分组或新建分组
任何分组都可能独立出一个分组，枚举到了所有分组都自成一组的情况
满足条件时也可以枚举到所有数都在一个分组的情况
参考文献 (雾)
AcWing 165. 小猫爬山 - AcWinghttps://www.acwing.com/activity/content/code/content/136433/https://www.acwing.com/activity/content/code/content/136433/https://www.acwing.com/activity/content/code/content/136433/https://www.acwing.com/activity/content/code/content/136433/https://www.acwing.com/activity/content/code/content/136433/只是参考了 y总 的注释和部分细节
(变量的初始值、具体含义等。我原先的版本 cnt 具体含义和此版本略有不同，初始值为 -1)
(不得不说这两个题目相似程度没有 100% 也有 10000% 了)
信息学奥赛一本通（1221：分成互质组） - 代码先锋网信息学奥赛一本通（1221：分成互质组），代码先锋网，一个为软件开发程序员提供代码片段和技术文章聚合的网站。https://www.codeleading.com/article/24965750320/https://www.codeleading.com/article/24965750320/https://www.codeleading.com/article/24965750320/https://www.codeleading.com/article/24965750320/https://www.codeleading.com/article/24965750320/"为什么要搜索，贪心不可以做吗？" 灵感来自这篇文章
"这道题没有必要放到dfs中，直接枚举即可" 我一开始也是这么想的
直到看到这篇文章并交了一发。。。。。。