#3272 简易版题解

Forgive_jkxjkx1031 edited 3 年,1 月前

可以用位运算实现。

先考虑第一个方案。用一个数组 (b[]) 表示集合,即当且仅当集合中存在 (x) 时 (b[x]=1)。于是可以枚举 (a[i]) 和 (b[j]),判断 (b[j+a[i]]) 是否为 0 。
存在的问题:复杂度是 (n*\max{a[i]}),必定会超时。

第二个方案。将 01 数组 (b[]) 用二进制数 (B) 表示,于是可以直接判断 (B \& (B \ll a[i])) 是否为零来获得答案。
存在的问题:(B) 的值最大可能为 (2^{200000}),C++ 不提供满足要求的数据类型。

所以我们考虑一个折中的方案:将数组 (b[]) 分块,每块都用二进制数表示。由于 C++ 中最大的整数类型占 64 位,因此可以把每 64 各元素合成一个二进制数。这样的复杂度是 (n*\max{a[i]}/64),可以在规定时间内跑完。

当然其中还有许多细节,比如需要时刻注意数据类型的范围、位移量不是 64 的整数倍时的处理方法、如何确保 (i \neq j \neq k) ......

附上 AC 代码(代码风格差求轻喷(灬°ω°灬) ):

#include <stdio.h>
#include <string.h>
#define MAX(X,Y) ((X)>(Y) ? (X) : (Y))

typedef unsigned long long ULL;
int T,n,m,a[50010];
ULL b[10010];
ULL high(ULL n,ULL len);
ULL low(ULL n,ULL len);

int main(void)
{
    freopen("nuclear.in","r",stdin);
    freopen("nuclear.out","w",stdout);
    scanf("%d",&T);
    int cas;
    for(cas=1;cas<=T;cas++)
    {
        scanf("%d",&n);
        memset(b,0,sizeof(b));
        int i,j;
        for(m=0,i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            b[a[i]/64]|=(ULL)1<<(a[i]%64);
            m=MAX(m,a[i]/64);
        }
        printf("Case %d: ",cas);
        int k,d;
        for(i=1;i<=n;i++)
        {
            for(j=0;j<=m;j++)
            {
                k=j+a[i]/64;  d=a[i]%64;
                if(k>m) continue;
                if(a[i]/64==j)
                    b[j]-=(ULL)1<<(a[i]%64);
                if((low(b[k+1],d) & high(b[j],d)) > 0
                   || (high(b[k],64-d) & low(b[j],64-d)) > 0) break;
                if(a[i]/64==j)
                    b[j]+=(ULL)1<<(a[i]%64);
            }
            if(j<=m) break;
        }
        if(i<=n) printf("NO\n");
        else printf("YES\n");
    }
    return 0;
}

ULL low(ULL n,ULL len)
{
    if(!len) return 0;
    else if(len==64) return n;
    else return n&(((ULL)1<<len)-1);
}

ULL high(ULL n,ULL len)
{
    if(!len) return 0;
    else if(len==64) return n;
    else return n>>(64-len);
}

Comments

你当前正在回复 博客/题目
存在问题!