题目描述：
给定一个长度为 $ n $ 的数组，删除若干个数，使得该数组可以分为两个和不相等的子序列，输出删除数的个数和下标
数据范围：
$ 2\le n \le 100, 1\le a_i \le 2000 $
题解：
首先可以发现 $ \text{sum} $ 为奇数时，不用删就行。当 $ \text{sum} $ 是偶数时，需要判断一下能否分成两个相等的子序列。
判断可以使用 $ 0-1 $ 背包，使用 $ \frac{\text{sum}}{2} $ 的容量得到的最大值是否为 $ \frac{\text{sum}}{2} $ 即可。如果可以分，那么看看里面有没有奇数，删掉奇数即可。如果全部是偶数，那么可以想象已经分成了两个子序列，且里面全是偶数。不难想到，我如果全约去最大公约数对答案没有影响。全约去最大公约数（肯定出现了奇数，因为如果全是偶数可以继续约），删掉里面的奇数即可。
因为只需要记录一个容量的背包能不能装满，因此只需要记录 $ 0,1 $ 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
| int dp[maxn * 2000];
bool check()
{
dp[0] = 1;
for (int i = 1; i <= n; i++)
{
for (int j = sum / 2; j >= a[i]; j--)
{
dp[j] |= dp[j - a[i]];
}
}
return dp[sum / 2];
}
|
注意观察内层循环，内层循环相当于把原 $ \text{dp} $ 数组中的元素全部左移，并且或上原来的。因此可以考虑使用 $ \text{bitset} $ 实现
1
2
3
4
5
6
7
8
9
10
| bitset<maxn * 2000> dp;
bool check()
{
dp.set(0);
for (int i = 1; i <= n; i++)
{
dp |= (dp << a[i]);
}
return dp[sum / 2];
}
|
二者运行时间差不多， $ \text{bitset} $ 空间更优
代码：
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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e2 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn], sum;
int gcd;
bitset<maxn * 2000> dp;
bool check()
{
dp.set(0);
for (int i = 1; i <= n; i++)
{
dp |= (dp << a[i]);
}
return dp[sum / 2];
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
read(n);
bool flag = false;
int index = -1;
for (int i = 1; i <= n; i++)
{
read(a[i]);
sum += a[i];
if (a[i] & 1)
flag = true, index = i;
if (i == 1)
gcd = a[i];
else
{
gcd = __gcd(gcd, a[i]);
}
}
if (sum & 1)
{
printf("0\n");
}
else
{
if (check())
{
if (flag)
{
printf("1\n%d\n", index);
}
else
{
for (int i = 1; i <= n; i++)
{
a[i] /= gcd;
if (a[i] & 1)
{
index = i;
break;
}
}
printf("1\n%d\n", index);
}
}
else
{
printf("0\n");
}
}
return 0;
}
|