题解：P13553 [IOI 2025] 神话三峰 triples Part 2

· · 题解

前情提要

在 Part 1 中，我们将匹配根据 h 的关系分成了六种类型。其中有五种都是很好做的，第六种可以通过三元环计数来完成。

观察匹配形式，其实我们应该去尽可能构造第六种。因为前五种之所以简单是它们可以一推二，也就是三元组中确定了某一个可以推导到另一个，这是我们很不希望了，这意味着三元组的变化很小基本很固定，难以让其数量增多。

故应该从第六种入手，这个变化多。我们应该让三元环个数尽可能多。有一个很基础的想法就是我们用很少的点，然后造一堆连在它们之间的边，这样子三元组的个数就会很多。首先应该注意到点的个数不能太少，因为通过两个点之间的信息解二元一次方程可以唯一确定一组 (i,h_i)，也就是说不能有重边。

自己做这题的时候就止步于此，因为我觉得自己造点很考验技术，随机造点又不太靠谱的样子。于是就瞎输出了一些很小的序列的组合获得了 78 \rm pts。后来看了别人的代码，发现这种思路确实可行，而且正是随机！

具体来说我们随机取一些 [0,M] 之间的偶数（不要太多，防止点很多导致边比较分散，但也不能太少不然的话就无法填充 h 数组了），取偶数的目的是为了解方程一定有解。然后在选择偶数中枚举所有数对，通过解方程确实 (i,h_i)。肯定有一些 h_i 到最后也没有被覆盖，我们就统一赋值为 1。

使用在 Part 1 中写的计数函数进行计算，多次随机，取最大的一次输出即可。

#include<bits/stdc++.h>
#define pb emplace_back
#define fi first
#define se second
#define mp make_pair
using namespace std;
typedef long long ll;
typedef vector<int> vi;
const int maxn=4e5+10;
void cmax(int &x,int y){ x=x>y?x:y; }
void cmin(int &x,int y){ x=x<y?x:y; }
int h[maxn],from[maxn],deg[maxn],n; 
int p[maxn],rk[maxn],vis[maxn]; map<int,int> id;
vector<int> G[maxn],L[maxn],R[maxn]; 
pair<int,int> E[maxn];
bool cmp(int x,int y){ return deg[x]<deg[y]||(deg[x]==deg[y]&&x<y); }
ll count_triples(vi H){
    n=H.size(); ll ans=0;
    for(int i=1;i<=n;i++) h[i]=H[i-1];
    //(i,j,k)
    //Hi=max{Hi,Hj,Hk}
    for(int i=1;i<=n;i++){
        int k=i+h[i];
        if(k>n) continue;
        int j=i+h[k];
        if(j<k&&j+h[j]==k) ans++;
        if(k-h[k]!=j){
            j=k-h[k];
            if(i<j&&j-h[j]==i) ans++;
        }
    }
    //Hk=max{Hi,Hj,Hk}
    for(int k=1;k<=n;k++){
        int i=k-h[k];
        if(i<1) continue;
        int j=i+h[i];
        if(j<k&&j+h[j]==k) ans++;
        if(k-h[i]!=j){
            j=k-h[i];
            if(i<j&&j-h[j]==i) ans++;
        }
    }
    //Hj=max{Hi,Hj,Hk}
    for(int i=1;i<=n;i++){
        if(i+h[i]<=n) L[i+h[i]].pb(i);
        if(i-h[i]>=1) R[i-h[i]].pb(i);
    }
    for(int i=1;i<=n;i++){
        for(auto u:R[i]) vis[u]=1;
        for(auto u:L[i])
            if(u+h[i]<=n&&vis[u+h[i]]&&h[u+h[i]]!=h[u]) ans++;
        for(auto u:R[i]) vis[u]=0;
    }
    int tot=0;
    for(int i=1;i<=n;i++){
        int h1=i+h[i];
        int h2=i-h[i];
        if(id.find(h1)==id.end()) id[h1]=++tot;
        if(id.find(h2)==id.end()) id[h2]=++tot;
        h1=id[h1]; h2=id[h2];
        E[i]=mp(h1,h2); deg[h1]++; deg[h2]++;
    }
    for(int i=1;i<=tot;i++) p[i]=i;
    sort(p+1,p+1+tot,cmp);
    for(int i=1;i<=tot;i++) rk[p[i]]=i;
    for(int i=1;i<=n;i++){
        int u=E[i].fi,v=E[i].se;
        if(rk[u]<rk[v]) G[u].pb(v);
        else G[v].pb(u);
    }
    for(int u=1;u<=tot;u++){
        for(auto v:G[u]) from[v]=u;
        for(auto v:G[u])
            for(auto w:G[v])
                if(from[w]==u) ans++;
    }
    for(int i=1;i<=n;i++) L[i].clear(),R[i].clear(); 
    for(int i=1;i<=tot;i++){
        G[i].clear(); deg[i]=0;
    } id.clear();
    return ans;
}
vi ans; int m;
void add(int x,int y){
    if(x<y) swap(x,y);
    int i=(x+y)/2,j=(x-y)/2;
    if(!ans[i]) ans[i]=j;
}
vi construct_range(int M,int K){
    ans.resize(M); int lim=2700,seed=330;
    double st=clock(); vi res; ll cur=0;
    while((clock()-st)/CLOCKS_PER_SEC<=1.8){
        mt19937 rnd(seed); vi vec;
        for(auto &z:ans) z=0;
        for(int i=0;i<=M;i+=2) vec.pb(i);
        shuffle(vec.begin(),vec.end(),rnd);
        if(vec.size()>lim) vec.resize(lim);
        for(int i=0;i<vec.size();i++)
            for(int j=0;j<i;j++) add(vec[i],vec[j]);
        for(auto &z:ans) 
            if(!z) z=1;
        int z=count_triples(ans);
        if(count_triples(ans)>cur){
            cur=z; res=ans;
        } seed++;
    }
    return res;
}