某种密码

发布时间：2020-12-14 03:47:54 所属栏目：大数据来源：网络整理

导读：时限1s 空间限制256M 题目描述关于某种密码有如下描述：某种密码的原文A是由N个数字组成，而密文B是一个长度为N的01数串，原文和密文的关联在于一个钥匙码KEY。若 K E Y = ∑ 〖 A i ? B i 〗，则密文就是原文的一组合法密码。现在有原文和钥匙码，请编一

时限1s 空间限制256M

题目描述

关于某种密码有如下描述：某种密码的原文A是由N个数字组成，而密文B是一个长度为N的01数串，原文和密文的关联在于一个钥匙码KEY。若

现在有原文和钥匙码，请编一个程序来帮助他统计到底有多少个符合条件的密文。

输入文件

第一行两个数N，KEY，意义同题目描述；

第二行N个数表示原文A，意义同题目描述。

输出数据

一个数ANS，表示对于原文A和KEY，有多少组可行的密文B。

输入样例

3 2
1 1 2

输出样例

样例说明

密文

一共两组可行的密文。

?题解: 其实有点像双向搜索，因为2^40必定TLE，就不如这般搜索一下（味道更好

我们先处理前一半的加和的情况，在处理后一半加和的情况，如果两个加起来是key的话计算时一种情况了

保存加和情况的最好用hash表

（但是本宝宝实在是太弱了，就用map了

差不多就是这样的。。emm

#include <bits/stdc++.h>
#include <map>

using namespace std;

typedef long long ll;

inline ll read() {
    ll x = 0,f = 1; char ch = getchar();
    for ( ; !isdigit(ch) ; ch = getchar()) if (ch == ‘-‘) f = -1;
    for ( ; isdigit(ch) ; ch = getchar()) x = x * 10 + ch - ‘0‘;
    return x * f;
}

const ll maxn = 50;

ll a[maxn];

ll n,key;

ll _left_geshu,_right_geshu,ans;

map <ll,ll> M;

int main() {
    n = read(),key = read();
    for (ll i = 1 ; i <= n ; i ++) {
        a[i] = read();
    }

    _left_geshu = (1 + n) >> 1,_right_geshu = n - _left_geshu;

    for (ll i = 0 ; i < (1 << _left_geshu) ; i ++) {
        ll tmp = 0;
        for (ll j = 0 ; j < _left_geshu ; j ++) {
            if (i & (1 << j)) {
                tmp += a[j + 1];
            }
        }
        M[tmp] ++;
    }
    for (ll i = 0 ; i < (1 << _right_geshu) ; i ++) {
        ll tmp = 0;
        for (ll j = 0 ; j < _right_geshu ; j ++) {
            if (i & (1 << j)) {
                tmp += a[_left_geshu + 1 + j];
            }
        }
        if (M[key - tmp]) {
            ans += M[key - tmp];
        }
    }

    printf("%lldn",ans);
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!