发布时间：2025-06-20

斩断灵藤(贪心)

定义$f_v$表示儿子$v$剩余的未分配的节点，显然$f_v \lt m$

当前父亲可以选择若干个儿子一起往上传(前提$\sum f_v +1 \leq m$)，剩余的儿子部分就必须自己组成一个连通块

因此，可以贪心，每次尽可能选择更多的儿子

最后别忘了答案+1

void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<int>> adj(n+1);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    vector<int> f(n+1);
    int ans=0; 
    auto dfs=[&](auto &&self,int u,int fa)->void{
        f[u]=1;
        vector<int> tmp;
        for(auto v:adj[u]){
            if(v==fa)continue;
            self(self,v,u);
            tmp.push_back(f[v]);
        }
        sort(tmp.begin(),tmp.end());
        for(int i=0;i<tmp.size();i++){
            if(f[u]+tmp[i]<=m){
                f[u]+=tmp[i];
            }
            else{
                ans+=tmp.size()-i;
                break;
            }
        }
    };
    dfs(dfs,1,0);
    cout<<ans+1<<"\n";
}

移铁术(平衡树)

首先考虑暴力怎么做，从左到右枚举当前位，贪心放最大的，这样肯定最优，复杂度为$O(n^2)$

可以发现，如果当前剩余为$m$，那么可以把头部的$m+1$个元素的最大值移到最前面(相同值取更靠前的)，然后减去代价，把最大值移出队列

考虑如何加速上面过程，官方讲解用的线段树。这里给出一种平衡树的做法，发现文艺平衡树非常容易维护序列的信息，找最大值坐标，删除序列一个元素，都可以在$\log n$内解决

使用fhq-treap实现，每个节点除了维护基本信息，还要维护当前子树的最大值和对应的下标,pushup也非常好写

复杂度为$O(n \log n)$

struct FHQ{
    int ls,rs,key,sz,val,pos,mx;
} fhq[N];
int root,T1,T2,T3,T4,idx;
int newNode(int val){
    fhq[++idx]={0,0,(int)rng(),1,val,1,val};
    return idx;
}
void pushup(int u){
    fhq[u].sz=fhq[fhq[u].ls].sz+fhq[fhq[u].rs].sz+1;
    fhq[u].pos=fhq[fhq[u].ls].pos;
    fhq[u].mx=fhq[fhq[u].ls].mx;
    if(fhq[u].val>fhq[u].mx){
        fhq[u].mx=fhq[u].val;
        fhq[u].pos=fhq[fhq[u].ls].sz+1;
    }
    if(fhq[fhq[u].rs].mx>fhq[u].mx){
        fhq[u].mx=fhq[fhq[u].rs].mx;
        fhq[u].pos=fhq[fhq[u].rs].pos+fhq[fhq[u].ls].sz+1;
    }
}
void split(int u,int k,int &x,int &y){
    if(!u){
        x=y=0;
        return;
    }
    int tmp=fhq[fhq[u].ls].sz+1;
    if(k==tmp){
        x=u;
        y=fhq[u].rs;
        fhq[u].rs=0;
    }
    else if(k<tmp){
        y=u;
        split(fhq[u].ls,k,x,fhq[u].ls);
    }
    else{
        x=u;
        split(fhq[u].rs,k-tmp,fhq[u].rs,y);
    }
    pushup(u);
}
int merge(int x,int y){
    if(!x||!y)return x+y;
    if(fhq[x].key>fhq[y].key){
        fhq[x].rs=merge(fhq[x].rs,y);
        pushup(x);
        return x;
    }
    fhq[y].ls=merge(x,fhq[y].ls);
    pushup(y);
    return y;
}
void solve(){
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        root=merge(root,newNode(x));
    }
    for(int i=1;i<=n;i++){
        int tmp=min(m+1,fhq[root].sz);
        split(root,tmp,T1,T2);
        int val=fhq[T1].mx;
        int pos=fhq[T1].pos;
        m-=pos-1;
        cout<<val<<" ";
        split(T1,pos,T1,T3);
        split(T1,pos-1,T1,T4);
        T1=merge(T1,T3);
        root=merge(T1,T2);
    }
}

昆仑墟(状压dp)

感觉是全场最难的题目了，非常像斯坦纳树，但是发现不是

对于第一个问，求的是最小树形图

在这道题，我们按$v$排序，那么前面的只能往后面加边，那么答案显然是每个节点最小的加边和，$O(n^2)$可以求出

对于第二问，考虑状压dp，$f_{i,S}$表示考虑到$i$，被合并掉的节点状态为$S$的方案数，显然如果$u$要合并到$v$，那么$u \rightarrow v$的权值一定在$u$的出边里面最小，预处理$pre_i$的状态，表示前面有多少个节点能转移到当前节点

如果当前节点不合并，那么$f_{i,S}=f_{i-1,S}$

否则枚举$S$的子集$T$,表示当前未选过的子集$T$合并到$i$，假设$siz$为$T$的$1$的个数，那么合并方案就是$siz!$，同时，令$S'=S-T$，那么原来已经合并了$S'$，方案为$f_{i,S'}$，因此$f_{i,S} += f_{i,S'}*siz!$

