本文主要是介绍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的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!