- 题解
- 7 年前 @
C++奥赛一本通刷题记录(回溯)
2017.11.13 By gwj1139177410
LETTERS openjudge156
八皇后问题 openjudge1700
八皇后 openjudge1756
红与黑 openjudge1818
棋盘问题 openjudge323
取石子游戏 openjudge6266
马走日 openjudge8465
单词接龙 openjudge8783
分成互质组 openjudge7834
cpp
//数据太水怪我咯?。。思路是每次对于新的一个数,与各组比对是否互质,若没有组能加就添加新组。
#include<iostream>
using namespace std;
const int maxn = 20;
int n, a[maxn], vis[maxn], cmp[maxn], cnt;
int gcd(int a, int b){
return !b?a:gcd(b,a%b);
}
int main(){
cin>>n;
for(int i = 0; i < n; i++)cin>>a[i];
//1. 每次找出未分类的值并将其放入新的类别
for(int i = 0; i < n; i++)if(!vis[i]){
vis[i] = 1; cmp[i]=++cnt;
//2. 找出所有未分类的值中与当前值所在类别全部互质的值并加入该类
for(int j = 0; j < n; j++)if(!vis[j]){
int ok = 1;
for(int k = 0; k < n; k++)if(cmp[k]==cmp[i]){//遍历当前值所在类别的值
if(gcd(a[j],a[k])!=1)ok = 0;
}
if(ok){
vis[j] = 1;
cmp[j] = cnt;
}
}
}
cout<<cnt<<"\n";
return 0;
}
cpp
//f[i][j],选到了第i个数,现在有j个集合
//注:当要把这个数放进来之前前面的数在放进来的时候都已经判断好了
#include<iostream>
using namespace std;
int n, a[20], b[20], ans;
int gcd(int a, int b){
return !b?a:gcd(b,a%b);
}
void dfs(int x, int y){
int flag = 1;
if(x==n){ ans = min(ans,y); return ;}
else for(int i = 1; i <= y; i++){//1.遍历每一个已有类别
int ok = 1;
for(int j = 0; j < n; j++)if(b[j]==i)//2.遍历该类别所有数
if(gcd(a[j],a[x])!=1){ ok=0; break; }
if(ok){//3.如果满足全部互质,就加入该类,并判断下一个数
flag = 0; //如果存在不互质,就不用新建组
b[x] = i;
dfs(x+1,y);
b[x] = 0;
}
}
if(flag){//4.如果没有与当前数互质的类别,就新建一个类别
b[x] = y+1;
dfs(x+1,y+1);
b[x] = 0;
}
}
int main(){
cin>>n;
for(int i = 0; i < n; i++)cin>>a[i];
b[0]=1; ans=0xffffff;
dfs(1,1);
cout<<ans<<"\n";
return 0;
}
放苹果 openjudge666