【bzoj3687】【FJ2014集训】简单题

2014年9月14日3,0832

【题目描述】
小呆开始研究集合论了,他提出了关于一个数集四个问题:
1. 子集的异或和的算术和。
2. 子集的异或和的异或和。
3. 子集的算术和的算术和。
4. 子集的算术和的异或和。
目前为止,小呆已经解决了前三个问题,还剩下最后一个问题还没有解决,他决定把
这个问题交给你,未来的集训队队员来实现。
【输入格式】
从 xor.in 中输入数据
第一行,一个整数 n。
第二行,n 个正整数,表示 a1, a2, …, an
【输出格式】
输出到 xor.out 中
一行,包含一个整数,表示所有子集和的异或和。
【样例输入】
2
1 3
【样例输出】
6
【样例解释】
6 = 1 ⊗ 3 ⊗ (1 + 3)
【数据规模与约定】
数据分为 A,B,C 三类。
A 类数据 (20%) 保证:ai > 0,1 ≤ n ≤ 10。
B 类数据 (40%) 保证:ai > 0,1 ≤ n ≤ 1000,
∑ ai ≤ 10000。
C 类数据 (40%) 保证:ai > 0,1 ≤ n ≤ 1000,
∑ ai ≤ 2000000。
另外,不保证集合中的数满足互异性,即有可能出现 ai = aj 且 i ̸= j。

【题解】

蒟蒻比赛的时候只会60直接背包。。。

学了下bitset好像很优越

不过这题数据似乎有问题。。不满n位,用快速读入会跪

 

  • zld37949552014年7月21日 下午3:42 回复

    bitset声明之后你就可以当作一个可以进行位运算的bool数组就好了= =

    #1  
  • SkyDec2014年9月15日 下午9:14 回复

    我为了卡过去加了读入优化,然后因为数据不全WA了半天

    #2