题意
将给定数组a分割成若干个互质子集的最小子集数量。每个子集内的任意两个元素都互质。
疑惑
我根据AcWing 1118. 分成互质组 - AcWing题解的思路2写的代码如下，但是代码有错。
把第35行 g[--zushu].pop_back();注释掉之后会出现terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc这段错误提示，
用样例
4
3 7 6 14
debug后组数zushu会一直+1，直到数组越界。
我非常不理解为什么会一直递归下去zushu+1，也不理解为什么7与3互质但是反而用7新开一组答案更好，而按照思路1却根本不用新开一组。
nnd，那就只能按照dfs要枚举所有情况或者背下来强行解释了。。。
namo，不是很理解为什么错了，先这样放这里吧
还有一个其他人的题解1118. 分成互质组 - AcWing题库
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cerr << #x << " = " << x << "\n";
int n;
const int N = 15;
int a[N];
bool used[N];
vector<int> g[N];
//
bool check(int zushu,int num){
for(int i=0;i<g[zushu].size();i++){
if(__gcd(g[zushu][i],num)!=1) return false;
}
return true;
}
int ans = N;
int zushu=0;
void dfs(int u){
if(u==n){
ans = min(ans,zushu);
return;
}
bool flag = true;
for(int i=0;i<zushu;i++){
if(check(i,a[u])){
g[i].push_back(a[u]);
dfs(u+1);
flag = false;
g[i].pop_back();
}
}
if(flag){
g[zushu++].push_back(a[u]);
dfs(u+1);
g[--zushu].pop_back();
}
}
int main(){
cin>>n;
for(int i=0;i<n;i++){
cin>>a[i];
}
dfs(0);
cout << ans << "\n";
return 0;
}
思路1：
枚举每一组可以放哪些元素。
#include<iostream>
#include<cstring>
using namespace std;
const int N = 10;
int n;
int a[N];//n个整数
int ans = N;//由于是求最小值，这里初始化为最大值
int g[N][N];//分组
int st[N];
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
bool check(int g[],int x,int start){
for(int i=0;i<start;i++){
if(gcd(g[i],x)>1) return false;
}
return true;
}
//当前要放在哪个分组；要放在该分组的第几个位置；从哪个位置开始选择元素【组合套路(定一个遍历顺序)】；当前已分组完毕的元素个数
void dfs(int gr,int gc,int start,int cnt){
if(gr>=ans) return;//剪枝 + 防止死循环
if(cnt==n) ans=gr;
bool flag=true;//从start开始找，是否有元素不能放到gr组中
for(int i=start;i<n;i++){
if(!st[i]&&check(g[gr],a[i],gc)){
st[i]=true;
g[gr][gc]=a[i];
dfs(gr,gc+1,i+1,cnt+1);
st[i]=false;
flag=false;
}
}
//新开一个分组
//由于dfs每层之间确定了顺序，所以期间是会有元素被漏掉的，【比如一开始你找的一串序列(1)是1,2,3,4 但是第二次(2)是1,3,4 很显然此时
//(2)还有一个3没有得到分组，需要从start=0开始再把它找出来！ 因此这样做仿佛有点浪费时间呢！！】
//因此当所有元素都不能放进当前分组的时候 或者 当start=n-1了但是元素没有全部分组完毕时，要重新从start=0开始找，并且一定要有st数组！！！不然会把一个元素重复的分组！
if(flag) dfs(gr+1,0,0,cnt);
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
//为什么一开始gr从1开始但是分组只开了10个呢？
//首先这样的话可以直接通过gr就得到当前分了多少组；其次由于ans初始化即为10，因此当打算开第10个分组时，会被弹回，数组不会越界
dfs(1,0,0,0);
cout<<ans;
return 0;
}
思路2：
枚举每个元素可以放在哪一组
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
const int N=10;
int a[N];
vector<int> g[N];
int n;
int ans=10;
int len=0;
int gcd(int a,int b){
return b?gcd(b,a%b):a;
}
bool check(int c,int x){
for(int i=0;i<g[c].size();i++){
if(gcd(g[c][i],x)>1) return false;
}
return true;
}
void dfs(int u){
if(u==n){
ans=min(ans,len);
return;
}
//每个元素的方法即——放到当前已经存在的组中 或者 放到新开的组中
for(int i=0;i<len;i++){
if(check(i,a[u])){
g[i].push_back(a[u]);
dfs(u+1);
g[i].pop_back();
}
}
//可见这里的len代表着的是当前开辟数组的个数
g[len++].push_back(a[u]);
dfs(u+1);
g[--len].pop_back();
}
int main(){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
dfs(0);
cout<<ans;
return 0;
}
对于以上的两种搜索的顺序其实可以想象一下这样的一种情景。即你有n个篮子你要用它们去装水果，每个篮子只能装对应种类的水果。
那么第一种方法就相当于是，你把水果任意的排成一排，然后拿着一个篮子从第一个水果开始一个个的往后看，看看能能放到你的这个篮子中。
对于第二种方法相当于是，你把篮子放一排，你拿着水果，然后一个个的往下看，看看能不能放在篮子里。