记一次人类智慧

fangzichang · 2023-09-12 13:57:12 · 算法·理论

早上比赛。
D 题面大概就是，n 个点完全图求最小生成树，每个点 u 有点权 a_u，点 u 到 v 的边权为 \min(a_u\bmod a_v,a_v\bmod a_u)。
然后点权值域 10^7，n \le 10^5。
不关键的一点，时限五秒。
然后开始人类智慧！

首先点权的式子转换一下就是 \max(a_u,a_v)\bmod \min(a_u,a_v)。
然后发现点权相同的点直接看作一个点。
然后发现，排序去重后，若对于每个 a_i 将 a_i 的所有倍数在数轴上标记一下，则：

总的标记过程是很像调和级数的一个东西，爆不了。

然后就很快乐的开始值域分块找最靠近的点。
然后死在第一个小样例。
因为不能简单的排序。就是假设三个点权 x<y<z，答案可能是 z \to x 然后 y \to z。
然后束手无策了一小会，打完后面的暴力回来整活，既然不能只找最近的一个标记点我就多找几个，找前 11 近的连边跑最小生成树就过了。

要感谢南酱。耳机里 \text{Only My Railgun} 里 \text{儚く舞う無数の願いは} 那一段响起的那一刻突然就人类智慧大爆发。

要稍微调参卡一下空间，但是时间充裕。
排行榜。我也不知道没账号能不能看到。

附在混沌情况下写的代码。累了，懒得写注释了。

#include<bits/extc++.h>
#include<bits/stdc++.h>
//#pragma GCC optimize(3)
//本代码含有小众情感元素，建议满 18 周岁后观看
#define trtag __gnu_pbds::tree_order_statistics_node_update
#define priority_queue __gnu_pbds::priority_queue
#define unordered_map __gnu_pbds::gp_hash_table
#define debug cerr<<"Hwy is homo.\n"
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define pii pair<int,int>
#define Inf (int)INFINITY
#define inf 0x3f3f3f3f
#define pb push_back
#define ll long long
#define endl '\n'
#define y second
#define x first
#define DEBUG
using namespace std;
using namespace __gnu_cxx;
const int N=1e6+10,M=1e7,K=3e3,KK=M/K+10,P=11;
void read(){};
template<class T1,class ...T2>
inline void read(T1& ret,T2&... rest){
    ret=0;char c=getchar();bool f=false;
    while(c<'0'||c>'9'){f=c=='-';c=getchar();}
    while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
    if(f)ret=-ret;
    read(rest...);
}
#define cin(...) read(__VA_ARGS__)
inline void print(int ret){
    static int sta[35];
    int x=ret,top=0;
    bool f=(ret<0);
    if(ret<0) x=-x;
    do{sta[top++]=x%10,x/=10;}while(x);
    if(f) putchar('-');
    while(top) putchar(sta[--top]+48);
}
int n,MM,ans,p[N],idx[M+10];
bool t[M+10];
vector<int> tt[M+10];
struct block{
    int l,r,sum;
    set<int,greater<int>> val;
}b[KK];
int cnt;
struct Edge{
    int u,v,w;
}e[M*2+10];
mt19937 rnd(time(0));
struct UF{
    int fa[N],h[N];
    int find(int x){
        return fa[x]==x?x:fa[x]=find(fa[x]);
    }
    void merge(int x,int y){
        x=find(x),y=find(y);
        if(h[x]>h[y]) swap(x,y);
        fa[x]=y;
    }
    void clear(int n){
        iota(fa+1,fa+n+1,1);
        for(int i=1;i<=n;i++)h[i]=rnd();
    }
}f;
int main(){
    cin(n);
    for(int i=1;i<=n;i++)cin(p[i]);
    sort(p+1,p+n+1);
    n=unique(p+1,p+n+1)-p-1;
    if(n>1e3){
        MM=p[n];
//      reverse(p+1,p+n+1);
        for(int i=1;i<=MM;i++)idx[i]=i/K;
        for(int i=1,lst=1;i<=MM;i++){
            if(idx[i]!=idx[i+1]){
                b[idx[i]].l=lst;
                b[idx[i]].r=i;
                lst=i+1;
            }
        }       
        for(int i=1;i<=n;i++){
            if(i>1){
                int tot=0;
                for(int j=p[i],tot=0;j>=b[idx[p[i]]].l;j--){
                    if(t[j]){
                        for(int v:tt[j])e[++cnt]={i,v,p[i]%j};
                        tot++;
                        if(tot>=P) break;
                    }
                }
                if(tot<P){
                    for(int j=idx[p[i]]-1;j>=0;j--){
                        if(b[j].sum){
                            for(int val:b[j].val){
                                for(int v:tt[val])e[++cnt]={i,v,p[i]%val};
                                tot++;
                                if(tot>=P) break;
                            }
                            if(tot>=P) break;
                        }
                    }               
                }
            }
            for(int j=p[i];j<=MM;j+=p[i]){
                t[j]=1;
                b[idx[j]].sum=1;
                tt[j].pb(i);
                b[idx[j]].val.insert(j);
                if(b[idx[j]].val.size()>P+1) b[idx[j]].val.erase(prev(b[idx[j]].val.end()));
            }
        }   
    }
    else{
        for(int i=1;i<=n;i++){
            for(int j=i+1;j<=n;j++){
                e[++cnt]={i,j,p[j]%p[i]};
            }
        }       
    }
    sort(e+1,e+cnt+1,[](const Edge&a,const Edge&b)->bool{
        return a.w<b.w;
    });
    f.clear(n);
    for(int i=1;i<=cnt;i++){
        int u=e[i].u,v=e[i].v,w=e[i].w;
        if(f.find(u)!=f.find(v)){
            ans+=w;
            f.merge(u,v);
        }
    }
    print(ans);
    putchar(endl);      
    return 0;
}

顺便，没有那句 if(b[idx[j]].val.size()>P+1) b[idx[j]].val.erase(prev(b[idx[j]].val.end())); 会爆空间。
分块是随手分的，压根没算，跑的还很快，最多也就 1.3s。

最后的最后，这个其实很像正解了。