牛客多校第九场 D Knapsack Cryptosystem 背包
2024-08-27 23:38:49
题意:
给你32个物品,给定一个容积,让你恰好把这个背包装满,求出装满的方案
题解:
暴力计算的话,复杂度$2^{32}$肯定会炸,考虑一种类似bsgs的算法,先用$2^{16}$的时间遍历前一半物品的所有子集,将所得结果存进map里,再遍历后一半物品的子集,每得到一个解,在map里查询有没有相加正好得到背包大小的解。总时间复杂度$2^{16}log2^{16}=16*2^{16} \approx 1e6$
#include<iostream>
#include<map>
#define ULL unsigned long long
using namespace std;
void bind(int k,int n){
while(n--){
printf("%d",k&);
k>>=;
}
}
ULL a[];
map<ULL,int> mapp;
int main(){
int n;
ULL ans;
scanf("%d %lld",&n,&ans);
for(int i=;i<=n;i++)scanf("%lld",&a[i]);
int h=n/;
int w=<<h;
int i=;
while(!(i&w)){
ULL sum=;
for(int j=;j<=h;j++){
if((<<(j-))&i)sum+=a[j];
}
mapp[sum]=i;
i++;
}
w=<<(n-h);
i=;
while(!(i&w)){
ULL sum=;
for(int j=;j<=n-h;j++){
if((<<(j-))&(i))sum+=a[j+h];
}
map<ULL,int>::iterator it=mapp.find(ans-sum);
if(it!=mapp.end()){
bind(it->second,h);
bind(i,n-h);
printf("\n");
break;
}
i++;
}
return ;
}
拓展知识:背包公钥密码体系
背包公钥密码体系是利用背包问题(子集和问题)的NP完全性保证安全性的密码体系。
私钥持有者Alice找一个超递增序列,即某位大于前面所有位之和。比如M={3,11,24,50,115}
在超递增序列上求解求解背包是十分容易的,只需从后往前贪心即可,此结论留给读者自证。
私钥部分除了超递增序列,还有一个乘数r和模数m,需要保证r在模m意义下有逆元。通过私钥计算公钥的过程实际上是把超递增序列伪装成一个非超递增序列的过程。
伪装过程,就是把M的每一位乘r模m。比如令r=113,m=250,则M'=M*113%250={89,243,212,150,245}
这个M'就是公钥。
Bob获得了公钥,要给Alice发送一段消息,假设明文为x={1,0,1,0,1},将公钥和明文做个内积就得到了密文,s=1*89+0*243+1*212+0*150+1*245=546
Alice知道了密文后,将密文模乘r的逆元,$s*r^{-1}$ $mod$ $m=546*117$ $mod$ $250=142$,再在M上贪心即可。
而第三方得知了公钥和密文后,需要花费$n*2^{n/2}$时间才可解出明文。
最新文章
- 几款比较好用的C语言的集成开发环境及在windows下用命令行编译C代码
- mvc5+ef6+Bootstrap 项目心得--WebGrid
- PHP文件操作 读取与写入
- 备份MYSQL出现:mysqldump: Got error: 1049: Unknown database &#39;test &#39;when selecting the data
- asp.net实现关闭当前网页
- Android 常用的常量
- MFC容器类介绍
- JS实现Tab切换
- DIV 遮挡问题总结
- 如何禁用Visual Studio 2013的Browser Link功能
- python httpConnection详解
- NAT( 网络地址转换) 实现
- iOS四种多线程(swift和oc)
- jenkins系列之插件配置(二)
- 数据库备份和还原(固定IP版)
- HTTP 方法:Get与Post分析
- oralce定时任务
- 关于tomcat性能优化
- composer ip2city配置
- IIS 域名 带参数 设置重定向
热门文章
- js 暂停几秒后刷新或提交
- Eclipse中安装SVN插件的艰难旅程
- RVIZ可视化平台
- linux浏览器,邮件客户端,输入法,双屏设置,应用软件,gnome-screenshot/scrot -s截图,office
- CSS:CSS Positioning(定位)
- pycharm中evaluate expression的用法
- jquery中的ajax方法参数的用法和他的含义
- springboot + zipkin + mysql
- 22-3concat
- Linux 父进程发送信号杀死子进程