首页 > 代码库 > 【bzoj3687】简单题 背包dp+STL-bitset
【bzoj3687】简单题 背包dp+STL-bitset
题目描述
小呆开始研究集合论了,他提出了关于一个数集四个问题:
1.子集的异或和的算术和。
2.子集的异或和的异或和。
3.子集的算术和的算术和。
4.子集的算术和的异或和。
目前为止,小呆已经解决了前三个问题,还剩下最后一个问题还没有解决,他决定把这个问题交给你,未来的集训队队员来实现。
输入
第一行,一个整数n。
第二行,n个正整数,表示01,a2….,。
输出
一行,包含一个整数,表示所有子集和的异或和。
样例输入
2
1 3
样例输出
6
题解
背包dp+STL-bitset
首先想想暴力怎么做?设f[i]表示i出现在算术和中的次数,那么对于a[j],有f[i]+=f[i-a[j]]。最后统计哪些数出现了奇数次即可。
那么怎么优化这个暴力?我们其实不需要知道某个数出现的具体次数,只需要知道它出现次数的奇偶性即可。
所以我们可以使用bitset压位来解决。
具体实现还是比较简单的,直接位运算然后异或即可。
#include <cstdio>#include <bitset>using namespace std;bitset<2000010> f;int main(){ int n , i , x , m = 0 , ans = 0; scanf("%d" , &n); f[0] = 1; for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &x) , f ^= (f << x) , m += x; for(i = 1 ; i <= m ; i ++ ) if(f[i]) ans ^= i; printf("%d\n" , ans); return 0;}
【bzoj3687】简单题 背包dp+STL-bitset
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。