Comet OJ 六一欢乐赛

题目链接:宝可梦中心大对决

已知共有 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.