[OOI2023] n 维巧克力问题 题解

· · 题解

其实是数论基础题。

考虑状态的设计：f_{i,P} 表示考虑了前 i 个元素，要求 \prod\limits_{j=i+1}^n b_j\ge P 的最大答案。由于 P 必然形如 \left\lceil\frac{k}{x}\right\rceil，根据整除分块的理论可能的 P 个数是 O(\sqrt{k}) 的——于是状态数变为 O(n\sqrt{k})，直接暴力枚举 b_i 转移时间复杂度为 O(n\sqrt{k}\max a_i)，可以获得 25 分。

发现对于某一些 b_i，\left\lceil\frac{P}{b_i}\right\rceil 的值是一样的，也就是说可以对于 [1,P] 内的值再套一层整除分块！这样的时间复杂度是 O\left(n\left(\sum\limits_{m=1}^{\sqrt{k}}\sqrt{m}+\sqrt{\left\lceil\frac{k}{m}\right\rceil}\right)\right)=O(nk^{\frac{3}{4}})，证明可以参考 杜教筛 - OI Wiki。于是本题得以解决。

实现时注意到 \left\lceil\frac{k}{x}\right\rceil=\left\lfloor\frac{k-1}{x}\right\rfloor+1，所以可以转换为 k-1 的下取整整除分块。这里注意特判 \left\lfloor\frac{k-1}{x}\right\rfloor=0 的情况，转移时单独提出来处理。

放代码：

#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  int n,k; cin>>n>>k,k--;
  vector<int> a(n),w;
  for(auto &i:a)cin>>i;
  for(int l=1,r;l<=k;l=r+1)
    w.emplace_back(k/l),r=k/(k/l);
  w.emplace_back(0); // 预处理第二维的可能值
  vector<int> p(k+1,-1);
  for(int i=0;i<w.size();i++)
    p[w[i]]=i; // 记一下位置方便转移时快速查找
  vector<double> f(w.size());
  f[0]=k+1;
  for(int x:a){
    vector<double> g(w.size());
    for(int i=0;i<w.size();i++)
      if(f[i]){
        for(int l=1,r;l<=w[i];l=r+1){
          int v=w[i]/l;
          g[p[v]]=max(g[p[v]],f[i]*(x/l)/x),r=w[i]/v;
        } // 整除分块进行转移
        g.back()=max(g.back(),f[i]*(x/(w[i]+1))/x);
        // 特判值为 0
      }
    f=move(g); // 使用滚动数组
  }
  cout<<fixed<<setprecision(11)<<f.back()<<endl;
  return 0;
}