社区讨论

如果这个题没有m>=n-2的限制……

DDefy_HeavenS
P6775[NOI2020] 制作菜品参与者 1已保存回复 2

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
2 条
当前快照
1 份
快照标识符
@mlgxy2dz
此快照首次捕获于
2026/02/11 02:35
4 周前
此快照最后确认于
2026/02/11 02:35
4 周前
查看原帖
能做的最优复杂度多少？
我纯口糊了个做法，不知道对不对。
首先，若 m<n2m<\frac{n}{2} 则一定无解。
对于 n2≤m<n−2\frac{n}{2}\le m<n-2 的情况，假设 m=n−xm=n-x。
就是要拆成 xx 个 SS 满足 ∑i∈Sdi=(∣S∣−1)k\sum_{i\in S} d_i=(|S|-1)k。
朴素的，按 m=n−2m=n-2 的方法拆出来一个 SS，剩下的就是 m=n−x+1m=n-x+1 的情况。拆 x−1x-1 次即可。
但这样是 O(n3kw)\mathcal{O}(\frac{n^3k}{w}) 的。
如果拆完第一次，拆下一次时，不同“朴素的”一样再做一遍背包，而是再利用已经求出的背包结果。
下面是我 m=n−2m=n-2 的代码。
CPP
  dp[0].reset();
  dp[0][n*k]=1;
  for(int i=1;i<=n;i++){
    if(d[i]-k>=0){
      dp[i]=dp[i-1]|(dp[i-1]<<d[i]-k);
    }else{
      dp[i]=dp[i-1]|(dp[i-1]>>k-d[i]);
    }
  }
  if(!dp[n][n*k-k]){
    cout<<"-1\n";
    return;
  }
  set<PII>st1,st2;
  for(int i=n,val=n*k-k;i>=1;i--){    //拆第一次，由于m=n-2，所以只拆这一次
    if(dp[i-1][val-(d[i]-k)]){
      val-=d[i]-k;
      st1.insert(mkp(d[i],i));    //一个m=n-1的集合
    }else{
      st2.insert(mkp(d[i],i));    //其他的，由于m=n-2，所以亦满足m=n-1
    }
  }
  work(st1),work(st2);    //处理m=n-1的
拆第一次时，是从 −k-k 出发往前推（代码中离散化成 n∗k−kn*k-k 了），从而拆出一个 m=n−1m=n-1 的集合 SS。
拆第二次时，若从 −2k-2k 出发往前推，是不是能拆出一个 m=n−2m=n-2 的集合 S′S'？
若使 S′⊂SS' \subset S，那么 S−S′S-S' 是不是就是与 SS 不相交的另外一个 m=n−1m=n-1 的集合了？补集咋打啊……
这个不用每次都跑一边背包，复杂度是 O(n2kw+n2log⁡n)\mathcal{O}(\frac{n^2k}{w}+n^2\log n) 的？其中拆 x−1x-1 次 O(n)\mathcal{O}(n)，拆一次 O(nlog⁡n)\mathcal{O}(n\log n)。

回复

共 2 条回复，欢迎继续交流。

正在加载回复...