woj 1010 Alternate Sum

本文主要是介绍woj 1010 Alternate Sum，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

证明结论之后很简单。考虑集合中每个元素最终对和的贡献：

（1）考虑集合中最大的一个元素，设为t，则在有 t 的子集中，求Alternate Sum时 t 一定是+的（因为它排序后只能在第一个位置），这样的集合有2 ^ (n - 1) 个，从而 t 的贡献为t * 2 ^ (n - 1)；

（2）考虑集合中第二大的元素 t1，它要在子集合中求Alternate Sum时以 - 的形式出现，则该子集必包含第一个元素，这样的集合有2 ^ (n - 2)个，不包含第一个元素的集合也有2 ^ (n - 2)个，所以所有包含 t1 的子集合的Alternate Sum求和时 t1 贡献为0；

（3）考虑集合中第三大的元素 t2，易知 t2 为 - 的情况有2 ^ (n - 2)种（分别是：包含第一个元素但不包含第二个元素：2 ^ (n - 3)，包含第二个元素但不包含第一个元素：2 ^ (n - 3)），为 + 的情况有2 ^ (n - 2)种（分别是：同时包含第一个、第二个元素：2 ^ (n - 3)，同时不包含第一个、第二个元素：2 ^ (n - 3)），所以所有包含 t2 的子集合的Alternate Sum求和时 t2 的贡献为0；

……

从而最终的结果是：max(Q) * 2 (|Q| - 1)

/** Author: stormdpzh* Created Time: 2012/7/12 16:33:32* File Name: woj_1010.cpp*/
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <string>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <functional>#define sz(v) ((int)(v).size())
#define rep(i, n) for(int i = 0; i < n; i++)
#define repf(i, a, b) for(int i = a; i <= b; i++)
#define repd(i, a, b) for(int i = a; i >= b; i--)
#define out(n) printf("%d\n", n)
#define mset(a, b) memset(a, b, sizeof(a))
#define wh(n) while(1 == scanf("%d", &n))
#define whz(n) while(1 == scanf("%d", &n) && n != 0)
#define lint long longusing namespace std;const int MaxN = 1 << 30;int main()
{int n;whz(n) {int maxx;scanf("%d", &maxx);rep(i, n - 1) {int tmp;scanf("%d", &tmp);maxx = max(maxx, tmp);}maxx %= 2006;if(maxx < 0) maxx += 2006;rep(i, n - 1) {maxx *= 2;maxx %= 2006;}printf("%d\n", maxx % 2006);}return 0;
}

这篇关于woj 1010 Alternate Sum的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---