题解：AT_abc425_g [ABC425G] Sum of Min of XOR
codwarm
·
·
题解
G - Sum of Min of XOR
自己想的一个比较不同的做法。
好写好理解。0 观察。0 注意力。
题意
令 m = M - 1。
求 \displaystyle \sum_{x=0}^{m} \min_{1\le i\le N} \left(x\oplus a_i \right)。
## 做法
若 $m$ 比较小，则可以建 trie 树，遍历 $0$ 到 $m$，从高位到低位，每次能往相同的走就尽量走。
不能的话则第 $i$ 位会为答案增加一个 $2^i$ 的贡献。
这启发我们去计算 trie 每一个树上的节点产生了多少贡献。
即大概是求一个节点会被多少个数走到，然后有多少个数会向 $0/1$ 走。
但这似乎有点困难。
因为走到一个节点上的数是多个区间。
还有 $m$ 的限制，这导致了一个节点向 $0/1$ 走的数的个数还不一样。
想想看，如果 $m=2^k-1$，那么可以保证的是 trie 树上任何一个节点
向 $0/1$ 走的数个数都是一样的。
在 dfs 的过程中维护当前位和走到当前节点的数的个数即可。
容易想到我们可以把 $[0,m]$ 拆成若干个长度为 $2^k$ 的区间来做。
具体来说，就是先找到一个极大的区间 $[0,2^k-1]$，然后继续去拆 $[2^k,m]$。
对于一个 $[x,x + 2^k-1]$ 的区间，我们可以先在 trie 树上找到他们共同的父亲，然后再跑 dfs。
这样就等价于 $m=2^k-1$ 的问题了。
```cpp
int n,m,a[N];
int son[N * 32][2],tot;
void insert(int x)
{
int p = 0;
for (int j = 30;j >= 0;j--)
{
int ch = (x >> j & 1);
if (!son[p][ch]) son[p][ch] = ++tot;
p = son[p][ch];
}
}
ll ans = 0;
void solve(int x,int w,int cnt)
{
if (!son[x][0] && !son[x][1]) return;
if (son[x][0] && son[x][1])
{
solve(son[x][0],w-1,cnt/2);
solve(son[x][1],w-1,cnt/2);
}
else if (son[x][0])
{
ans += ((1ll<<w) * cnt / 2);
solve(son[x][0],w-1,cnt);
}
else{
ans += ((1ll<<w) * cnt / 2);
solve(son[x][1],w-1,cnt);
}
}
void solvemain()
{
cin >> n >> m;
m--;
rep(i,1,n) cin >> a[i],insert(a[i]);
for (int i = 30;i >= 0;i--)
if (m >> i & 1)
{
int p = 0,cnt = (1<<i);
for (int j = 30;j >= i;j--)
{
int ch = (m >> j & 1);if(j==i)ch=0;
if (son[p][ch])p=son[p][ch];
else p = son[p][!ch],ans += cnt * (1ll<<j);
}
solve(p,i - 1,cnt);
}
int p = 0,cnt = 1; // 还剩下一个 [m,m]
for (int j = 30;j >= 0;j--)
{
int ch = (m >> j & 1);
if (son[p][ch])p=son[p][ch];
else p = son[p][!ch],ans += cnt * (1ll<<j);
}
cout << ans << endl;
}
```