CF Round #717 (Div. 2) 1516C Baby Ehab Partitions Again

知识点：思维、01背包

题目链接

题意

求给定序列最少删哪些数使得不存在两对立的子序列（不连续）使子序列和相等。

思路

本题关键在于证明对所有元素整除二的操作产生的新序列与原序列性质完全相似。
其次在于设计寻找和相等对立子序列的方法。
本题所涉及只有求和和分组操作，所以第一行所述成立。
第二行的方法使用dfs会超时，注意到$a_i<2e3$，提示将值域当下标，由此联想到dp，为01背包的变形。对一个子序列，要求经过前n个数选或不选后的和是否等于原序列和的一半，就要先求得经过前i个数选或不选后的和是否等于j，设bool dp[i][j],i==n且j==原序列和的一半即为解。
判断完毕后，原序列和必为偶数（一个数乘二为偶数），移除一个奇数后必为奇数，此时无法分解为两个相等的数，故满足了题意。
若没有奇数，使用第一行的结论，必能构造出含奇数的序列（操作迭代必经过1），按照上一行所述即可。
总之，至多1次即可满足题意。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e2+10,M=N*2e3+10;

ll n;
ll arr[N];
bool dp[N][M];//dp[i][j]表示前i个数选和不选后是否恰好为j

//判断当前序列奇数的位置，不存在返回0（false）
ll judge()
{
   
    for(ll i=1; i<=n; i++)
        if(arr[i]&1) return i;
    return 0;
}

void solve()
{
   
    scanf("%lld",&n);
    for(ll i=1; i<=n; i++) scanf("%lld",&arr[i]);
    ll sum=0;//原序列和
    for(ll i=1; i<=n; i++) sum+=arr[i];
    if(sum&1)//为奇数说明无法分解，满足题意
    {
   
        puts("0");
        return;
    }
    sum/=2;//一个子序列的和
    dp[0][0]=true;//前0件为0必成立
    dp[1][arr[1]]=true;//大概不需要这句

    for(ll i=1; i<M; i++)
    {
   
        for(ll j=1; j<=n; j++)
        {
   
            dp[j][i]|=dp[j-1][i];
            if(i-arr[j]<0) continue;
            dp[j][i]|=dp[j-1][i-arr[j]];
        }
    }
    if(!dp[n][sum])
    {
   
        puts("0");
        return ;
    }
    while(judge()==false)//直到包含奇数退出循环
    {
   
        for(ll i=1; i<=n; i++)//除二操作
        {
   
            arr[i]/=2;
        }
    }
    printf("1\n%lld\n",judge());
}

int main()
{
   
    solve();
    return 0;
}