[集训队互测 2025] 携春同行 题解

· · 题解

赛场上没调完狂砍 44 分，午睡结束后几下调到了 95 分，在进行神秘优化后终于得到满分，令人忍俊不禁。

提供一种非常简洁的做法。是题解发布时的 QOJ 最短解。

先尝试做 a_i 互不相同的部分分。考虑缩小问题规模，注意到菊花是个性质优良的东西，对于每个点 u 询问以 u 为根的菊花，此时的直径即为 a_u 加上其他元素中最大的两个。观察到仅有最大的三个值无法区分，其他的值都可以在得出全局第三大值之后推断得出。此时再询问一条链，即可得到 \sum a_i，解方程能够得到第三大值（记为 q），进而推出其他所有 <q 的元素的值。总共需要 n+1 次“离线操作”，符合题意。

问题在于目前无法区分谁是第三大值——特殊性质下的判断方法很多且与正解无关，在此略过。直接考虑没有特殊性质时的方法，发现此时与有特殊性质的唯一区别在于，可能有很多个元素的值 =q——要从所有可能的元素中找出两个不合法的。下文称可能 =q 的元素为备选元素，称 =q 的元素为合法元素。

考虑一种暴力地判断备选元素是否合法的方法：把需要被判断的元素拿出来，其他元素连成一条链，并且这条链满足头尾均为备选元素。再把这个元素对应的点和链的中点连边。这样如果这个元素 =q，最优的直径一定不会经过它，答案必为 \left(\sum a_i\right)-q（因为链中点两侧的链权值和一定都 >q，这个“分岔点”不会被选入直径）；否则答案一定不为该值。由于备选元素 \ge 3 个，故此时必然能找出两个没被选中的备选元素作为链头尾。这样就可以 n 次询问得出不合法元素的位置，能够获得 44 分。

尝试拓展这个方法，此时在中点上挂不止一个点，这样就能判断里头是否存在不合法的元素（如果 check x 个点，若均为合法元素，答案必为 \left(\sum a_i\right)-q\cdot x；若存在不合法元素，答案一定不为该值）。结合题目的限制，自然地就想到二分。

但是此时要保证至少有两个点挂在链的头尾，发现二分最多 check \left\lfloor\frac{n}{2}\right\rfloor 个点，于是 n 很小的时候直接暴力，n 大点时就做两次二分求出两个不合法元素。在线操作最多做 2\left\lceil\log_2n\right\rceil=18 次，可以通过。

放代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> query(const vector<vector<int> > &U,const vector<vector<int> > &V);
bool guess(const vector<int> &U,const vector<int> &V,ll x);
vector<int> haru(int n){
  vector<vector<int> > U(n+1),V(n+1);
  for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      if(i!=j)U[i].push_back(i),V[i].push_back(j); // 构造菊花
  for(int i=0;i<n-1;i++)
    U[n].push_back(i),V[n].push_back(i+1); // 构造链
  auto R=query(U,V);
  vector<ll> v(R.begin(),R.begin()+n);
  sort(v.begin(),v.end());
  ll t=v.back(),q=t-(accumulate(v.begin(),v.begin()+n-3,0ll)-(R[n]-t))/(n-3); // 解出 q 的值
  vector<int> a(n),p;
  for(int i=0;i<n;i++)
    if((a[i]=R[i]-t+q)==q)p.push_back(i); // 筛出备选元素
  auto check=[&](int l,int r){
    vector<bool> b(n);
    for(int i=l;i<=r;i++)
      b[p[i]]=true;
    int h=p[(l+p.size()-1)%p.size()],t=p[(r+1)%p.size()];
    vector<int> c={h},U,V;
    for(int i=0;i<n;i++)
      if(i!=h&&i!=t&&!b[i])c.push_back(i);
    c.push_back(t);
    for(int i=0;i+1<c.size();i++)
      U.push_back(c[i]),V.push_back(c[i+1]);
    for(int i=0;i<n;i++)
      if(b[i])U.push_back(c[c.size()>>1]),V.push_back(i);
    return !guess(U,V,R[n]-1ll*(r-l+1)*q);
  }; // 判断 p[l...r] 内是否有不合法元素
  if(p.size()<=18){
    for(int i=0;i<p.size();i++)
      if(check(i,i))a[p[i]]=-1;
    return a;
  } // 备选元素不多直接暴力
  auto f=[&](auto &&sf,int l,int r)->int{
    if(l>=r)return r;
    int m=l+r>>1;
    return check(l,m)?sf(sf,l,m):sf(sf,m+1,r);
  }; // 使用递归实现二分
  int x=f(f,0,p.size()-1),y=f(f,x+1,p.size()-1);
  return a[~x?p[x]:0]=a[~y?p[y]:0]=-1,a;
}