题目描述
给出n个数a[i]，现在可以在其中任意选出若干个数，问有多少种选择方案，使得这几个数可以分成两个和相等的集合。
思路
将这个序列分为两份进行处理，对于每一个数我们可以在其前面加上系数[-1,0,1],来表示它是放在左集合/右集合或是不选
首先可以通过搜索得出所有的状态，然后我们就可以用指针在两段里面分别进行查找，如果相加等于0，那么就是一个符合的方案
然后显然会有重复的情况，我们可以用一个十进制数来表示每一个状态，然后相加时也用左边的进行左移然后加上右边的进行判重即可
#include#include using namespace std; int a[21], n, ll = 0, rr = 0, totl, totr; struct arr { int x, w; }l[70000]; arr r[70000]; bool fl[20000000]; int cmp(arr a, arr b) { return a.x < b.x; } int dfs(int dep, int end, int tot, int o, int m) { if (dep > end) { if (o == 1) { if (m == 0) return 0; l[++ll].x = tot; l[ll].w = m; return 0; } else { if (m == 0) return 0; r[++rr].x = tot; r[rr].w = m; return 0; } return 0; } dfs(dep + 1, end, tot + a[dep], o, m * 2 + 1); dfs(dep + 1, end, tot - a[dep], o, m * 2 + 1); dfs(dep + 1, end, tot, o, m * 2); } int main() { // freopen("number.in", "r", stdin); // freopen("number.out", "w", stdout); scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); dfs(1, n / 2, 0, 1, 0); dfs(n / 2 + 1, n, 0, 2, 0); int ans = 0; sort(l + 1, l + ll + 1, cmp); sort(r + 1, r + rr + 1, cmp); int j = rr; for (int i = 1; i <= ll; i++) { while (l[i].x + r[j].x > 0 && j > 0) j--; int k = 0; int jj = j; while (l[i].x + r[j].x == 0 && j > 0) { if (!fl[(l[i].w << (n / 2 + 1)) + r[j].w]) fl[(l[i].w << (n / 2 + 1)) + r[j].w] = 1; else k++; j--; } ans += (jj - j) - k; j = jj; } for (int i = 1; i <= ll; i++) if (l[i].x == 0 && !fl[l[i].w << (n / 2 + 1)]) { ans++; fl[l[i].w << (n / 2 + 1)] = 1; } for (int i = 1; i <= rr; i++) if (r[i].x == 0 && !fl[r[i].w]) { ans++; fl[r[i].w] = 1; } printf("%d\n", ans); }
]]>
Comments NOTHING