「BZOJ3687」「FJ2014集训」简单题

2014年9月14日6,2682

「题目描述」
小呆开始研究集合论了,他提出了关于一个数集四个问题:
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位,用快速读入会跪

 

avatar
2 Comment threads
0 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
SkyDeczld3794955 Recent comment authors
  Subscribe  
提醒
SkyDec

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

zld3794955

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