自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 22:22:00，当前版本为作者最后更新于2020-05-25 13:42:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考场上的错误：

1. 输出大小写

2. 二进制优化写挂/kk

这个题目就是变形的多重背包，那么不难想到，用一个 $5\times 10^5$ 的 bool 数组来 dp 每个数能否被选中。

但是这样极限数据是 $200 \times 1000\times 5\times 10^5$，直接爆炸，只能拿 $50\ \text{pts}$。

接下来就是套路性的优化多重背包了：二进制优化。

比如有 $a$ 个价值为 $b$ 的物品，那么他们能组合出的就是 $1\times b,2\times b,\dots a\times b$ 价值的物品。

那么能不能构造另一些物品，让这些物品同样能组合出 $1\times b,2\times b,\dots a\times b$ 价值的物品呢？

可以的。

我们需要构造的是价值为 $1\times b,2\times b,4\times b,\dots 2^n\times b$，其中这些物品价值的总和不超过 $a\times b$ 且 $n$ 尽量大。当然最后离 $a\times b$ 可能还有一些距离，所以要用一个价值为 $(a-\sum_{i=1}^n 2^n)\times b$ 来弥补。

用二进制的位值原理法可以得出这个是正确的。首先，除最后的一个物品可以组合出 价值 $1\times b\sim (2^{n+1}-1)\times b$ 价值的物品。然后再搭配最后一个物品就可以组合出全部物品了。

好处是物品数量由 $a$ 下降到了 $\log a$，但是 $200 \times 10\times 5\times 10^5$ 似乎还是过不了 虽然在洛谷的脚造数据可以过

那么还有一个好东西：bitset

上面的 dp 看起来是这个样子的：

for(j=5e5-l*k;j>=0;j--)
	if(dp[j])
		dp[j+l*k]=1;

欸，那不就是位运算吗？说清楚一些，如果把 dp 数组当作一个大 bool 类型，那么这个操作就等同于 dp|=dp<<l*k。

正好，万能的 STL 库中就有这个好东西 bitset，本质上是一个 bool 数组（内置是用 ull 压了位），但是仍然支持各种位运算。

这样定义：

bitset<500005> dp;

操作也很简洁：

dp|=dp<<l*k;

常数是一般的 bool 数组的 $\dfrac 1 w$，在一般的机子中 $w=64$。

然后凭借卡常技巧卡到了 rank 1/cy

#include<bits/stdc++.h>
using namespace std;
bitset<500005> dp;
int main()
{
//	freopen("watch.in","r",stdin);
//	freopen("watch.out","w",stdout);
	int n,m,i,j,a,k,l;
	scanf("%d%d",&n,&m);
	dp[0]=1;
	for(i=0;i<n;i++)
	{
		scanf("%d%d",&k,&a);
		for(l=1;a>=l;l*=2)
		{
			dp|=dp<<l*k;
			a-=l;
		}
		if(a*k)
			dp|=dp<<a*k;	
	}
	while(m--)
	{
		scanf("%d",&k);
		puts(dp[k]?"Yes":"No");
	}
	return 0;
}