看了官方題解之后，自己寫一遍加深下印象，
2.cf Baby Ehab Partitions Again
傳送門 ：https://codeforces.com/contest/1516/problem/C
大意：給你一個長度為n 的序列 a,要求洗掉最少的元素個數，使得任意分成兩組，這兩組各自的和都不相等（可以不洗掉），輸出洗掉的最少的元素個數，和要洗掉的下標，n不超過100
思維好題，解鎖背包新用法
思路：先來想想什么情況下可以不洗掉？ 很容易想到，如果原序列和為奇數的話，任意分兩組必定都是不相等的兩組，但和為偶數的時候的呢？因為和 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;
}
總結（（1）可以用01背包模型來判斷序列能否湊出和為某個數的問題（2）全是偶數時除以2的思想真的巧妙）
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/279290.html
標籤：其他