← 返回题目列表

Codeforces · 1743/D

D. 随机测试的问题

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

给定一个由 $$$n$$$ 个字符组成的字符串 $$$s$$$。 $$$s$$$ 的每个字符不是 0 就是 1。

$$$s$$$ 的子字符串是其字符的连续子序列。

你必须选择 $$$s$$$ 的两个子串(可能相交,可能相同,可能不相交——任意两个子串)。选择它们后,计算所选子字符串对的值,如下所示:

- 让 $$$s_1$$$ 为第一个子字符串,$$$s_2$$$ 为第二个选择的子字符串,$$$f(s_i)$$$ 为整数,使得 $$$s_i$$$ 为其二进制表示形式(例如,如果 $$$s_i$$$ 为 11010,则 $$$f(s_i) = 26$$$);
- 该值是 $$$f(s_1)$$$ 和 $$$f(s_2)$$$ 的按位或。

计算可以获得的最大可能值,并以不带前导零的二进制表示形式打印它。

输入

第一行包含一个整数 $$$n$$$ — $$$s$$$ 中的字符数。

第二行包含 $$$s$$$ 本身,由 $$$n$$$ 字符 0 和/或 1 组成。

该问题中的所有非示例测试都是随机生成的:$$$s$$$ 的每个字符都是独立于其他字符选择的;对于每个字符,其为 1 的概率恰好为 $$$\frac{1}{2}$$$。

这个问题正好有 $$$40$$$ 测试。从 $$$1$$$ 到 $$$3$$$ 的测试是示例;从 $$$4$$$ 到 $$$40$$$ 的测试是随机生成的。在 $$$4$$$ 到 $$$10$$$ 的测试中,$$$n = 5$$$;在 $$$11$$$ 到 $$$20$$$ 的测试中,$$$n = 1000$$$;在 $$$21$$$ 到 $$$40$$$ 的测试中,$$$n = 10^6$$$。

此问题禁止黑客攻击。

输出

以二进制表示形式打印不带前导零的最大可能值。

示例

输入 #1

5
11010

输出 #1

11111

输入 #2

7
1110010

输出 #2

1111110

输入 #3

4
0000

输出 #3

0

注意

在第一个示例中,您可以选择子字符串 11010 和 101。$$$f(s_1) = 26$$$,$$$f(s_2) = 5$$$,它们的按位或为 $$$31$$$,$$$31$$$ 的二进制表示为 11111。

在第二个示例中,您可以选择子字符串 1110010 和 11100。