bitset优化01可行背包

例题传送门：『STA - R3』Aulvwc

先讲bitset用法：

1，基础

下标：\(5~4~3~2~1~0\)

数字：\(0~0~0~0~1~0\)

\(bitset\)<\(n\)> \(s\)表示一个\(n\)位的二进制数，空间复杂度：\(O(\frac{n}{32})\)，可见其非常优秀

因为其跟二进制有关，所以可以使用\(\&,|,\land\)对两个位数相同的\(bitset\)执行按位与，或，异或运算。

当然也可以使用\(<<,>>\)对其进行左移和右移

\(==,!=\)也可以比较两个位数相同的\(bitset\)代表的二进制数是否相等

2，特有的

\(s.count()\)返回二进制串中\(1\)的个数

\(s.set()\)把\(s\)的所有位变成\(1\)

\(s.set(k,v)\)或\(s[k]\)把\(s\)的第\(k\)位变为\(v\)，其中\(v\)为\(0\)或\(1\)

\(s.reset()\)把\(s\)的第\(k\)位变为\(0\)

\(s.reset(k)\)把\(s\)的第\(k\)位变成\(0\)

\(s.filp()\)或\(s=\sim s\)把\(s\)所有位取反

\(s.filp(k)\)或\(s[k]\land=1\)把第\(k\)位取反

\(01\)背包，即背包中只有\(0\)和\(1\)，一般\(f_i\)表示\(i\)这个数能否取到

正常\(01\)背包代码

f[0]=1
for(int i=1;i<=n;i++)
for(int j=m;j>=a[i];j--)
  f[j]=max(f[j],f[j-a[i]]);

但是对于每个数只有选和不选的情况下

我们考虑构建\(bitset\)<\(m\)> \(s\)，其中第\(i\)位表示\(i\)能否取到

那么对于加入的\(a_i\)我们考虑我们选\(a_i\)，如果我们选\(a_i\)，那么代表原来能取到\(j\)的数，就能取到\(j+a_i\)，因为第\(i\)位表示\(i\)能否取到，所以我们选\(a_i\)能取到的值域就是\(s<<=a_i\)，不选\(a_i\)就是\(s\)，所以最终的\(s\)就是\(s=(s|(s<<=a_i))\)

代码：

bitset<m> s;
s.set(0,1);
for(int i=1;i<=n;i++)
s|=(s<<a[i]);

非常快，那么例题就可用这种优化优化到\(O(qnw),w=max(a_i)\)

上代码：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=2e3+50,M=3e6+50;
ll q,n,a[N],zh;
bool flag=false;
bitset<M> f,f1;
int main()
{
	scanf("%lld",&q);
	while(q--)
	{
		flag=false;
		zh=0;
		scanf("%lld",&n);
		for(ll i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);
			zh+=a[i];
		}
		if(zh%n!=0)
		{
			puts("No");
			continue;
		}
		zh=zh/n;
		for(ll i=1;i<=n;i++)
		a[i]-=zh;
		for(ll i=1;i<=n;i++)
		if(a[i]==0) flag=true;
		if(flag)
		{
			puts("Yes");
			continue;
		}
		
		f.reset();
		f1.reset();
		f.set(0,1);
		f1.set(0,1);
		for(ll i=1;i<=n;i++)
		{
			if(a[i]<0)
			{
				a[i]=a[i]*-1;
				f=(f|(f<<a[i]));
			}
			else f1=(f1|(f1<<a[i]));
		}
		f=(f&f1);
		if(f.count()>2) puts("Yes");
		else puts("No");
	}
	return 0;
}

注意代码中\(f.count()>2\)因为\(0\)和都选一定是都能取到的，假如还有第三种能取到，那么就是\(Yes\)，否则为\(No\)