Codeforces Round #717 Baby Ehab Partitions Again - 数学+01背包

题意

给你一个长度为$n$的数组$a$。定义美的数组:如果这个数组分成两组,存在一种分法,使得两组的和相同。问:最少移除多少个数,使得这个数组不美。

题解

定义$sum=\sum_{i=1}^n a_i$。如果$sum$是一个奇数,那么显然不需要移除。

如果$sum$是偶数,那么我们跑一个容量为$\frac {sum}2$的01背包,如果不存在解,那么也不需要移除。

于是到此,原数组$a$,一定需要移除点什么。

首先,如果$a$中存在奇数,那么直接移除这个奇数,使得$sum$变成奇数。

如果不存在奇数,那就意味着$a$里面全是偶数咯。那么,在移除任何数之前,我们将整个数组除以2,仍然能沿用之前的分组方式使得两组和相等。

如果除以2之后出现了奇数,那么就移除这个奇数。如果除以2之后还是全都是偶数,那么就一直除,直到第一次出现奇数。

代码

Submission #113893840 - Codeforces
Codeforces. Programming competitions and contests, programming community
展示评论