← 返回题目列表

Codeforces · 2048/C

C. 凯文和二进制字符串

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

凯文在月光河公园的河里发现了一个以1开头的二进制字符串$$$s$$$并将其交给了你。你的任务是选择$$$s$$$中的两个非空子串$$$^{\text{*}}$$$(可以重叠),使这两个子串的异或值最大化。

两个二进制字符串 $$$a$$$ 和 $$$b$$$ 的 XOR 被定义为对通过将 $$$a$$$ 和 $$$b$$$ 解释为二进制数而获得的两个数字进行 $$$\oplus$$$ 运算的结果,最左边的位代表最高值。这里,$$$\oplus$$$表示按位异或运算。

您选择的字符串可能有前导零。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。

每个测试用例的唯一行包含一个以 1 开头的二进制字符串 $$$s$$$ ($$$1\le\lvert s\rvert\le 5000$$$)。

保证所有测试用例的 $$$\lvert s\rvert$$$ 总和不超过 $$$5000$$$。

输出

对于每个测试用例,输出四个整数 $$$l_1, r_1, l_2, r_2$$$ ($$$1 \le l_1 \le r_1 \le |s|$$$, $$$1 \le l_2 \le r_2 \le |s|$$$) - 如果您选择的两个子字符串是 $$$s_{l_1} s_{l_1 + 1} \l点 s_{r_1}$$$ 和 $$$s_{l_2} s_{l_2 + 1} \l点 s_{r_2}$$$。

如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

5
111
1000
10111
11101
1100010001101

输出 #1

2 2 1 3
1 3 1 4
1 5 1 4
3 4 1 5
1 13 1 11

注意

在第一个测试用例中,我们可以选择 $$$ s_2=\texttt{1} $$$ 和 $$$ s_1 s_2 s_3=\texttt{111} $$$ 和 $$$ \texttt{1}\oplus\texttt{111}=\texttt{110} $$$。可以证明不可能得到更大的结果。此外,$$$ l_1=3$$$、$$$r_1=3$$$、$$$l_2=1$$$、$$$r_2=3 $$$也是有效的解决方案。

在第二个测试用例中,$$$ s_1 s_2 s_3=\texttt{100} $$$, $$$ s_1 s_2 s_3 s_4=\texttt{1000} $$$,结果为$$$ \texttt{100}\oplus\texttt{1000}=\texttt{1100} $$$,这是最大值。