2019牛客暑期多校训练营（第九场） - D - Knapsack Cryptosystem（折半枚举）

本文主要是介绍2019牛客暑期多校训练营（第九场） - D - Knapsack Cryptosystem（折半枚举），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：https://ac.nowcoder.com/acm/contest/889/D

题意：挑选若干个数使得和为s。

思路：考虑二进制枚举，但是n的范围是36，直接枚举会超时，所以我们把数组分两部分枚举，然后用map映射一下即可。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[50], sum, s;
int m, n;
map <ll, string> mp1, mp2;
string str;
int main()
{scanf("%d%lld",&n, &s);for(int i = 0; i < n; i++) scanf("%lld", &a[i]);m = n / 2; n = n - m;for(int i = 0; i < (1 << m); i++){sum = 0; str = "";for(int j = 0; j < m; j++){if(i & (1 << j))sum += a[j], str += '1';else str += '0';}mp1[sum] = str;}for(int i = 0; i < (1 << n); i++){sum = 0; str = "";for(int j = 0; j < n; j++){if(i & (1 << j))sum += a[m+j], str += '1';else str += '0';}mp2[sum] = str;}for(auto it : mp1)if(mp2.count(s-it.first))return cout << it.second << mp2[s-it.first] << endl, 0;
}

 

这篇关于2019牛客暑期多校训练营（第九场） - D - Knapsack Cryptosystem（折半枚举）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---