← 返回题目列表

Codeforces · 1493/E

E. 巨大的异或

中文机器翻译题面 查看原题

给定两个二进制表示的整数 $$$l$$$ 和 $$$r$$$。令 $$$g(x, y)$$$ 等于从 $$$x$$$ 到 $$$y$$$ 之间所有整数的按位异或(即 $$$x \oplus (x+1) \oplus \dots \oplus (y-1) \oplus y$$$)。我们将 $$$f(l, r)$$$ 定义为 $$$g(x, y)$$$ 满足 $$$l \le x \le y \le r$$$ 的所有值中的最大值。

输出$$$f(l,r)$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — $$$r$$$ 的二进制表示形式的长度。

第二行包含 $$$l$$$ 的二进制表示 — 长度为 $$$n$$$ 的字符串,由数字 $$$0$$$ 和 $$$1$$$ 组成 ($$$0 \le l < 2^n$$$)。

第三行包含 $$$r$$$ 的二进制表示 — 长度为 $$$n$$$ 的字符串,由数字 $$$0$$$ 和 $$$1$$$ 组成 ($$$0 \le r < 2^n$$$)。

保证$$$l \le r$$$。 $$$r$$$ 的二进制表示不包含任何额外的前导零(如果 $$$r=0$$$,则其二进制表示由单个零组成)。 $$$l$$$ 的二进制表示形式前面有前导零,因此其长度等于 $$$n$$$。

输出

在单行中以二进制表示形式输出给定的 $$$l$$$ 和 $$$r$$$ 对的 $$$f(l, r)$$$ 值,不带额外的前导零。

示例

输入 #1

7
0010011
1111010

输出 #1

1111111

输入 #2

4
1010
1101

输出 #2

1101

注意

在示例测试用例 $$$l=19$$$ 中,$$$r=122$$$。 $$$f(x,y)$$$ 是最大值,等于 $$$127$$$,例如 $$$x=27$$$,$$$y=100$$$。