题目链接:宝可梦中心大对决
已知共有 n 只皮卡丘,给出每只皮卡丘后背的数字,请你选择尽量多的皮卡丘上场,使得它们后背的数满足任意两个数字互质。只需输出你最多能选择了多少只皮卡丘。
估算一下复杂度,二进制枚举+直接判断就可过.当然也可以使用递归+预处理两个数是否互质,这样更快.
code:
暴力法:
#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;
int gcd(int a, int b) {
if (!b) return a;
return gcd(b, a % b);
}
int a[20];
int t[20];
int main() {
// clock_t start,end;
// start=clock();
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i];
}
int ans = 0;
for (int i = 0; i < pow(2, n); ++i) {
int j = i;
int p = 0, k = 0;
while (j) {
if (j & 1) t[p++] = a[k];
k++;
j >>= 1;
}
int flag=1;
for (int q = 0; q < p; ++q) {
for (int m = q+1; m < p; ++m) {
if (gcd(t[q], t[m]) != 1) {
flag=0;
break;
}
}
if(!flag) break;
}
if(flag) ans=max(ans,p);
}
cout << ans << endl;
}
// end=clock();
// cout<<"TIME PASSED:"<<end-start<<endl;
return 0;
}
预处理+位元压缩:
#include <time.h>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;
#define maxn 0x3f3f3f3f
#define lowbit(x) (x & -x)
typedef long long ll;
typedef unsigned long long ull;
int gcd(int a, int b) {
if (!b) return a;
return gcd(b, a % b);
}
int coprime[20];
int n;
int ans;
int a[20];
void pre(){
for(int i=0;i<n;++i){
coprime[i]=0;
for(int j=0;j<n;++j){
if(i!=j&&gcd(a[i],a[j])==1){
coprime[i]|=1<<j;
}
}
}
}
void dfs(int id,int cnt,int choosen_mark){
if(id==n){
if(ans<cnt) ans=cnt;
return;
}
if((coprime[id]&choosen_mark)==choosen_mark)
dfs(id+1,cnt+1,choosen_mark|(1<<id));
dfs(id+1,cnt,choosen_mark);
}
int main() {
// clock_t start,end;
// start=clock();
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
int T;
cin >> T;
while (T--) {
cin>>n;
for(int i=0;i<n;++i){
cin>>a[i];
}
ans=0;
pre();
dfs(0,0,0);
cout << ans << endl;
}
// end=clock();
// cout<<"TIME PASSED:"<<end-start<<endl;
return 0;
}
前者要300多ms,后者只要2ms.