题目大意
有 n ( 2 ≤ n ≤ 1 0 5 ) n(2 \le n \le 10^5) n(2≤n≤105)个正整数的数组 a n , 1 ≤ a i ≤ 1 0 9 a_n,1 \le a_i \le 10^9 an,1≤ai≤109。
对于每个数 a i a_i ai，可以进行如下操作: 找到一个自然数 k k k,满足 2 k ≥ a i 2^k \ge a_i 2k≥ai,使 a i = 2 k − a i a_i = 2^k - a_i ai=2k−ai。
通过数次这种操作,总可以使得变化后 a i a_i ai等于其它任意一个数 a j a_j aj。
那么请问，把哪两个数的变成相同所需次数的最小值最大？
思路
这种操作的本质就是，二进制下选择 a i a_i ai的任意一个比最高位 1 1 1的位，把它后面的所有位数取反，比如 1001 1001 1001,选择 100000 100000 100000这一位,转换后变成 010110 010110 010110，通过数次这种操作，是可以把一个数变成 0 0 0的，也可以从 0 0 0开始构造起来每一个数的。
但是呢，从 0 0 0开始往上构造比较困难，所以我们不如考虑这个数怎么用最短的方法变成0。在二进制下，每次选择最高位 1 1 1前面的那一位进行反转，这么做就是最快的方法，十进制下就是找到最小的 k k k，使得 2 k ≥ a i 2^k \ge a_i 2k≥ai，然后 a i = 2 k − a i a_i = 2^k - a_i ai=2k−ai。
我们先观察一下样例的变化 6 → 2 → 0 → 1 → 7 → 9 6 \rightarrow 2 \rightarrow 0 \rightarrow 1 \rightarrow 7 \rightarrow 9 6→2→0→1→7→9,是不是有点像在遍历边？实际上这道题的重点就是把这转化为图。
其实也不一定所有情况都要经过 0 0 0，比如 7 , 9 7,9 7,9但 9 9 9在向 0 0 0经过的时候，是会经过 7 7 7的，所以这种情况也是会被计算的。
那么我们在建立新的点的时候,对于每个 a i a_i ai，按照把这个数最快变成 0 0 0的方式去建立新的点，如果遇到已经建好的点，那就停止，进行下一个。比如 6 , 9 , 10 6,9,10 6,9,10。 10 10 10在转化成 0 0 0的时候会经过 6 6 6,所以遇到 6 6 6之后就没必要继续建立新的点了(因为后续操作都一样)，并且意味着 6 , 10 6,10 6,10之间的转化不需要经过 0 0 0了。
那么答案就是求树的直径。
为什么一定是一个树呢？假设有 x , y , z x,y,z x,y,z三个点(值各不相同), x , y x,y x,y相连, x , z x,z x,z相连,那么 y , z y,z y,z一定不会相连。
证明：设 x + y = 2 m , x + z = 2 n x + y = 2^m,x + z = 2^n x+y=2m,x+z=2n,则 y + z = 2 m + 2 n − 2 x y + z = 2^m + 2^n - 2x y+z=2m+2n−2x,是没法构造出 2 m + 2 n − 2 x = 2 l 2^m + 2^n - 2x = 2^l 2m+2n−2x=2l的。
代码
G [ x ] G[x] G[x]是个点 x x x的出边, d [ x ] d[x] d[x]是在两次 d f s dfs dfs求直径中点 x x x离根节点的距离,用 m a p < x , y > map<x,y> map<x,y>去储存权值为 x x x的点在图中的编号为 y y 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;
}