题意

给定一个长度为$n(2 \leq n \leq 100)$的数列，数列内元素称为$a_i(1 \leq a_i \leq 2000)$。

现要求你在这个数列中删除最少的元素，使得对于任何一种划分整个数列为两个子序列的方案，都不能使划分的两个子序列的元素和相等。

思路

开始的时候完全找不到突破口。

考虑从最小的情况出发，只有两个数时，只要判断是否相等就可以了。

如果添加第三个数，就要判断新加的数字是否能和原来的数字构成子序列，使得和相等。

这一步我开始想的是$O(2^n)$的子集枚举，后面想了一下，$01$背包枚举是否能生成$sum/2$，$O(nm)$就可以实现。

但是怎么样才能够使得删除的数最少？这个问题一直没能解决。

后学习题解，才发现其实最多只需要删除一个数字！

我们可以对全部元素求和，得到$sum$。然后，我们只关心$sum$二进制下的最后一位。

如果$sum$二进制下的最后一位值为$1$，即$sum$为奇数，则一定不存在划分两个子序列和相等的情况。因为最后一位值只能够被划分到某一子序列里。这是个充分条件。

也就是说，如果我们得到$sum$本来就是奇数，我们可以不做任何修改，直接输出$0$。

否则，我们要考虑在$[a_n]$中删除一个元素，使得$sum$变为奇数，这样就可以使得任何划分方案都不能得到和相等的子序列。

但是，我们是否能够在任意删除一个元素的操作中，使得$sum$变为奇数呢？

答案是不能的，如果这个数列均由偶数组成，比如$[6,6,6,6]$，我们就不能通过某一操作使得$sum$变为奇数。

那么，我们能不能通过某种办法，使得这种情况转化为数列中存在奇数的情况，便于我们快速解决呢？

可以。我们可以设当前数列$[a_i]$都是由另一数列$[b_i]$乘上某一常数$c$得到的，即$a_i=c*b_i$。

这样，我们把问题转化为对数列$[b_i]$的划分。

为什么这样是可行的呢？我们可以设对于$[b_i]$任一划分方式产生的集合元素和为$G$。

那么，在原数列$[a_i]$使用同样划分方式划分得到的元素和就为$c*G$，对相等的判断是不影响的。

现在有另一个问题，我们该怎么去找到$c$，使得$[b_i]$中出现奇数呢？

我们只需要不断对$a_i$的元素除$2$，当发现出现至少一个奇数时，停止相除就可以了，此时$c=2^k$。

另外，有个更加简便的方法，我们只需要对$a[i]$除以整个数列的最大公约数，就一定可以得到存在至少一个奇数的数列。

由此，这道题得以解决了…吗？

不，在上面数列中元素皆为偶数的情况中，解题思路是基于一定需要删除某一元素来做的。

实际上，元素皆为偶数，$sum$为偶数，同样存在情况不需要删除，如$[6,6,6]$。

因此，我们在最开始的时候就要进行一次$01$背包判断，看看能不能凑出$sum/2$。

所以，在上面我才提到，那是个充分条件，而不是充要条件。

到此，这道题正式结束。

（不得不说这道题非常漂亮！）

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
#define maxn 200005
using namespace std;
int n, sum, g;
int a[maxn], b[maxn], can[maxn];
int main(void)
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        sum += a[i];
        g == 0 ? g = a[i] : g = __gcd(g, a[i]);
    }
    if(sum & 1)
    {
        printf("0\n");
        return 0;
    }
    can[0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = sum; j >= a[i]; j--)
            can[j] |= can[j - a[i]];
    if(!can[sum / 2])
    {
        printf("0\n");
        return 0;
    }
    int flag = -1;
    for(int i = 1; i <= n; i++)
    {
        b[i] = a[i] / g;
        if(b[i] & 1)
        {
            flag = i;
            break;
        }
    }
    printf("%d\n%d\n", 1, flag);
    return 0;
}

End