UOJ176 新年的繁荣题解

题意：

在这新年的第一天，神族首领 cxy 打算重新规划一下神族领地的交通。

神族领地中有 \(n\) 个城市，其中第 \(i\) 座城市的繁荣度为 \(a_i\)。神族领地中任意两个城市之间都可以修建双向道路，在第 \(i\) 座城市和第 \(j\) 座城市之间修建道路可以给新的一年带来 \(a_i \mathbin{\mathrm{and}} a_j\) 的繁荣度。其中 \(\mathbin{\mathrm{and}}\) 表示按位与运算，例如 \(2 \mathbin{\mathrm{and}} 3=2\)，\(1 \mathbin{\mathrm{and}} 0=0\)，\(1 \mathbin{\mathrm{and}} 1=1\)。

为了彰显自己的功绩，神族首领 cxy 决定修建若干条道路，使得任意两个城市之间都可以只通过他新修建的道路直接或者间接到达，为了发扬节约精神，他决定修建恰好 \(n-1\) 条道路。一个修建方案的繁荣度是所有要修建的道路带来的繁荣程度之和。

作为一个英明的首领， cxy 决定在所有可行的方案中选择繁荣度最大的方案，现在他想要知道他选择的方案的繁荣度，但是因为他日理万机，没有时间来想这种简单的小问题，于是他就让你来帮忙啦。

输入格式：

第一行两个正整数 \(n,m\)。

接下来一行 \(n\) 个非负整数表示 \(a_i\) 。

输出格式：

输出所有方案中最大的繁荣度。

数据范围：

\(1 \le n \le 10^5,m \le 18,~0 \leq a_i < 2^m\)

~~这个数据范围很有迷惑性，看上去很像 \(\mathcal{O}(nm)\) 的算法~~

~~然而经过思考可以发现，似乎并不存在这样的做法。~~

但是我们可以发现最优方案中一定会让较高位的 \(1\) 尽可能保留。

也就是尽量用 \((110001)_2 \,\mathrm{and}\,(110000)_2\) ，而不是用 \((100011)_2 \,\mathrm{and}\,(110000)_2\)

到此，我们可以发现，点权相同的点可以直接连起来，显然这样不会变劣。

因此我们假设所有的点的点权均不相等。

考虑从大到小枚举点权 \(w\) ，然后枚举所有 \(w^{\prime}\sqsubseteq w\) 的点（定义 \(a\sqsubseteq b\) 为 \(\forall a : a \,\mathrm{and}\, b = a\)）

但是这么做复杂度会爆炸，因为我们会枚举很多没用的点或者不存在的点。

而我们判断一个点是否存在是容易的，因此我们可以反过来枚举 \(w^{\prime}\) ，然后找到所有的 \(w\) 。

（cxy：但是这个 \(w\) 也很多呀！）

这里又用到了一个有趣的思想，即在枚举 \(w^{\prime}\) 的基础上，我们只枚举所有 \(\mathrm{popc}(w) = \mathrm{popc}(w^{\prime})+1\) 的 \(w\) ，

同时用并查集维护每个 \(w^{\prime}\) 的超集所在的连通块。（定义 \(w^{\prime}\) 的超集为 \(\{\mathtt{node}(w)\mid w^{\prime}\sqsubseteq w \land \mathtt{node}(w) \in V\}\)）

具体地，我们用一个 \(\mathtt{id}_{k}\) 表示点权 \(k\) 所对应的连通块的代表点（注意 \(\mathtt{node}(k)\) 不一定存在）

每次合并所有的 \(w\) ，并把它与 \(w^{\prime}\) 合并，同时计算贡献。

注意如果 \(\mathtt{node}(w^{\prime}) \in V\) ，就把 \(\mathtt{node}(w^{\prime})\) 加入连通块内。否则随便选一个点当代表点。

不难发现这样一定能找到最优解。因为每次所有 \(\mathrm{popc}(w) > \mathrm{popc}(w^{\prime})+1\) 的 \(w\) 都在上一轮被合并了。

说实话这个用文字描述是真的难，还是代码比较容易懂。qwq

时间复杂度 \(\mathcal{O}(m2^m)\)

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5+15))
#define M ((int)(3e5+15))

int n,m,res,id[M],f[N],sz[N];
void init(int n) { for(int i=1; i<=n; i++) f[i] = i, sz[i] = 1; }
int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }
bool merge(int u,int v)
{
    int x = find(u), y = find(v);
    if(x == y) return 0;
    if(sz[x] < sz[y]) swap(x,y);
    f[x] = y; sz[y] += sz[x];
    return 1;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m; init(n);
    for(int i=1,x; i<=n; i++)
    { cin >> x; id[x] ? res += x : (id[x] = i); }
    for(int w = (1ll << m) - 1,i,v; w; --w)
    {
        int &u = id[w];
        for(i=0; i<m && !u; i++) u = id[w | (1ll << i)];
        for(; i<m; i++) if( (v = id[w | (1ll << i)]) && merge(u,v)) res += w;
    }
    cout << res << '\n';
    return 0;
}