黄学长模拟day1 某种密码
2024-10-15 20:51:02
关于某种密码有如下描述:某种密码的原文A是由N个数字组成,而密文B是一个长度为N的01数串,原文和密文的关联在于一个钥匙码KEY。若KEY=∑▒〖Ai*Bi〗,则密文就是原文的一组合法密码。
现在有原文和钥匙码,请编一个程序来帮助他统计到底有多少个符合条件的密文。
【输入数据】
第一行两个数N,KEY,意义同题目描述;
第二行N个数表示原文A,意义同题目描述。
【输出数据】
一个数ANS,表示对于原文A和KEY,有多少组可行的密文B。
【输入样例】
3 2
1 1 2
【输出样例】
2
【样例说明】
密文110,1*1+1*1+0*2=2
密文001,0*1+0*1+1*2=2
一共两组可行的密文。
【数据约定】
60%数据满足N<=25
100%数据满足N<=40,-maxlongint<=∑▒Ai<=maxlongint
/*
这道题作为第一题难度确实是不大,但一定要有这个优化的意识,如果纯粹搜索所有方案,时间无法承受,我们可以考虑到,当前面一些的值计算出来,后面的值等于说是在前面的基础上进行进一步的计算,我们于是考虑到去掉“在前面的基础上”这个指数级的冗余运算,通过后面和前面比较,先算前面的,后面的看有没有那个和他相加等于K的就行了,hash运算,注意sum可能是一个很大的负数
*/
//我写的hash
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#define ll long long
#define fo(i,l,r) for(int i = l;i <= r;i++)
using namespace std;
const ll sed = ,Sed = ,mod = ,Mod = ;
struct dat{
ll v;
ll a;
};
int n;
bool gt;
vector<dat> h[mod];
ll a[],key,ans,lm;
inline void dfs(int pos,ll sum){
if(pos <= lm){
dfs(pos+,sum+a[pos]);
dfs(pos+,sum);
}else{
dat tmp;
if(!gt) {
ll ha = (sum + mod*) % mod;
ll hb = (sum + Mod*) % Mod;
for(int i = ;i < h[ha].size();i++){
if(h[ha][i].v == hb){
h[ha][i].a++;
return;
}
}
tmp.v = hb;
tmp.a = ;
h[ha].push_back(tmp);
}else{
ll ha = (key - sum + mod*) % mod;
ll hb = (key - sum + Mod*) % Mod;
for(int i = ;i < h[ha].size();i++){
if(h[ha][i].v == hb){
ans+=h[ha][i].a;
break;
}
}
} }
}
int main(){
freopen("password.in","r",stdin);
freopen("password.out","w",stdout);
cin>>n>>key;
fo(i,,n){
cin>>a[i];
}
if(n == ){
ans = (a[] == key) + ( == key);
return ;
}
lm = n >> ;
dfs(,);
gt = true;
lm = n;
dfs((n >> )+,);
cout<<ans;
return ;
}
//黄学长Map
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<map>
#include<vector>
#define ll long long
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
bool flag;
ll ans;
int n,cnt,key;
int a[];
map<int,int> b;
void dfs(int x,int now)
{
if(x==cnt+)
{
if(!flag)b[now]++;
else ans+=b[key-now];
return;
}
dfs(x+,now+a[x]);
dfs(x+,now);
}
int main()
{
//freopen("password.in","r",stdin);
//freopen("password.out","w",stdout);
n=read();key=read();
for(int i=;i<=n;i++)
a[i]=read();
cnt=n/;dfs(,);
flag=;cnt=n;dfs(n/+,);
printf("%I64d",ans);
return ;
}
最新文章
- opencv 之 icvCreateHidHaarClassifierCascade 分类器信息初始化函数部分详细代码注释。
- Windows 10 Build 14997中Edge浏览器已默认阻止Flash运行
- 4.27-4.30webstorm
- iOS 使用XCode6打开项目以后再用XCode5出现的问题fatal error: malformed or corrupted AST file: &#39;Unable to load module
- JAVA坏境变量中的JAVA_HOME path classpath 的设置与作用。
- [ActionScript 3.0] AS3.0 Loader加载子swf时是否需要指定新的应用程序域ApplicationDomain
- hbase表结构设计
- SpringMVC处理Date类型的成员变量方法
- loadrunner java协议脚本要点
- 阿里云ECS每天一件事D3:挂载硬盘
- 安卓弹出对话框——AlertDialog(二)
- JQuery实现Ajax跨域访问--Jsonp原理
- Python进阶——笔记1
- 再学ajax--第一天
- C# 实体类转json数据过滤掉字段为null的字段
- 存储与服务器的连接方式对比(DAS,NAS,SAN)
- D - The Lucky Week ZOJ - 3939 (思维)
- Shiro笔记(四)编码/加密
- MYSQLI_USE_RESULT or MYSQLI_STORE_RESULT
- weblogic+eclipse插件部署多个项目