【BestCoder Round #83】A.zxa and set

发布于 2016-11-15  557 次阅读


问题描述
zxa有一个集合A=\{a_1,a_2,...,a_n\}A={a1,a2,,an}nn表示集合AA的元素个数,这个集合明显有(2^n-1)(2n1)个非空子集合。

对于每个属于AA的子集合B=\{b_1,b_2,...,b_m\}(1\leq m\leq n)B={b1,b2,,bm}(1mn)mm表示集合BB的元素个数,zxa定义它的价值是\min(b_1,b_2,\cdots,b_m)min(b1,b2,,bm)。

zxa很好奇,如果令S_{odd}Sodd表示集合AA的所有含奇数个元素的非空子集合的价值之和,S_{even}Seven表示集合AA的所有含偶数个元素的非空子集合的价值之和,那么|S_{odd}-S_{even}|SoddSeven是多少,你能帮助他吗?
输入描述
第一行有一个正整数TT,表示有TT组数据。

对于每组数据:

第一行有一个正整数nn,表示集合有nn个元素。

第二行有nn个互异的正整数,表示集合的元素a_1,a_2,...,s,a_na1,a2,,an。

每一行相邻数字之间只有一个空格。

1\leq T\leq 100,1\leq n\leq 30,1\leq a_i\leq 10^91T100,1n30,1ai109
输出描述
对于每组数据,输出一行,包含一个非负整数,表示|S_{odd}-S_{even}|SoddSeven的值。
输入样例
3
1
10
3
1 2 3
4
1 2 3 4
输出样例
10
3
4
Hint
对于第一组样例,A=\{10\}A={10},它只有一个含奇数个元素的子集合\{10\}{10},没有含偶数个元素的子集合,所以S_{odd}=10,S_{even}=0,|S_{odd}-S_{even}|=10Sodd=10,Seven=0,SoddSeven=10。

对于第二组样例,A=\{1,2,3\}A={1,2,3},它有四个含奇数个元素的子集合\{1\},\{2\},\{3\},\{1,2,3\}{1},{2},{3},{1,2,3},有三个含偶数个元素的子集合\{1,2\},\{2,3\},\{1,3\}{1,2},{2,3},{1,3},所以S_{odd}=1+2+3+1=7,S_{even}=1+2+1=4,|S_{odd}-S_{even}|=3Sodd=1+2+3+1=7,Seven=1+2+1=4,SoddSeven=3

题目分析:通过样例和小数据先猜测ans=max{a[i]}。
给出证明:

由于a_i互不相同,因此可以考虑每个元素在哪些子集中是最小值。

a_iA中第k大的元素,以a_i为最小值的集合只能包含不小于a_i的元素,因此这样的集合有2^{k-1}个。

如果k=1,则只有{a_i}a_i为最小值;否则,上述集合中包含最大元素的子集和不包含最大元素的子集的元素个数奇偶性不同,对答案的贡献相互抵消。因此有S_{odd}-S_{even}=\max(a_i)SoddSeven=max(ai)

实际上,a_i不需要互不相同,也可以得到答案是\max(a_i)的结论。

code:略.


「知我罪我,其惟春秋」