【Codeforces】1617-E Christmas Chocolates 题解

题目大意

给定 $n$（$2 \le n \le 10^5$）个数的数组 $a_n$（$1 \le a_i \le 10^9$）。

操作：对 $a_i$ 选择最小的 $k$ 使得 $2^k \ge a_i$，令 $a_i = 2^k - a_i$。

通过数次这种操作，总可以使得变化后 $a_i$ 等于其它任意一个数 $a_j$。

那么请问，把哪两个数变成相同所需次数的最小值最大？

题目链接

思路

这种操作的本质是：在二进制下，选择 $a_i$ 最高位 $1$ 前面的那一位进行反转，相当于把最高位前那一位置 $1$，后面所有位取反。比如 $1001$，选择 $100000$ 这一位，转换后变成 $010110$。通过数次这种操作，可以把一个数变成 $0$，也可以从 $0$ 开始构造每一个数。

但是呢，从 $0$ 开始往上构造比较困难，所以我们考虑每个数怎么用最短的方法变成 $0$：每次选择最高位 $1$ 前面的那一位进行反转，这就是最快的方法，即找到最小的 $k$ 使得 $2^k \ge a_i$，令 $a_i = 2^k - a_i$。

我们先观察一下样例的变化：

$$6 \rightarrow 2 \rightarrow 0 \rightarrow 1 \rightarrow 7 \rightarrow 9$$

其实也不一定所有情况都要经过 $0$，比如 $7, 9$，但 $9$ 在向 $0$ 经过的时候会经过 $7$，所以这种情况也会被计算到。

那么在建立新的点时，对于每个 $a_i$，按照把这个数最快变成 $0$ 的方式建立新的点，如果遇到已经建好的点就停止。比如 $6, 9, 10$：$10$ 在转化成 $0$ 的时候会经过 $6$，所以遇到 $6$ 之后就没必要继续建立新的点了，并且意味着 $6, 10$ 之间的转化不需要经过 $0$。

那么答案就是求树的直径。

为什么一定是一棵树呢？假设有 $x, y, z$ 三个点（值各不相同），$x, y$ 相连，$x, z$ 相连，那么 $y, z$ 一定不会相连。

证明：设 $x + y = 2^m,\ x + z = 2^n$，则 $y + z = 2^m + 2^n - 2x$，是无法构造出 $2^m + 2^n - 2x = 2^l$ 的。

代码

$G[x]$ 是点 $x$ 的出边，$d[x]$ 是在两次 dfs 求直径中点 $x$ 离根节点的距离，用 $map\langle x, y\rangle$ 储存权值为 $x$ 的点在图中的编号为 $y$。

#include <cstdio>
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
 
const int maxN = 2e5 + 7;
 
int n, a[maxN], cnt, d[maxN * 31];
vector<int> G[maxN * 31];
unordered_map<int, int> mp;
 
inline int GetFa(int x)
{
    int t = 0;
    while((1 << t) < x)
        t++;
    return (1 << t) - x;
}
 
inline void dfs(int x, int fa)
{
    d[x] = fa ? d[fa] + 1 : 0;
    for(int i = 0; i < G[x].size(); ++i)
        if(G[x][i] != fa)
            dfs(G[x][i], x);
}
 
int main()
{
    scanf("%d", &n);
    mp[0] = cnt = 1;
    for(int i = 1; i <= n; ++i) {
        scanf("%d", &a[i]);
        int p = a[i];
        if(mp[p]) continue;
        mp[p] = ++cnt;
        int nxt = GetFa(p);
        while(!mp[nxt]) {
            mp[nxt] = ++cnt;
            G[mp[nxt]].emplace_back(mp[p]);
            G[mp[p]].emplace_back(mp[nxt]);
            p = nxt; nxt = GetFa(p);
        }
        G[mp[nxt]].emplace_back(mp[p]);
        G[mp[p]].emplace_back(mp[nxt]);
    }
    int st = 1, ed = 1;
    dfs(mp[a[1]], 0);
    for(int i = 2; i <= n; ++i)
        if(d[mp[a[st]]] < d[mp[a[i]]])
            st = i;
    dfs(mp[a[st]], 0);
    for(int i = 2; i <= n; ++i)
        if(d[mp[a[ed]]] < d[mp[a[i]]])
            ed = i;
    printf("%d %d %d\n", st, ed, d[mp[a[ed]]]);
    return 0;
}