题解 CF1516C

江户川·萝卜 · 2021-04-25 22:05:08 · 题解

容易发现一个结论：数列之和为奇则原数列不是 good array。

则先判断一下原数列之和是否为奇。

之后再用背包判断一下原数列是不是 good array。

那如果原数列之和是偶呢？那好办，减掉一个奇数就行了！

如果原数列各元素全是偶呢？

容易发现，对数列同除以一个数不影响结果。

所以可以对原数列不断除以2，直到出现奇数为止，减掉一个奇数就可以。

具体写代码时，我们可以统计每个数含有2的几次幂，输出最小的那个数的位置即可。

#include<iostream>
#include<cstdio>
using namespace std;
int a[105];
bool f[200005];
int main(){
    int n,sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),sum+=a[i];
    if(sum&1){
        puts("0");
        return 0;
    }
    sum/=2;
    f[0]=1;
    for(int i=1;i<=n;i++)
        for(int j=sum;j>=a[i];j--)
            f[j]|=f[j-a[i]];
    if(!f[sum]){
        puts("0");
        return 0;
    }
    int minc=1e5,minp=0;
    for(int i=1;i<=n;i++){
        int x=a[i],cnt=0;
        while(!(x&1)){
            x>>=1;
            cnt++;
        }
        if(cnt<minc) minc=cnt,minp=i;
    }
    printf("1\n%d",minp);
    return 0;
}