2019牛客暑期多校训练营(第九场) D Knapsack Cryptosystem

淡淡的烟草味﹌ 2023-10-11 09:36 10阅读 0赞

[题目][Link 1]

题意：

给你n（最大36）个数，让你从这n个数里面找出来一些数，使这些数的和等于s（题目输入），用到的数输出1，没有用到的数输出0

例如：3  4

2 3 4

输出：0 0 1

题解：

认真想一下这一道题，首先看到n不是多大就想用dfs（超时），又在dfs的基础上记忆化（超时），大概是我记忆化不完全。又想用01背包，打出来代码后发现s就是体积，但是s的范围太大了，数组存不下 T\_T

看题解发现用一个叫 折半枚举（就是一种思想） 和 [二进制枚举][Link 2] 的东西

折半枚举：比如有时集合过大无法全部搜索，但刚好只需要他们的和或其他可以处理出的东西，就可以一半一半搜

知道了这两个东西，你就可以先对输入的n个数据中的前一半枚举，并记录他们每一个状态的值；之后再对后一半枚举，如果在枚举过程中时刻和前一半枚举的数据对照一下，找到了满足题意得方式就跳出循环

代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <stdio.h>
     2 #include <algorithm>
     3 #include <iostream>
     4 #include <string.h>
     5 #include<math.h>
     6 #include<set>
     7 #include<map>
     8 using namespace std;
     9 const int maxn = 105;
    10 const int INF=0x3f3f3f3f;
    11 const int mod=1000000007;
    12 typedef long long ll;
    13 ll n,s,a[maxn],p[maxn];
    14 int main()
    15 {
    16     map<ll,string>m1;
    17     map<ll,string>m2;
    18     scanf("%lld%lld",&n,&s);
    19     for(ll i=0;i<n;++i)
    20         scanf("%lld",&a[i]);
    21     for(ll i=0;i<1<<(n/2);i++)
    22     {
    23         string vis;
    24         ll sum=0;
    25         for(ll j=0;j<n/2;j++)
    26         {
    27             if((i>>j)&1)
    28             {
    29                 sum=sum+a[j];
    30                 vis.push_back('1');
    31             }
    32             else vis.push_back('0');
    33         }
    34         m1[sum]=vis;
    35     }
    36     for(ll i=0;i<1<<(n-n/2);i++)
    37     {
    38         string vis;
    39         ll sum=0;
    40         for(ll j=0;j<n-n/2;j++)
    41         {
    42             if((i>>j)&1)
    43             {
    44                 vis.push_back('1');
    45                 sum+=a[n/2+j];
    46             }
    47             else vis.push_back('0');
    48         }
    49         m2[sum]=vis;
    50         if(m1.count(s-sum))
    51         {
    52             cout<<m1[s-sum]<<m2[sum]<<endl;
    53             break;
    54         }
    55     }
    56     return 0;
    57 }

顺便在补充一下位运算：

>> :右移 最高位是0，左边补齐0;最高为是1，左边补齐1

<<  :左移 左边最高位丢弃，右边补齐0       （数据没有溢出情况下，右移==除2；左移==乘2）

>>>：无符号右移 无论最高位是0还是1，左边补齐0

2 >> 2  == 4

4 >> 2  ==16

4 << 2  ==1

转载于:https://www.cnblogs.com/kongbursi-2292702937/p/11361690.html

[Link 1]: https://ac.nowcoder.com/acm/contest/889/D
[Link 2]: https://blog.csdn.net/sugarbliss/article/details/81099340
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: https://images.cnblogs.com/OutliningIndicators/ExpandedBlockStart.gif