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

叁歲伎倆 2023-01-15 15:29 121阅读 0赞

思维好题，解锁背包新用法  
思路：先来想想什么情况下可以不删除？ 很容易想到，如果原序列和为奇数的话，任意分两组必定都是不相等的两组。但和为偶数的时候的呢？因为和 s 是偶数，我们只需看其中一组能不能凑够是s/2就行了,不妨令m=s/2。接下来我们可以用01背包来判定。为什么呢？先让我们来想想01背包是用来干嘛的？ 在不超过背包容量，每种商品最多取一次的前提下可以取到商品的最大价值！！！将本题代入01背包：即背包容量为m,求不超过m的选择方案的最大值，因为每个商品 体积==价值，总体积不超过背包容量m,所以选择的方案中的最大价值<=m,所以就可以用01背包来判断能不能凑成，即该最大价值是否和m相等。如果不等，即最大的都不等了，那凑不出了，所以就不用删。反之就是能凑出来，接下来进行下一步。

因为和是偶数。如果序列有奇数的话，删除这个奇数的话，和就变成奇数了，就不能分成相等的两组了。

但如果没有奇数呢？那简单，你们都是偶数，那我把你们都除以2不过分吧，因为你们到时候是看分组后的和嘛，除以2之后对你们又没什么影响。还没有奇数怎么办，那我再出一下再除一下不过分吧…还没有？我… 得，您被别除了，给您个奇数行了吧…

完毕。

#include <bits/stdc++.h>
    #define pb push_back
    #define scf scanf
    #define prf printf
    #define cs cout<<"\n"
    #define cts cout<<"YES"<<"\n"
    #define ctn cout<<"NO"<<"\n"
    #define rep(i,bbb,eee) for(int i=bbb;i<=eee;i++)
    #define per(i,bbb,eee) for(int i=bbb;i>=eee;i--)
    #define mem(a,b) memset(a,b,sizeof(a))
    #define inf 0x3f3f3f3f
    #define _sy ios::sync_with_stdio(false);cin.tie(0)
    using namespace std;
    typedef long long LL;
    typedef unsigned long long ULL;
    typedef pair<int,int> PII;
    const int N=100010;
    int a[110];
    int n;
    int f[N];
    bool check()
    { 
    	int s=0;
    	rep(i,1,n)s+=a[i];
    	if(s%2)return true;
    	int m=s/2;
    	for(int i=0;i<n;i++)
        { 
            for(int j=m;j>=a[i];j -- )
                f[j] = max(f[j], f[j- a[i]] + a[i]);
        }
    	return f[m]!=m;
    
    }
    void find()
    { 
    	while(1)
    	{ 
    		rep(i,1,n)
    		{ 
    			if(a[i]%2)
    			{ 
    				cout<<1<<"\n"<<i<<"\n";
    				return ;
    			}
    			a[i]/=2;
    		}
    	}
    }
    int main()
    { 
    	_sy;
    	cin>>n;
    	rep(i,1,n)cin>>a[i];
    	if(check())cout<<0<<"\n";
    	else find();
    	return 0;
    }

原文链接：https://blog.csdn.net/m0\_51488693/article/details/116009313