首页 > 代码库 > Ladies' Shop
Ladies' Shop
题意:
有 $n$ 个包,设计最少的物品体积(可重集),使得
1. 对于任意一个总体积不超过给定 $m$ 的物体集合有其体积和 恰好等于一个包的容量。
2.对于每一个包,存在一个物品集合能恰好装满它。
解法:
考虑对于包的容量集合建立多项式 $A(x)$
注意到显然答案中的物品体积取自 $n$ 个包的容量。
那么根据题意有 条件2 <-> [$A(x)$中系数i为零 -> $A^2(x)$ 中系数i为零]
proof : 在只考虑系数是否为零的合法情况下,$A^k(x)$ 随着 $k$ 的增大而变小。
从而有取出 $A^2$ 相对 $A$ 所有丢失的项作为答案即可。
#include <bits/stdc++.h> #define PI acos(-1) const int N = 1000010; using namespace std; struct EX { double real,i; EX operator+(const EX tmp)const{return (EX){real+tmp.real, i+tmp.i};}; EX operator-(const EX tmp)const{return (EX){real-tmp.real, i-tmp.i};}; EX operator*(const EX tmp)const{return (EX){real*tmp.real - i*tmp.i, real*tmp.i + i*tmp.real};}; }; int R[N<<2]; void DFT(EX a[],int n,int tp_k) { for(int i=0;i<n;i++) if(i<R[i]) swap(a[i],a[R[i]]); for(int d=1;d<n;d<<=1) { EX wn = (EX){cos(PI/d), sin(PI/d)*tp_k}; for(int i=0;i<n;i += (d<<1)) { EX wt = (EX){1,0}; for(int k=0;k<d;k++, wt = wt*wn) { EX A0 = a[i+k], A1 = wt * a[i+k+d]; a[i+k] = A0+A1; a[i+k+d] = A0-A1; } } } if(tp_k==-1) for(int i=0;i<n;i++) a[i] = (EX){a[i].real/n, a[i].i/n}; } int n,m,a[N],b[N],ans[N]; EX A[N<<2]; bool v[N],flag[N]; bitset<N> f; int main() { scanf("%d%d",&n,&m); m++; for(int i=1;i<=n;i++) scanf("%d",&a[i]), v[a[i]]=1; int L = 0,tot; while((1<<L)<m+m) L++; tot = (1<<L); for(int i=1;i<tot;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1)); for(int i=1;i<=n;i++) A[a[i]] = (EX){1,0}; DFT(A,tot,1); for(int i=0;i<tot;i++) A[i] = A[i]*A[i]; DFT(A,tot,-1); bool ansv = 1; int t = 0; for(int i=0;i<m;i++) { if(A[i].real>0.5 && !v[i]) ansv = 0; else if(v[i] && A[i].real<0.5) b[++t] = i; } if(!ansv) puts("NO"); else { puts("YES"); printf("%d\n",t); for(int i=1;i<=t;i++) printf("%d ",b[i]); printf("\n"); } return 0; }
Ladies' Shop
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。