题目大意
有\(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\)的位，把它后面的所有位数取反，比如\(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<x,y>\)去储存权值为\(x\)的点在图中的编号为\(y\)
1 |
|
- 本文作者： 水蓝络合物
- 本文链接： https://miku39393939.github.io/2022/02/02/Codeforces-1617-E/
- 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！