题解 P6567 【[NOI Online #3 入门组]买表】

· · 题解

考场上的错误：

  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;
}