题解：P17142 [NOI 2026] 布丁（暂无数据）

· · 题解

写一个官解没有的随机化做法。

我们问一个已经排好序的序列 a，设 a_p\le w \le a_{p+1}，那么最后会返回 \sum_i \gcd(a_i, a_{i+1})+\gcd(a_p, w)+\gcd(a_{p+1}, w)-\gcd(a_p, a_{p+1})。欸那我们一方面可以让 \gcd(a_i, a_{i+1}) 尽可能不一样，另一方面要尽可能让 \gcd(a_i, w) 大。

我们发现最大质因子 \le X(X 是一个非常小的常数) 的数构成的集合就很能满足上面的要求。

具体地，我们每次随机从满足上面的序列中随机几个，维护目前可能的答案集合，挑选信息熵最大的进行询问即可。

思路非常简单，这个做法写出来的代码不经过任何调参即可获得五十多分，经过一些调参可获得 90 到 95 分，再经过一些比较变态的调参和细节优化即可获得满分。

下面放出代码，已在 qoj 通过。



#include<bits/stdc++.h>
#include"pudding.h"
#define rep(i, j, k) for(int i=(j); i<=(k); ++i)
#define per(i, j, k) for(int i=(j); i>=(k); --i)
#define siz(x) (int)x.size()
using namespace std;
using vec=vector<int>;
vec&operator+=(vec&a,int x){return a.emplace_back(x), a;}
vec operator+(vec a, int x){return a+=x;}
vec&operator+=(vec&a,vec b){for(auto x:b) a+=x; return a;}
vec operator+(vec a, vec b){return a+=b;}
const int N=6003, V=3000, M=1e6+5;
int tot, dep[N], sum[N];
vec q[N], d[N];
map<int, int> son[N];
vector<vec> pq[10];

int sd=311153493;

mt19937 rnd(sd);
int ri(int l, int r){return uniform_int_distribution<int>(l, r)(rnd);}

int len[3]={10, 10, 8};
int cnt[3]={(int)(1e4), (int)(2e4), (int)(2e4)};

int gcd(int x, int y){
  int zx=__builtin_ctz(x), zy=__builtin_ctz(y), z=min(zx, zy);
  x>>=zx, y>>=zy;
  while(x!=y){
    if(x<y) swap(x, y);
    x-=y;
    x>>=__builtin_ctz(x);
  }
  return x<<z;
}

int calc(vec d){
  per(i, siz(d)-2, 0) 
    if(d[i]>d[i+1]) swap(d[i], d[i+1]);
    else break;
  int w=0;
  rep(i, 0, siz(d)-2)
    w+=gcd(d[i], d[i+1]);
  return w;
}

int calc(const vec &q, const vec &d){
  int mx=1;
  static int vis[M], t, cnt[M];
  ++t;
  int w=0;
  rep(i, 0, siz(q)-2) w+=gcd(q[i], q[i+1]);
  int p=0;
  for(auto x:d){
    int v=w;
    if(x<q.front()) v+=gcd(x, q.front());
    else if(x>q.back()) v+=gcd(x, q.back());
    else{
      while(q[p+1]<x) ++p;
      v+=gcd(q[p], x)+gcd(q[p+1], x)-gcd(q[p], q[p+1]);
    }
    if(vis[v]!=t) vis[v]=t, cnt[v]=1;
    else ++cnt[v], mx=max(mx, cnt[v]);
  } 
  return mx;
}

void init(int c, int t){
  tot=1;
  if(c==1){
    rep(i, 1, 35) d[1]+=i;
  } 
  else if(c==2){
    auto prime=[&](int x)->bool {
      for(int i=2; i*i<=x; i++) if(x%i==0) return 0;
      return 1;
    };
    rep(i, 1, V) if(prime(i)) d[1]+=i; 
  }
  else{
    rep(i, 1, V) d[1]+=i;
  }
  vec pr{2, 3, 5, 7, 11, 13};
  vec num;
  auto ck=[&](int x)->bool {
    for(auto p:pr) while(x%p==0) x/=p;
    return x==1;
  };
  rep(i, 1, 4500) if(ck(i)) num+=i;
  rep(u, 1, tot) if(siz(d[u])>1){
    int best=1e9;
    int Z=dep[u];
    if(dep[u]==3 || siz(d[u])<=len[Z]){
      q[u]=d[u];
    } 
    else{
      for(int i=0; i<=cnt[Z] || best>=siz(d[u]); i++){
        vec z;
        if(i<pq[Z].size()){
          z=pq[Z][i];
        }
        else if(i<=cnt[Z]/2){
          rep(i, 1, len[Z]) z+=num[ri(0, siz(num)-1)];
          sort(z.begin(), z.end());
        } else{
          z=q[u];
          rep(_, 1, 5) z[ri(0, siz(z)-1)]=num[ri(0, siz(num)-1)];
          sort(z.begin(), z.end());
        }
        int tmp=calc(z, d[u]);
        if(tmp<best){
          best=tmp;
          q[u]=z;
        }
      }
      unordered_set<int> s;
      rep(i, 0, siz(q[u])-2)
        s.emplace(gcd(q[u][i], q[u][i+1]));
    }
    sum[u]+=siz(q[u]);
    pq[Z].emplace_back(q[u]);
    for(auto x:d[u]){
      int tmp=calc(q[u]+x);
      int v;
      if(son[u].count(tmp)) v=son[u][tmp];
      else son[u][tmp]=v=++tot, dep[v]=dep[u]+1, sum[v]=sum[u];
      d[v]+=x;
    }
  }
}

int find_tastiness(int c, int m){
  int u=1;
  while(siz(d[u])>1){
    int z=query_tastiness(q[u]);
    assert(son[u].count(z));
    u=son[u][z];
  }
  return d[u][0];
}