题解：CF1516C Baby Ehab Partitions Again

· · 题解

首先我们能感知到，当序列总和为奇数时，不可行。

其次我们发现如果全是偶数可以对他全部除 2 直到至少有一个奇数。

最后我们发现如果和是偶数可以删掉一个奇数使和变成奇数。

我们怎么判断一个序列可不可行呢？尝试用里面的数凑出 \frac{sum}2 即可，用 bitset 做这个即可。

#include<bits/stdc++.h>

#define pii pair<int,int> 
#define pll pair<long long,long long> 
#define ll long long
#define i128 __int128

#define mem(a,b) memset((a),(b),sizeof(a))
#define m0(a) memset((a),0,sizeof(a))
#define m1(a) memset(a,-1,sizeof(a))
#define lb(x) ((x)&-(x))
#define lc(x) ((x)<<1)
#define rc(x) (((x)<<1)|1)
#define pb(G,x) (G).push_back((x))
#define For(a,b,c) for(int a=(b);a<=(c);a++)
#define Rep(a,b,c) for(int a=(b);a>=(c);a--)
#define in1(a) a=read()
#define in2(a,b) a=read(), b=read()
#define in3(a,b,c) a=read(), b=read(), c=read()
#define in4(a,b,c,d) a=read(), b=read(), c=read(), d=read()
#define fst first 
#define scd second 
#define dbg puts("IAKIOI")

using namespace std;

int read() {
    int x=0,f=1; char c=getchar();
    for(;c<'0'||c>'9';c=getchar()) f=(c=='-'?-1:1); 
    for(;c<='9'&&c>='0';c=getchar()) x=(x<<1)+(x<<3)+(c^48);
    return x*f;
}
void write(int x) { if(x>=10) write(x/10); putchar('0'+x%10); }

const int mod = 998244353;
int qpo(int a,int b) {int res=1; for(;b;b>>=1,a=(a*a)%mod) if(b&1) res=res*a%mod; return res; }
int inv(int a) {return qpo(a,mod-2); }

const int N = 200050;

int n,a[N];
bitset<200050> vis;

bool check() {
    For(i,1,n) if(a[i]%2==1) return 0;
    return 1;
}

void work() {
    in1(n); int sum=0; vis[0]=1;
    For(i,1,n) in1(a[i]),sum+=a[i];
    while(check()) {
        For(i,1,n) a[i]/=2; sum/=2;
    }
    For(i,1,n) vis|=(vis<<a[i]);
    if(sum%2==0&&vis[sum/2]==1) {
        For(i,1,n) if(a[i]%2==1) {
            return cout<<1<<'\n'<<i<<'\n',void();
        }       
    }

    cout<<0<<'\n';
}

signed main() {
//  freopen("data.in","r",stdin);
//  freopen("myans.out","w",stdout);
//  ios::sync_with_stdio(false); 
//  cin.tie(0); cout.tie(0);
    double stt=clock();
    int _=1;
//  _=read();
//  cin>>_;
    For(i,1,_) {
        work();
    }
    cerr<<"\nTotal Time is:"<<(clock()-stt)*1.0/1000<<" second(s)."<<'\n';
    return 0;
}