最后答案为$f_{n,2^{n-1}-1}$

复杂度$O(n \cdot 3^n)$，注意状态$S$只需要枚举到$2^i-1$，否则超时

void add(int &x,int y){
    x+=y;
    if(x>=mod)x-=mod;
}
int fac[20];
void init(){
    for(int i=(fac[0]=1);i<20;i++)fac[i]=fac[i-1]*i%mod;
}
void solve(){
    init();
    int n;
    cin>>n;
    vector<array<int,3>> a(n);
    for(auto &[x,y,z]:a)cin>>x>>y>>z;
    sort(a.begin(),a.end(),[](auto &x,auto &y){
        return x[2]<y[2];
    });
    vector<int> dis(n+1,INF);
    vector<int> pre(n+1);
    for(int i=0;i<n;i++){
        auto &[x,y,z]=a[i];
        for(int j=i+1;j<n;j++){
            auto &[xx,yy,zz]=a[j];
            dis[i]=min(dis[i],(x-xx)*(x-xx)+(y-yy)*(y-yy));
        }
        for(int j=i+1;j<n;j++){
            auto &[xx,yy,zz]=a[j];
            int d=(x-xx)*(x-xx)+(y-yy)*(y-yy);
            if(d==dis[i])pre[j]|=1<<i;
        }
    }
    int ans=0;
    for(int i=0;i<n-1;i++)ans+=dis[i];
    vector f(n+1,vector<int>(1<<n));
    f[0][0]=1;
    for(int i=0;i<n;i++){
        for(int s=0;s<1<<i;s++){
            f[i+1][s]=f[i][s];
            for(int t=s;t;t=(t-1)&s){
                if((t&pre[i])==t){
                    add(f[i+1][s],f[i][s^t]*fac[__builtin_popcount(t)]%mod);
                }
            }
        }
    }
    cout<<ans<<"\n"<<f[n][(1<<n-1)-1]<<"\n";
}

星空迷轨阵(强连通分量+dp)

首先发现，在一个强连通分量里面的所有点答案相同

接下来考虑在拓扑图上如何计算答案

发现不能直接贪心，因为假设当前有两条路径到达点$u$，对$u$的贡献不一样，当前$u$的答案能正确计算，但是节点$u$后面的节点的最大答案可能需要较小的贡献的质因子来得到

观察值域只有20，分解质因子， 发现$2$指数最多为$4$$3$指数最多为$2$$5,7,9,11,13,17,19$最多为$1$ 因此做多只有$5*3*2^6=960$种数 考虑dp求解转移即可

此时发现，不缩点也能做，但是需要卡卡常( 复杂度$O(960 \cdot n)$

下面代码是987ms极限过的，保险一点的话还是老实缩点吧

bool dp[N][3][5][1<<6];
array<int,3> st[21];
int val[3][5][1<<6];
vector<int> nums={5,7,11,13,17,19};
void init(){
    for(int i=1;i<=20;i++){
        int x=i;
        int cnt=0;
        while(x%3==0)x/=3,cnt++;
        st[i][0]=cnt;
        cnt=0;
        while(x%2==0)x/=2,cnt++;
        st[i][1]=cnt;
        for(int j=0;j<6;j++){
            cnt=0;
            while(x%nums[j]==0)x/=nums[j],cnt++;
            if(cnt)st[i][2]|=1<<j;
        }
    }
    for(int i=0,c=1;i<5;i++,c*=2){
        for(int j=0,nc=c;j<3;j++,nc*=3){
            for(int k=0;k<1<<6;k++){
                int v=nc;
                for(int x=0;x<6;x++){
                    if(k>>x&1)v*=nums[x];
                }
                val[j][i][k]=v;
            }
        }
    }
}
void clear(int n){
    for(int i=0;i<=n;i++){
        memset(dp[i],0,sizeof dp[i]);
    }
}
void solve(){
    int n,m,s;
    cin>>n>>m>>s;
    clear(n);
    vector<int> a(n+1);
    for(int i=1;i<=n;i++)cin>>a[i];
    vector<vector<int>> adj(n+1); 
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
    }
    vector<int> ans(n+1,-1);
    queue<array<int,4>> q;
    dp[s][st[a[s]][0]][st[a[s]][1]][st[a[s]][2]]=1;
    ans[s]=val[st[a[s]][0]][st[a[s]][1]][st[a[s]][2]];
    q.push({s,st[a[s]][0],st[a[s]][1],st[a[s]][2]});
    while(!q.empty()){
        auto [u,c3,c2,mask]=q.front();
        q.pop();
        for(auto v:adj[u]){
            int nc3=max(c3,st[a[v]][0]);
            int nc2=max(c2,st[a[v]][1]);
            int nmask=mask|st[a[v]][2];
            if(!dp[v][nc3][nc2][nmask]){
                dp[v][nc3][nc2][nmask]=1;
                ans[v]=max(ans[v],val[nc3][nc2][nmask]);
                q.push({v,nc3,nc2,nmask});
            }
        }
    }
    for(int i=1;i<=n;i++)cout<<ans[i]<<" \n"[i==n];
}