C. Baby Ehab Partitions Again
[原题网址](Problem - C - Codeforces (Unofficial mirror site, accelerated for Chinese users))
题意: 给出n个数,要求删除尽可能少的数使得原序列不能分成和相同的数,给出任意一种删除方案即可。 2 ≤ n ≤ 100 , 1 ≤ a i ≤ 2000 2 \leq n \leq 100,1 \leq a_i \leq 2000 2≤n≤100,1≤ai≤2000
题解:
令 s u m = ∑ i = 1 n a i sum=\sum_{i=1}^{n}a_i sum=∑i=1nai
如果 s u m sum sum为奇数,显然不用删除任何元素。
否则:
01背包判断(见下文)是否能选出若干个数使得其和为 s u m 2 \frac{sum}{2} 2sum,如果不存在则不用删除,否则:
1.删除一个奇数,使得剩下的和为奇数即可,如果奇数不存在,那么可以把所有的数看成是若干个’2’组成的,于是同除以2,再找奇数,直到出现奇数为止。本质是找质因式分解后2的幂次最小的那个数。
2.将所有的数除以 d = g c d ( a 1 , a 2 , a 3 . . . a n ) d=gcd(a_1,a_2,a_3...a_n) d=gcd(a1,a2,a3...an),然后找到第一个奇数即可(必然有)。这种思维就是把d看做最小单位,找一个奇数,则剩下的数的和一定是这个最小单位的奇数倍,所以一定不能平分。
01背包判断:
令 V = s u m 2 V=\frac{sum}{2} V=2sum
将第 i i i个物品的体积与价值都看作 a i a_i ai,01背包求体积为V的背包最多能装下多少价值的物品,看答案与V是否相同即可判断。
简单证明:
由于背包体积是V,所以选出来的数的和一定小于等于V,而又因为要价值最大化,所以会尽可能的接近1,如果存在合法方案,那么最后的价值一定是V。
#include <bits/stdc++.h>
#define debug(x) cout<<#x"=" <<x<<'\n';
using ll=long long;
using namespace std;
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
template<typename T> void read(T &x)
{
x = 0;
char ch = getchar();
ll f = 1;
while(!isdigit(ch))
{
if(ch == '-')f*=-1;
ch=getchar();
}
while(isdigit(ch))
{
x = x*10+ch-48;
ch=getchar();
}
x*=f;
}
const int M=105;
int a[M];
int dp[2000*105];
int n;
bool work(int sum)
{
//debug(sum);
for(int i=1; i<=n; i++)
{
for(int j=sum; j>=1; j--)
{
dp[j]=max(dp[j],j>=a[i]?(dp[j-a[i]]+a[i]):0);
//printf("%d ",dp[i][j]);
}
//puts("");
}
return dp[sum]==sum;
}
int main()
{
read(n);
int sum=0;
int gcdd=0;
for(int i=1; i<=n; i++) read(a[i]),sum+=a[i],gcdd=gcd(gcdd,a[i]);
if(sum%2)
{
puts("0");
return 0;
}
if(work(sum/2))
{
for(int i=1; i<=n; i++)
{
if((a[i]/gcdd)&1)
{
puts("1");
printf("%d\n",i);
return 0;
}
}
}
else
{
puts("0");
}
return 0;
}