1020考试T3
题目大意：
SOI2015夏令营期间，营委会计划举办一次拔河比赛，以庆祝我们敬爱的李老爷爷八十大寿。为了使得比赛最激烈，我们希望将参加比赛的营员按照力气值之和分成尽可能平衡的两组。现在假设夏令营有N个人，每个人的力气为M(i)。请大家计算：要使分成的两组力气之和完全相等，有多少种分法？N <= 20。
md题意有毒。我理解为分法，题目让输出选法。
STL + 枚举子集 + 双指针。
首先我们要把这些数分半，因为(2 ^ {20})太大了。然后枚举状态，1代表这个人在集合内，然后在枚举这个状态的子集，也就是把这些人分成两组，然后用vector存起来。
之后双指针扫一下两个vector，看看有没有相同的sum。并且把相同sum合并出的状态标记为1，最后统计1的状态有几个。
#include <bits/stdc++.h>
using namespace std;
inline long long read() {
long long s = 0, f = 1; char ch;
while(!isdigit(ch = getchar())) (ch == '-') && (f = -f);
for(s = ch ^ 48;isdigit(ch = getchar()); s = (s << 1) + (s << 3) + (ch ^ 48));
return s * f;
}
int n, sum;
vector <int> a, b, ans;
vector <pair<int, int> > resa, resb, tmp;
vector <pair<int, int> > rebuild(vector <int> s) {
int m = s.size(); tmp.clear();
for(int i = 0;i < (1 << m); i++) {
for(int j = i; ; j = (j - 1) & i) {
int sum = 0;
for(int k = 0;k < m; k++) {
if(j & (1 << k)) sum -= s[k];
else if(i & (1 << k)) sum += s[k];
}
if(sum >= 0) tmp.push_back(make_pair(sum, i));
if(j == 0) break;
}
}
sort(tmp.begin(), tmp.end());
tmp.resize(unique(tmp.begin(), tmp.end()) - tmp.begin());
return tmp;
}
int main() {
n = read();
for(int i = 0, x;i < n; i++) {
x = read();
if(i & 1) a.push_back(x); else b.push_back(x);
}
resa = rebuild(a); resb = rebuild(b);
int la = resa.size(), lb = resb.size(), l = a.size();
int x = 0, y = 0;
ans.resize(1 << n);
while(x < la && y < lb) {
if(resa[x].first < resb[y].first) x ++;
else if(resa[x].first > resb[y].first) y ++;
else {
int xx = x, yy = y;
while(xx < la && resa[xx].first == resa[x].first) xx ++;
while(yy < lb && resb[yy].first == resb[y].first) yy ++;
for(int i = x;i < xx; i++)
for(int j = y;j < yy; j++) ans[resa[i].second | (resb[j].second << l)] = 1;
x = xx; y = yy;
}
}
for(int i = 1;i < (1 << n); i++) sum += ans[i];
printf("%d", sum);
return 0;
}