题解 | #最长异或公共子段#
最长异或公共子段
https://www.nowcoder.com/practice/2b25c51da0c547cf80a29a3f11c7dd84
最长异或公共子段
思路
题目给了两个不同的非负整数 ，分别生成两个无限序列
和
（
）。要求找到最长的公共连续子段长度
。
"公共连续子段"意味着存在 使得对所有
，有
，即：
$$
两边同时异或，等价于：
$$
其中 是个固定值。
关键转化
问题变成：找最大的 ，使得存在
，对连续
个
值都有
。
取 ，设
，则条件变为
对连续
个
成立。
当我们选 时，条件变成
。什么时候
呢？恰好是
和
没有公共的 1-bit，即
的时候。
所以问题进一步简化为：最长的连续整数段 ，满足每个数与
按位与为 0。
lowbit 就是答案
设 的最低位的 1 在第
位（即
是
的末尾零的个数）。那么
要求
的第
位为 0。但连续的整数中，第
位每隔
个数就会翻转一次。所以最多有
个连续整数使得第
位为 0，同时更高位的约束也可以通过合理选择
的起始位置来满足。
因此答案就是 的 lowbit，即
。
可以验证所有样例：
，lowbit = 1
，lowbit = 8
，lowbit = 4
，lowbit =
复杂度
- 时间：
，每组测试
- 空间：
代码
#include <bits/stdc++.h>
using namespace std;
int main(){
int T;
scanf("%d", &T);
while(T--){
long long x, y;
scanf("%lld%lld", &x, &y);
long long d = x ^ y;
printf("%lld\n", d & (-d));
}
return 0;
}
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
long x = sc.nextLong();
long y = sc.nextLong();
long d = x ^ y;
System.out.println(d & (-d));
}
}
}
import sys
input = sys.stdin.readline
T = int(input())
out = []
for _ in range(T):
x, y = map(int, input().split())
d = x ^ y
out.append(str(d & (-d)))
print('\n'.join(out))
const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
const lines = [];
rl.on('line', (line) => lines.push(line.trim()));
rl.on('close', () => {
let idx = 0;
const T = parseInt(lines[idx++]);
const res = [];
for (let i = 0; i < T; i++) {
const parts = lines[idx++].split(' ').map(BigInt);
const d = parts[0] ^ parts[1];
res.push((d & (-d)).toString());
}
console.log(res.join('\n'));
});
