← 返回题目列表

Codeforces · 1869/A

A. 使其为零

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

在中考考试期间,Reycloer 遇到了一个有趣的问题,但他无法立即想出解决方案。时间不多了!请帮助他。

最初,给你一个由 $$$n \ge 2$$$ 整数组成的数组 $$$a$$$,你想将其中的所有元素更改为 $$$0$$$。

在一次操作中,选择两个索引 $$$l$$$ 和 $$$r$$$ ($$$1\le l\le r\le n$$$) 并执行以下操作:

- 让$$$s=a_l\oplus a_{l+1}\oplus \ldots \oplus a_r$$$,其中$$$\oplus$$$表示按位异或运算;
- 然后,对于所有 $$$l\le i\le r$$$,将 $$$a_i$$$ 替换为 $$$s$$$。

您可以按任何顺序使用上述操作,总共最多 $$$8$$$ 次。

找到一个运算序列,使得按顺序执行运算后,$$$a$$$中的所有元素都等于$$$0$$$。可以证明解总是存在的。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1\let t\le 500$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\le n\le 100$$$) — 数组 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$0\le a_i\le 100$$$) — 数组 $$$a$$$ 的元素。

输出

对于每个测试用例,在第一行输出一个整数 $$$k$$$ ($$$0\le k\le 8$$$) — 您使用的操作数。

然后打印$$$k$$$行,在第$$$i$$$行输出两个整数$$$l_i$$$和$$$r_i$$$ ($$$1\le l_i\le r_i\le n$$$)代表你在第$$$i$$$操作中选择了$$$l_i$$$和$$$r_i$$$。

请注意,您不必最小化 $$$k$$$。如果有多个解决方案,您可以输出其中任何一个。

示例

输入 #1

6
4
1 2 3 0
8
3 1 4 1 5 9 2 6
6
1 5 4 1 4 7
5
0 0 0 0 0
7
1 1 9 9 0 1 8
3
100 100 0

输出 #1

1
1 4
2
4 7
1 8
6
1 2
3 4
5 6
1 3
4 6
1 6
0
4
1 2
6 7
3 4
6 7
1
1 2

注意

在第一个测试用例中,由于$$$1\oplus2\oplus3\oplus0=0$$$,对段$$$[1,4]$$$执行操作后,数组中的所有元素都等于$$$0$$$。

在第二个测试用例中,第一次操作后,数组等于 $$$[3,1,4,15,15,15,15,6]$$$,第二次操作后,数组等于 $$$[0,0,0,0,0,0,0,0]$$$。

在第三个测试用例中:

操作$$$a$$$之前$$$a$$$ $$$1$$$$$$[\下划线{1,5},4,1,4,7]$$$$$$\rightarrow$$$$$$[4,4,4,1,4,7]$$$$$$2$$$$$$[4,4,\下划线{4,1},4, 7]$$$$$$\右箭头$$$$$$[4,4,5,5,4,7]$$$$$$3$$$$$$[4,4,5,5,\下划线{4,7}]$$$$$$\右箭头$$$$$$[4,4,5,5,3,3] $$$$$$4$$$$$$[\下划线{4,4,5},5,3,3]$$$$$$\rightarrow$$$$$$[5,5,5,5,3,3]$$$$$$5$$$$$$[5,5,5,\下划线{5,3,3}] $$$$$$\rightarrow$$$$$$[5,5,5,5,5,5]$$$$$$6$$$$$$[\下划线{5,5,5,5,5,5}]$$$$$$\rightarrow$$$$$$[0,0,0,0,0,0]$$$

在第四个测试用例中,初始数组仅包含 $$$0$$$,因此我们不需要对其执行任何操作。