FindNumbers
时间限制：5s 内存限制：65536K
问题描述：
给n个非负整数，满足对于某正整数k，n=2^k-1。从中选出(n+1)/2个数，使得它们的和是(n+1)/2的倍数。
输入
第一行，T，询问个数。
下面2T行，每两行是一个询问。对于每两行：
第一行，n。
第二行，n个整数，a_0, a_1, ..., a_{n-1}。
1<=T<=20
1<=n<=2^15
0<=a_i<=10^9
输出
对第i个（1<=i<=T）询问的回答为两行，第一行为编号：
Case #i:
第二行为结果：
如果不能选出这样的(n+1)/2个数，输出-1；
否则输出一行，用一个空格分隔的(n+1)/2个数b_0, b_1, ..., b_{(n+1)/2-1}。满足b_i两两不同，且sum(a_{b_i})是(n+1)/2的倍数。如果有多解，输出任意一个。
样例输入
2
3
1 3 5
7
0 1 2 3 4 5 6
样例输出：
Case #1:
0 2
Case #2:
0 2 4 6
解题报告 –
FindNumbers
鉴于n=2^k-1（k为正整数），因此由归纳法可证明必有解。
证明：
归纳基础：对于k=1，显然成立，
归纳假设：假定对于任意正整数k，有解。
归纳推理：考虑对于n=2^(k+1)-1的情形，我们可以将a[0..n-1]分为a[0..2^k-2]和a[2^k-1..n-2], 由归纳假设可得：
从a[0..2^k-2]中我们可以挑出(m+1)/2个数b1[0..(m-1)/2]， 满足sum{b1[0..(m-1)]}=r*(m+1)/2，其中m=2^k-1，r为某个非负整数。
从a[2^k-1..n-2]中我们可以挑出(m+1)/2个数b2[0..(m-1)/2]， 满足sum{b2[0..(m-1)]}=s*(m+1)/2，其中m=2^k-1，s为某个非负整数。
从a-b1-b2中（含|a-b1-b2|=m个非负整数）我们可以挑出(m+1)/2个数b3[0..(m-1)/2]， 满足sum{b3[0..(m-1)]}=t*(m+1)/2，其中m=2^k-1，t为某个非负整数。
由于r,s,t三个非负整数中必有两个奇偶性相同，从而{(r+s),(s+t),(r+t)}中必有某个为2的倍数。若(r+s)%2==0, 则可将b1和b2合并得到m+1=(n+1)/2个非负整数且sum{b1,b2}=(r+s)*(m+1)/2=(r+s)/2*(m+1)=(r+s)/2*(n+1)/2，为(n+1)/2的倍数。其他情况同理可得。
证毕
由上述证明，可得到分治算法，先将a分为a[0..(n-1)/2-1]和a[(n-1)/2..n-2],递归分别求得b1和b2, 如果sum{b1+b2}满足条件，则返回，否则对a-b1-b2递归，求得b3，如果sum{b1+b3}满足条件，则返回，否则sum{b2+b3}必满足条件，返回。易见该算法复杂度为O(nlogn)。
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cassert>
#include <ctime>
#include <set>
#include <map>
#include <vector>
#include <string>
#include <sstream>
#include <iostream>
#include <algorithm>
//#include <sys/time.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<vector<int>, int> PVI;
#define N 65555
int a[N];
vector<int> comb(const vector<int>&a, const vector<int>&b) {
vector<int> c;
int l = 0, r = 0; int n = (int) a.size();
while (l < n && r < n) {
if (a[l] < b[r]) c.pb(a[l++]);
else c.pb(b[r++]);
}
while (l < n) c.pb(a[l++]);
while (r < n) c.pb(b[r++]);
return c;
}
PVI ff(const vector<int>&p) {
int n = (int) p.size(); int m = (n+1)/2;
if (n == 1) return mp(p, a[p[0]]);
vector<int> p1, p2;
for (int i = 0; i < n/2; i ++) p1.pb(p[i]);
for (int i = n/2; i < n-1; i ++) p2.pb(p[i]);
PVI s1 = ff(p1), s2 = ff(p2);
if ((s1.se + s2.se) % m == 0) return mp(comb(s1.fi, s2.fi), s1.se + s2.se);
vector<int> p3; int l = 0, r = 0;
for (int i = 0; i < n; i ++) {
while (l < (n+1)/4 && s1.fi[l] < p[i]) l ++;
while (r < (n+1)/4 && s2.fi[r] < p[i]) r ++;
if ((l == (n+1)/4 || s1.fi[l] > p[i]) && (r == (n+1)/4 || s2.fi[r] > p[i])) p3.pb(p[i]);
}
PVI s3 = ff(p3);
if ((s1.se + s3.se) % m == 0) return mp(comb(s1.fi, s3.fi), s1.se + s3.se);
if ((s2.se + s3.se) % m == 0) return mp(comb(s2.fi, s3.fi), s2.se + s3.se);
}
int main()
{
// timeval start;
// gettimeofday(&start, NULL);
int T;
scanf("%d", &T);
for (int c = 1; c <= T; ++c) {
int n; scanf("%d", &n);
int m = (n+1)/2;
for (int i = 0; i < n; i ++)
scanf("%d", a+i), a[i] %= m;
vector<int> p;
for (int i = 0; i < n; i ++)
p.pb(i);
vector<int> s = ff(p).fi;
printf("Case #%d:
", c);
for (int i = 0; i < (n+1)/2; i ++)
printf ("%d%c", s[i], i == n/2 ? '
': ' ');
}
// timeval end;
// gettimeofday(&end, NULL);
// double duration = ((long long) end.tv_sec * 1000000 + end.tv_usec - (long long) start.tv_sec * 1000000 + start.tv_usec) / 1000000.0;
// fprintf(stderr, "%.1fsec
", duration);
return 0;
}