首页 > > 程序设计 > C/C++ >

某种密码

2018-09-01 05:38:04来源：博客园阅读 ()

时限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("%lld\n" , ans);
}