UVALive - 6912 Prime Switch （状压DP）

时间：2021-02-08 20:10:49

题目链接：传送门

【题意】有n个灯，m个开关，灯的编号从1~n,每个开关上有一个质数，这个开关同时控制编号为这个质数的倍数的灯，问最多有多少灯打开。

【分析】发现小于根号1000的质数有10个左右，然后大于根号1000的质数所控制的灯是不会重叠的，所以我们状压枚举小于31的质数，然后贪心后面的。

#include <cstdio>

#include <map>

#include <algorithm>

#include <vector>

#include <iostream>

#include <set>

#include <queue>

#include <string>

#include <cstdlib>

#include <cstring>

#include <cmath>

#define inf 0x3f3f3f3f

#define met(a,b) memset(a,b,sizeof a)

#define pb push_back

#define mp make_pair

#define rep(i,l,r) for(int i=(l);i<=(r);++i)

#define inf 0x3f3f3f3f

using namespace std;

typedef long long ll;

const int N = ;;

const int M = ;

const int mod = ;

const int mo=;

const double pi= acos(-1.0);

typedef pair<int,int>pii;

int n,k,cas,cnt;

int a[N],b[];

int vis[N];

int main(){

    int T;

    scanf("%d",&T);

    while(T--){

        cnt=;

        scanf("%d%d",&n,&k);

        for(int i=;i<k;i++){

            scanf("%d",&a[i]);

            if(a[i]<=)b[cnt++]=a[i];

        }

        int ans=;

        for(int i=;i<(<<cnt);i++){

            int now=;

            met(vis,);

            for(int j=;j<cnt;j++){

                if(i&(<<j)){

                    for(int s=b[j];s<=n;s+=b[j])vis[s]^=;

                }

            }

            for(int j=;j<k;j++){

                if(a[j]<=)continue;

                int res=;

                for(int s=a[j];s<=n;s+=a[j]){

                    if(vis[s])res--;

                    else res++;

                }

                if(res<=)continue;

                for(int s=a[j];s<=n;s+=a[j]){

                    vis[s]^=;

                }

            }

            for(int j=;j<=n;j++)if(vis[j])now++;

            ans=max(ans,now);

        }

        printf("Case #%d: %d\n",++cas,ans);

    }

    return ;

}

/*

4

10 2

2 5

21 4

2 3 5 7

100 1

5

100 3

3 19 7

*/

相关文章