Codeforces Round #717 (Div. 2) C.Baby Ehab Partitions Again 思维

题意

给定数组(a)，问去掉最少的元素使得不可以对剩余元素划分得到两个和相等的子序列

[2 leq n leq 100\ 1 leq a_i leq 2000 ]

分析

若原本的数组和是奇数，那么本来就不可能拆出和相等的子序列

若是偶数，那么只要去找到一个奇数就行了，这样剩下的和就会变成奇数

但是有可能出现全部都是偶数的情况，这个时候两边的和一定都是偶数，完全可以除以二，保持了等价

因此不妨干脆对所有数先除以一个gcd，这样就保证一定会有奇数了

于是对数组预处理后，用bitset跑一遍布尔背包，判断是0还是1，是1的话就找到数组中的那个奇数即可

代码

int main(){
	int n = rd();
	vector<int> v(n);
	for(int i = 0;i < n;i++)
		v[i] = rd();
	int g = v[0];
	for(auto it:v) 
		g = gcd(g,it);
	for(auto &it:v)
		it /= g;
	int tot = 0;
	for(auto it:v)
		tot += it;
	bitset<200005> st;
	st[0] = 1;
	for(int i = 0;i < n;i++)
		st |= (st << v[i]);
	if((tot & 1) || (!st[tot / 2])) {
		puts("0");
		return 0;
	}
	int pos = 0;
	while(v[pos] % 2 == 0) pos++;
	printf("1
%d",pos + 1);
}