from NOIP2016模擬題36

Description

商店里有n種背包和m種物品，物品體積為1到m，背包容積<=m
給出n個(gè)背包的容積
現(xiàn)在要求出這樣一個(gè)物品集合，滿足：
1)對于任意一個(gè)背包，都能找到這樣一個(gè)物品的子集，使得這個(gè)子集中物品的體積和（每個(gè)物品可以使用多次）恰好等于背包的容積

2)對于每一個(gè)體積和小于等于m的物品子集（每個(gè)物品可以使用多次），都有一個(gè)背包容積恰好等于這個(gè)體積和

求滿足條件的最少的物品集合

Analysis

有解 \(\Leftrightarrow\) 物品集=背包體積集合 時(shí) 有解
然后我們要縮小集合
就是判斷一個(gè)數(shù)能不能被小于它的數(shù)背包dp出來
然而由于題目的特殊性質(zhì)
只用是否存在兩個(gè)小于它的數(shù)a,b滿足a+b等于它
我們可以用FFT
簡單證明：
若已經(jīng)求出有解
a,b,c,d在物品集中
則2a,3a.....都在物品集中
同理a+b,2a+b,4a+2b+3c,2a+4b+5c+d什么的都在集合中
集合中的數(shù)任意兩個(gè)相加即可表示任何數(shù)

證完了
回到一開始怎么知道物品集=背包集的情況是否滿足條件？
將物品集conv后看看是否出現(xiàn)新數(shù)
有就不滿足

Code

#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <cctype> #include <algorithm> using namespace std; const double pi=acos(-1.0); const int M=1000007; const int N=2097152;inline int rd(){int x=0;bool f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=0;for(;isdigit(c);c=getchar()) x=x*10+c-48;return f?x:-x; }int n,m; int rev[N]; struct CP{double x,i;CP(double xx=0.0,double ii=0.0){x=xx;i=ii;} }a[N]; CP operator +(CP x,CP y){return CP(x.x+y.x,x.i+y.i);} CP operator -(CP x,CP y){return CP(x.x-y.x,x.i-y.i);} CP operator *(CP x,CP y){return CP(x.x*y.x-x.i*y.i,x.i*y.x+x.x*y.i);}void FFT(CP *a,int fl){int i,j,k;CP W,Wn,u,v;for(i=0;i<N;i++) if(rev[i]<i) swap(a[i],a[rev[i]]);for(i=2;i<=N;i<<=1){Wn=CP(cos(2*pi/i),fl*sin(2*pi/i));for(j=0;j<N;j+=i){W=CP(1,0);for(k=j;k<j+i/2;k++,W=W*Wn){u=a[k];v=W*a[k+i/2];a[k]=u+v;a[k+i/2]=u-v;}}}if(fl==-1)for(i=0;i<N;i++) a[i].x=(a[i].x/N)+0.5; }int vis[M]; int ans=0;int main(){int i,j,k,x;n=rd(),m=rd();for(i=1;i<=n;i++){x=rd();vis[x]=1;a[x]=CP(1,0);}for(i=0;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)?(N>>1):0);FFT(a,1);for(i=0;i<N;i++) a[i]=a[i]*a[i];FFT(a,-1);ans=n;for(i=1;i<=m;i++)if(a[i].x>=1){ //注意現(xiàn)在是double if(!vis[i]){puts("NO");return 0;}ans--;}puts("YES");printf("%d\n",ans);for(i=1;i<=m;i++)if(vis[i]&&a[i].x<1){if(ans>1) printf("%d ",i);else printf("%d\n",i);ans--;}return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/acha/p/6366075.html

總結(jié)

以上是生活随笔為你收集整理的xsy 1836 - Shop的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。