Balanced Cow Subsets G

链接

题意很简单,给出一个序列,找到这个序列有多少个子序列可以拆为两个新的子序列,且这两个子序列的元素之和相等

由于数据很大,我们需要进行二分查找

我们定义某个序列分为的两个子序列元素之和分别为A,B

如果A=B,那么这个序列是我们要找的子序列,但是我们需要进行拆分处理

可以将这个序列分为左右两个子序列,L和R

我们从L中挑选一些数作和得到LA,LB

从R中得到RA,RB

显然LA+RA=LB+RB

由于RA和RB LA和LB总是一起的,所以我们需要变一下形,得到LA-LB=RB-RA

这样我们就可以分别处理了

但是,还有一个问题,如果生成子序列以及如何查重

单单生成子序列不难,但是查重很费力,如果只用vector的话,查重需要遍历

所以我们需要引入map和bitset两个容器,前者负责查找和记录,后者是前者的底层容器

代码如下:

#include<iostream>
#include<vector>
#include<unordered_map>
#include<bitset>
using namespace std;
int n;
vector<int>cow;
unordered_map<int, vector<bitset<20>>>left_map;
int Count = 0;
bitset<1048576>visited;

void Left(int idx,bitset<20>mask,int sumA,int sumB) {
	if (idx == n / 2) {
		int diff = sumA - sumB;
		left_map[diff].push_back(mask);
		return;
	}

	Left(idx + 1, mask, sumA, sumB);

	mask.set(idx);

	Left(idx + 1, mask, sumA + cow[idx], sumB);

	Left(idx + 1, mask, sumA, sumB + cow[idx]);
}

void Right(int idx,bitset<20>mask,int sumA,int sumB) {
	if (idx == n) {
		int diff = sumB - sumA;
		if (left_map.find(diff) != left_map.end()) {
			for (bitset<20> it : left_map[diff]) {
				bitset<20>full_mask = it | mask;
				if (full_mask.none()) continue;

				int value = (int)full_mask.to_ulong();
				if (!visited[value]) {
					visited[value] = 1;
					Count++;
				}
			}
		}
		return;
	}

	Right(idx + 1, mask, sumA, sumB);

	mask.set(idx);
	Right(idx + 1, mask, sumA + cow[idx], sumB);

	Right(idx + 1, mask, sumA, sumB + cow[idx]);
}

int main() {
	cin >> n;
	cow.resize(n);
	for (int i = 0;i < n;i++) {
		cin >> cow[i];
	}
	bitset<20>emp;
	Left(0, emp, 0, 0);

	Right(n / 2, emp, 0, 0);
	
	cout << Count;
}

时间复杂度:O(3^(n/2))

空间复杂度:O(3^(n/2))