CometOJ_六一欢乐赛B题：宝可梦中心大对决！

叁歲伎倆 2023-06-03 03:57 33阅读 0赞

# CometOJ\_六一欢乐赛B题： 宝可梦中心大对决！ #

[题目链接][Link 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70 1]

看着感觉挺简单的，开始想着直接暴力，遍历一遍数组，发现两两不互质，则标记，但是发现这样并不能求出最大数量，看了官方题解，感觉还是有点东西的。。。。

[官方题解][Link 2]

这里用的时间复杂度相对比较高的**使用递归来枚举**

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    int used[20];
    int a[20];
    int t,n;
    int ans;
    int gcd(int x,int y){
        
        return y==0?x:gcd(y,x%y);
    }
    void dfs(int id){
        
        if(id==n){
        
            for(int i=0;i<n;i++){
        
                for(int j=0;j<i;j++){
        
                    if(used[i]&&used[j]&&gcd(a[i],a[j])!=1){
        
                        return ;
                    }
                }
            }
            int cnt=0;
            for(int i=0;i<n;i++){
        
                if(used[i]==1){
        
                     cnt++;
                }
            }
            if(cnt>ans){
        
                   ans=cnt;
            }
            return ;
        }
        used[id]=1;
        dfs(id+1);
        used[id]=0;
        dfs(id+1);
    }
    int  main(){
        
        scanf("%d",&t);
        while(t--){
        
            memset(used,0,sizeof(used));
            memset(a,0,sizeof(a));
            scanf("%d",&n);
            for(int i=0;i<n;i++){
        
                scanf("%d",&a[i]);
            }
            ans=0;
            dfs(0);
            printf("%d\n",ans);
        }
        return 0;
    }

[Link 1]: https://cometoj.com/problem/1026
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70]: /images/20230601/37ce9abbc8ca4db8843ab90a0f36df5a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2JvbGl1MTQ3MjU4_size_16_color_FFFFFF_t_70 1]: /images/20230601/741710292b1f498095a511a9d00ef15e.png
[Link 2]: http://static.eduzhixin.com/cometoj/solution/contest_40.pdf