题目: here https://agc020.contest.atcoder.jp/tasks/agc020_c
题解: 要转化一下, 找所有子集的中间值, 等价于找一个子集, 满足这个子集的和最接近整个序列的和的一半. 也就是一个背包判断可行性的问题. 重点来了, bitset 优化, 至于为什么? 我也不懂啊啊啊啊!!!
注意: 总和为奇数的时候. 这些都不是重点, 重点只有一句: bs | = bs <<tp. 复杂度变成了 O( N^2 * max(Ai) / 64 ), 这儿有个大佬 https://blog.csdn.net/zzzzone/article/details/79115522
- #pragma warning(disable:4996)
- #include<bitset>
- #include<cstdio>
- #include<cstring>
- #include<iostream>
- #include<algorithm>
- #define ll long long
- #define lson root<<1
- #define rson root<<1|1
- #define mid (l+r)>>1
- #define mem(arr, in) memset(arr, in, sizeof(arr))
- using namespace std;
- const int maxn = 4000005;
- int n;
- bitset<maxn> bs;
- int main()
- {
- while (cin>> n) {
- int res = 0;
- bs[0] = 1;
- for (int i = 1; i <= n; i++) {
- int tp;
- cin>> tp;
- res += tp;
- bs |= bs << tp;
- }
- int m = (res + 1) / 2;
- for (int i = m; i <= res; i++) if (bs[i]) {
- printf("%d\n", i);
- break;
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2625997.html