XCPC Notes

Appearance

发布时间：2023-08-30

背包问题 ​

多重背包 ​

单调队列优化 复杂度：O（N^2） ​

看f[j]的转移 从 f[j−v]+w,f[j−2⋅v]+2⋅w,f[j−3⋅v]+3⋅wf[j-v]+w,f[j-2\cdot v]+2\cdot w,f[j-3\cdot v]+3\cdot w .......中的最大值转移
j体积都会与相同的模数转移过来，考虑枚举从0~v-1的模数，体积每次加v，不同的模数转移互不影响

cpp
const int M=200010;
int n,m;
int f[M],g[M],q[M];
void solve(){
	cin>>n>>m;//物品组数n,体积m
	for(int i=1;i<=n;i++){
		int c,w,s;
		cin>>c>>w>>s;//物品的体积，价值，个数
		memcpy(g,f,sizeof(f));
		for(int j=0;j<c;j++){
			int hh=0,tt=-1;
			for(int k=j;k<=m;k+=c){
				f[k]=g[k];
				if(hh<=tt&&k-c*s>q[hh])hh++;//当前队列里的个数为s个，需要弹出一个
				if(hh<=tt)f[k]=max(f[k],g[q[hh]]+(k-q[hh])/c*w);//从q[hh]到需要加上多少个w
				while(hh<=tt&&g[q[tt]]-(q[tt]-j)/c*w<=g[k]-(k-j)/c*w)tt--;//维护q[tt]>=k
				q[++tt]=k;
			}
  		}
	}
	cout<<f[m]<<'\n';
}

带负权的背包问题 ​

P2340 [USACO03FALL] Cow Exhibition G ​

题意：
给定n头牛(n<=400)，每头牛有智商和情商(-1000<=x<=1000)，求出智商与情商之和最大，且智商和情商之和都不能小于0
思路：
01背包问题，但是容量可能为负，因此需要偏移
建二维数组会爆空间
因此每次转移若大于等于0则像普通01背包一样从后往前转移，小于0则从前往后转移
初始化 dpshift=0dp_{shift}=0,其他负无穷
答案为maxi=1N(dpi+i−shift)max_{i=1}^N(dp_i+i-shift)

cpp
int dp[N*2],a[410],b[410],n;
int shift=400000;
void solve(){
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++){
        cin>>a[i]>>b[i];
        if(a[i]>0)sum+=a[i];
    }
    sum+=shift;
    memset(dp,-0x3f,sizeof dp);
    dp[shift]=0;
    for(int i=1;i<=n;i++){
        if(a[i]>=0)for(int j=sum;j>=a[i];j--)dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
        else for(int j=0;j<=sum+a[i];j++)dp[j]=max(dp[j],dp[j-a[i]]+b[i]);
    }
    int ans=0;
    for(int i=shift;i<=sum;i++)if(dp[i]>=0)ans=max(ans,dp[i]+i-shift);
    cout<<ans<<"\n";
}

完全背包 ​

两重枚举的顺序问题 ​

  • 如果先枚举值，再枚举容量，此时方案数与顺序无关，即选[1,2,1],[1,1,2][1,2,1],[1,1,2] 等价
  • 反过来，则此时与顺序有关，[1,1,2],[1,2,1][1,1,2],[1,2,1] 为两种方案

bitset优化01存在性背包 ​

  • 使用普通01背包的复杂度为:O(nm)，优化后的复杂度为：O(nm/w)，w=32

P9509 『STA - R3』Aulvwc ​

题意：
问一个序列是否可以分成多个部分(不需要连续，只取下标)，这些部分平均数相等
思路：

  • 平均值一定为整个序列的平均值
  • 假设总和为sum，那么就是求是否能组成sum/2
  • 明显是背包问题，复杂度n*sum，会超时
  • 使用bitset优化，复杂度变成n*sum/32，仍然会超时
  • 发现只会在sum/2附近，因此值域可以缩小一半，变成n*sum/64
  • 值域缩小一半的方法：将所有a减去平均数，然后问题转变成是否可以组成0
  • 正数负数都维护一个bitset
  • 最后两个相与，如果1的个数大于2那么就可以组成(因为要排除0和最大最小值)
cpp
bitset<M> f,g;
int a[N],n;
void solve(){
    cin>>n;
    int sum=0;
    for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
    if(sum%n!=0){
        cout<<"No\n";
        return;
    }
    f.reset();
    g.reset();
    f.set(0,1);
    g.set(0,1);
    sum/=n;
    for(int i=1;i<=n;i++){
        a[i]-=sum;
        if(a[i]==0){
            cout<<"Yes\n";
            return;
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i]>0)f|=(f<<a[i]);
        else g|=(g<<-a[i]);
    }
    f&=g;
    if(f.count()>2)cout<<"Yes\n";
    else cout<<"No\n";
}

Wenwei Lin · 2022 — 2025