leetcode 周赛 526,异或与1个数的关系
作者: | 更新日期:
异或与1个数奇偶性的关系
本文首发于公众号:天空的代码世界,微信号:tiankonguse
零、背景
leetcode 第 526 场比赛在 11 月 1 号。
这天在写 CSP-S 题解,所以就没有时间写 leetcode 比赛题解了。
拖到了今天,感冒没出门,也把短剧戒掉了,小红书和 B 站短视频也刷腻了。
于是便想,补一下这场比赛的题解吧。
本场题型概览如下。
A 题:模拟
B 题:构造
C 题:逆序对
D 题:换根DP
一、合并整数后的最小值
题意:给一个数组,元素依次两两按十进制拼接在一起,最后求最小值。
思路:模拟
按题意两两拼接,然后取最小值。
小技巧 1:可以先转字符串,然后字符串拼接,最后再转数字。
小技巧 2:数字拼接,等价于按进制左移与相加。
ll Merge(ll a, const ll B) {
ll ans = a;
ll b = B;
while (b) {
ans = ans * 10;
b /= 10;
}
return ans + B;
}
二、最小化 GCD 连通数组的最大值
题意:如果一个数组是递增的,且相邻元素的 gcd 大于 1,则称为 GCD 连通数组。
问数组 nums[i] = value 时,是否可以构造出 GCD 连通数组。
如果可以,求最后一个元素的最小值。
思路:构造
想要最后一个元素的值最小,显然需要找到一种方法,使得相邻元素增长速度最慢。
由于需要满足 GCD 大于 1,那就需要加上大于 1 的最小因子。
如果初始值是偶数,最小因子是 2,后续还都是偶数,所以不断加 2 即可。
如果初始值不是偶数,则最小因子是一个奇质数,下一个数字就是偶数了,再之后也都是加上 2。

定义 V 的最小质因子为 M,则:
序列右侧第一个数字是加 M,再之后都是加 2。
序列左侧第一个数字是减 M,再之前都是减 2。

基于这个规律先判断左侧是否成立,成立了求出右侧对应位置的值即可。
计算第一个质因子,复杂度 O(sqrt(n)),随后数学公式构造出答案。
综合复杂度:O(sqrt(n))。
三、将锁定数组排序的最少操作次数
题意:给一个排列序列,部分位置锁定。
现在可以执行两个操作:
1)交换相邻的两个都未加锁的元素。
2)永久解锁一个元素。
问最多解锁 K 次时,使得元素严格递增的最小操作次数。
思路:逆序对
首先判断需要解锁哪些元素。
如果一个加锁的元素最终位置不一致,那肯定需要解锁。
另外,即使位置一致,还需要判断左边是否有大于自己的值,右边是否有小于自己的值,有了,就需要解锁。

如果 K 次操作够用,就把所有需要解锁的元素都解锁了。
之后求逆序数即可。
小技巧:可以使用冒泡排序来求逆序数。
四、平衡异或路径的最小开销
题意:给一个无向带权树,每个节点也有一个权值。
如果两个不同节点之间的路径上的所有节点的异或值在二进制上有偶数个 1,则称为平衡异或路径。
求边权和最小的平衡异或路径。
思路:换根DP
新的知识点,不知道绝对做不出来。
首先,需要推导出异或与二进制 1 个数的关系。
假设一个数字 x 二进制中 1 的个数记作 f(x)。
我们可以发现,这个函数与异或满足下面的关系。

所以,求路径各个节点异或值中 1 的个数的问题,转化为了各个节点 1 的个数奇偶性的异或问题。
因此,可以预处理出每个节点值中 1 的个数的奇偶性。
剩下就是标准的换根DP了。
换根DP,原先根节点是 u,然后把根换成其中一个儿子。
假设换根前,已经求出所有从 u 的祖先到 u 的路径中,节点异或值分别为 0 与 1 的最小路径值。
另外假设也已经预处理出每个儿子的子树中,从子树内各节点到该儿子的路径里,节点异或值分别为 0 与 1 的最小路径值。
然后尝试枚举,把根从 u 换成每一个儿子,例如下图的 c3。
此时,需要求出所有节点经过 u 到达 c3 的路径中,节点异或值分别为 0 与 1 的最小路径值。
这个求出来了,就可以把 c3 作为根了。

显然,这里需要把 c3 排除在外,然后求其他所有到 u 的路径的 0/1 最小路径值。
这是一个经典的换根DP,需要预处理出所有儿子里面的最小值。
由于最小值可能恰好是 c3 这个儿子,所以需要记录次小值,从而计算出真正的最小值。
有了最小值,就可以计算出父路径的 0/1 最小值了。
// 保留最小的 2 个值
vector<vector<ll>> child(2, vector<ll>(2, INT64_MAX2));
auto Add = [](vector<ll>& child, ll v) {
if (child.back() <= v) return;
child.back() = v;
if (child[0] > child[1]) {
swap(child[0], child[1]);
}
};
注意事项:u 转到儿子时,u 到儿子这条路径也需要计算进去。
复杂度:O(n)
五、最后
这次比赛最后一题涉及到异或与二进制 1 个数的公式。
我是第一次遇到这种题,所以没推导出这个公式。
赛后学习了这个公式后,就做出这道题了。
《完》
-EOF-
本文公众号:天空的代码世界
个人微信号:tiankonguse
公众号 ID:tiankonguse-code
本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面关注公众号进行留言。
