牛客練習賽43 F Tachibana Kanade Loves Game 容斥定理

題目連結：

https://ac.nowcoder.com/acm/contest/548/F

思路：

盡量選傷害對手而不傷害自己的武器，如果這些武器用完了，就選既傷害自己又傷害對手的武器。

選不傷害自己的武器其實就是選不是2,3...m的倍數，這其實可以進一步推出選不是2--m中的素數的倍數，因為每一個數都可以被表示成素數相乘。

找不是2-m中素數的倍數其實可以用n減去2-m素數的并集，這裡就需要用容斥定理了。

可以通過dfs來取容斥定理所需要的集合，然後套用容斥定理公式即可。

還有幾個優化：

(1)如果自身血量==0，則直接算輸。

(2)如果自己的武器數小于敵人血量則算輸。

求出總數sum之後，n-sum就是不傷害自己的總數。

如果n-sum>=k赢。

否則則需要傷害自己的武器補傷害，如果傷害不夠或者補着補着自己就死了則算輸。

否則算赢

代碼如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
ll k,q,n,m;
int su[15]={0,2,3,5,7,11,13,17,19};
int vis[15];
int re[15];
ll sum;
int r;
void dfs(int loc,int nn,int nnum)
{
    if(nnum==nn)
    {
        ll tsum=1;
        for (int i=0;i<nn;i++)
        {
            tsum*=su[re[i]];
        }
        if(nn%2) sum=sum+n/tsum;
        else sum=sum-n/tsum;
        return;
    }
    for (int i=loc;i<=r;i++)
    {
        if(!vis[i])
        {
            vis[i]=1;
            re[nnum]=i;
            dfs(i+1,nn,nnum+1);
            vis[i]=0;
        }
    }
}
int main()
{

    while(scanf("%d",&t)!=EOF)
    {
        while(t--)
        {
            scanf("%lld%lld%lld%lld",&k,&q,&n,&m);
            sum=0;
            if(k==0||q>n)
            {
                printf("QAQ\n");
                continue;
            }
            r=0;
            for (int i=1;i<=8;i++)
            {
                if(m<su[i]) break;
                r++;
            }
            for (int i=1;i<=r;i++)
            {
                memset (vis,0,sizeof(vis));
                dfs(1,i,0);
            }
            if(n-sum>=q)
            {
                printf("Yes\n");
                continue;
            }
            q=q-(n-sum);
            if(sum<q||k<q)
            {
                printf("QAQ\n");
            }
            else
            {
                printf("Yes\n");
            }
        }
    }
    return 0;
}