icontofig | 发布于 2020-02-06 20:52:24 | 阅读量 306 | 最小生成树 Trie
发布于 2020-02-06 20:52:24 | 最小生成树 Trie

题解

每条边的权值都是根据每个点的定值通过二进制异或得出的。

如果有两个点的数二进制高k位相等,那么我们如果要想要把这两个点的边加入最小生成树,那么花费的代价是与高k位无关的。

假设在第k+1位发生分歧,则这条边的最小权值即为这一位对应的二进制值。然后要做的就是继续向更低位检查。

这明显是个递归过程,而且很容易能想到这个过程是与01Trie的节点访问实际上是一样的。

于是所有的答案统计全部都在01trie上。

接下来看kruskal算法的核心:每一次将最小边权的边试图加入最小生成森林。

所以我们必然优先去找01Trie中同一个叶子节点上的点对的边。

假如一个叶节点上有k个点(k > 2),那么对应的建边方案就是kk-2种。

当从叶节点向上走的时候,假设某节点的父亲节点的两个子树上都有点存在(即两个子树都非空),那么我们肯定要用边把这两个子树连起来,连起来的时候就需要顺着trie往下找异或值最小的边的权值是多少。

细节不是很好解释,不过这种思路是二进制异或时一种常见的贪心思路,可以看代码理解一下。

这个题不需要并查集,因为当刚向上走到某个点时,如果其两个子树都非空,那么这两个子树代表的两个已经构建好的生成树必然属于两个不同的连通块。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PI;
const int maxn = 1e5+5;
const int INF = 2e9;
const ll MOD = 1e9+7;
int n, sz, fac[35], rt;
ll ans,sum;
struct tree{
    int l, r, cnt;
} tr[maxn*30];
ll quick_pow(ll x, ll y){
    ll ans = 1;
    while (y){
        if (y & 1)
            ans = ans * x % MOD;
        x = x * x % MOD;
        y >>= 1;
    }
    return ans;
}
void insert(int &d, int dep, int v){
    if (!d)
        d = ++sz;
    tr[d].cnt++;
    if (dep < 0)
        return;
    if (v & fac[dep])
        insert(tr[d].l, dep - 1, v);
    else
        insert(tr[d].r, dep - 1, v);
}
PI get(int x, int y, int dep){
    if (dep < 0)
        return make_pair(0, (ll)tr[x].cnt * tr[y].cnt % MOD);
    PI ans = make_pair(INF, 0);
    if (tr[x].l && tr[y].l || tr[x].r && tr[y].r){
        if (tr[x].l && tr[y].l){
            PI now = get(tr[x].l, tr[y].l, dep - 1);
            if (now.first < ans.first)
                ans = now;
            else if (now.first == ans.first)
                ans.second += now.second,ans.second %= MOD;
        }
        if (tr[x].r && tr[y].r){
            PI now = get(tr[x].r, tr[y].r, dep - 1);
            if (now.first < ans.first)
                ans = now;
            else if (now.first == ans.first)
                ans.second += now.second,ans.second %= MOD;
        }
    }
    else{
        if (tr[x].l && tr[y].r){
            PI now = get(tr[x].l, tr[y].r, dep - 1);
            now.first += fac[dep];
            if (now.first < ans.first)
                ans = now;
            else if (now.first == ans.first)
                ans.second += now.second,ans.second %= MOD;
        }
        if (tr[x].r && tr[y].l){
            PI now = get(tr[x].r, tr[y].l, dep - 1);
            now.first += fac[dep];
            if (now.first < ans.first)
                ans = now;
            else if (now.first == ans.first)
                ans.second += now.second,ans.second %= MOD;
        }
    }
    return ans;
}
void solve(int d, int dep){
    if (dep < 0){
        if (tr[d].cnt > 2)
            sum = (ll)sum * quick_pow(tr[d].cnt, tr[d].cnt - 2) % MOD;
        return;
    }
    if (tr[d].l)
        solve(tr[d].l, dep - 1);
    if (tr[d].r)
        solve(tr[d].r, dep - 1);
    if (tr[d].l && tr[d].r){
        PI now = get(tr[d].l, tr[d].r, dep - 1);
        ans += now.first + fac[dep];
        sum = (ll)sum * now.second % MOD;
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    fac[0] = 1;
    for (int i = 1; i <= 30; i++)
        fac[i] = fac[i - 1] * 2;
    for (int i = 1, x; i <= n; i++){
        cin >> x;
        insert(rt, 30, x);
    }
    sum = 1;
    solve(rt, 30);
    cout << ans << endl;
    cout << sum << endl;
    return 0;
}



内容更新于: 2020-02-06 20:52:24
链接地址: http://blog.leanote.com/post/icontofig/9f7d1776c23c

上一篇: CodeForces - 484E Sign on Fence 二分+主席树

下一篇: luogu P4178 Tree 点分治+树状数组

306 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航