CF1928D Lonely Mountain Dungeons 题解

· · 题解

这道题送我上紫名。

似乎大部分人的做法都是二分、三分。这里提供一个组合数学 + 差分的赛时做法。

首先观察到每个族群互相独立，又因为 \sum c_i\le 2\times 10^5，这启发我们对于每个族群分别求解答案最后合并。

对于一个有 c 人族群，考虑将其分成 x 个队伍是能获得的最大价值。根据初中的简单不等式知识，显然要尽量将其均分才能产生最大价值，具体地，将其分为 x_1=c\bmod x 个有 p_1=\left\lceil\dfrac{x}{c}\right\rceil 人的队伍和 x_2=x-c\bmod x 个有 p_2=\left\lfloor\dfrac{x}{c}\right\rfloor 的队伍。运用简单组合数学知识，能得出产生的价值为同一种小队之间的价值 \dfrac{p_1^2bx_1(x_1-1)}{2}+\dfrac{p_2^2bx_2(x_2-1)}{2} 与不同种小队之间产生的价值 p_1p_2bx_1x_2 之和。于是对于每个 x(1\le x\le c_i) 分别计算即可。

最后统计答案的时候，如果枚举到的队伍数比前面某个族群的人数 c_i 还大，那么它的贡献应该为队伍为 c_i 时的贡献。赛时暴力维护 T 了一发后直接拍个线段树上去，赛后发现可以用差分数组更为简单的维护。于是时间复杂度 O(\sum c_i)，可以通过此题。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
int C2(int x){
  return x*(x-1)>>1;
}
main(){
  ios::sync_with_stdio(false);
  int t; cin>>t;
  while(t--){
    int n,b,m=1,x; cin>>n>>b>>x;
    vector<int> c(n);
    for(auto &i:c)cin>>i,m=max(m,i);
    vector<int> d(m+1);
    auto upd=[&](int l,int r,int x){
      d[l]+=x; if(r<m)d[r+1]-=x;
    };
    for(int i=0;i<n;i++){
      vector<int> s(c[i]+1);
      for(int j=1;j<=c[i];j++){
        int y=c[i]/j,x1=c[i]%j,x2=j-x1;
        s[j]=(y+1)*(y+1)*b*C2(x1)+y*y*b*C2(x2)+y*(y+1)*b*x1*x2;
        upd(j,j,s[j]);
      }
      if(c[i]+1<=m)upd(c[i]+1,m,s[c[i]]);
    }
    int w=0;
    for(int i=1;i<=m;i++)
      w=max(w,(d[i]+=d[i-1])-(i-1)*x);
    cout<<w<<'\n';
  }
  return 0;
}