Forgive_jkxjkx1031 edited 6 年，11 月前
可以用位运算实现。
先考虑第一个方案。用一个数组 (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);
}