309500: CF1689E. ANDfinity
Memory Limit：256 MB
Time Limit：4 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
ANDfinity
题意翻译
#### 题目描述 从计算机科学系毕业后， Vlad 被奖与一个由 $n$ 个非负整数组成的数组 $a_1,a_2, \dots , a_n$。他很自然地想到构建一个有 $n$ 个点，编号为 $1,2,\dots,n$ 的图。点 $i$ 和 $j$ 之间有边当且仅当 $a_i\& a_j >0$，其中 $\&$ 表示按位与。 Vlad 希望这张图连通，虽然最初可能不是这样。为了使图连通，他可以对这个数组做下列两种操作： 1. 选择一个元素 $a_i$ 并将它加一。 2. 选择一个元素 $a_i$ 并将它减一（仅能在 $a_i>0$ 时做此操作）。 可以证明存在一个有穷的操作序列使得这张图连通。所以，你能帮 Vlad 找到最少的可能操作数以达成这个目标并给出操作方法吗？ #### 输入格式 输入多组数据。 第一行一个整数 $t$ $(1 \le t \le 1000)$ 表示数据组数。 对于每组数据，第一行一个整数 $n$ $(2 \le n \le 2000)$。 第二行包含 $n$ 个整数 $a_1 , a_2 , \dots ,a_n$ $(0 \le a_i < 2^{30} )$表示给出的数组 $a$ 中各个元素。 保证所有数据中 $n$ 之和不超过 2000。 #### 输出格式 对于每组数据，第一行输出一个整数 $m$ 表示最少操作数。 第二行输出经过一系列有效操作后使得对应的图连通的数组。 如果存在多种解，输出任意一个。题目描述
Bit Lightyear, to the ANDfinity and beyond! After graduating from computer sciences, Vlad has been awarded an array $ a_1,a_2,\ldots,a_n $ of $ n $ non-negative integers. As it is natural, he wanted to construct a graph consisting of $ n $ vertices, numbered $ 1, 2,\ldots, n $ . He decided to add an edge between $ i $ and $ j $ if and only if $ a_i \& a_j > 0 $ , where $ \& $ denotes the [bitwise AND operation](https://en.wikipedia.org/wiki/Bitwise_operation#AND). Vlad also wants the graph to be connected, which might not be the case initially. In order to satisfy that, he can do the following two types of operations on the array: 1. Choose some element $ a_i $ and increment it by $ 1 $ . 2. Choose some element $ a_i $ and decrement it by $ 1 $ (possible only if $ a_i > 0 $ ). It can be proven that there exists a finite sequence of operations such that the graph will be connected. So, can you please help Vlad find the minimum possible number of operations to do that and also provide the way how to do that?输入输出格式
输入格式
There are several test cases in the input data. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 1000 $ ) — the number of test cases. This is followed by the test cases description. The first line of each test case contains an integer $ n $ ( $ 2\leq n \leq 2000 $ ). The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0\leq a_i < 2^{30} $ ) — the elements of the array. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2000 $ .
输出格式
For each test case, print a single integer $ m $ in the first line — the minimum number of operations. In the second line print the array after a valid sequence of operations that have been done such that the graph from the task becomes connected. If there are multiple solutions, output any.
输入输出样例
输入样例 #1
4
5
1 2 3 4 5
2
0 2
2
3 12
4
3 0 0 0输出样例 #1
0
1 2 3 4 5
2
2 2
1
3 11
3
3 1 1 1说明
In the first test case, the graph is already connected. In the second test case, we can increment $ 0 $ twice and end up with the array $ [2,2] $ . Since $ 2 \& 2 = 2 > 0 $ , the graph is connected. It can be shown that one operation is not enough. In the third test case, we can decrement $ 12 $ once and we end up with an array $ [3,11] $ . $ 3 \& 11 = 3 > 0 $ hence the graph is connected. One operation has to be done since the graph is not connected at the beginning.Input
题意翻译
#### 题目描述 从计算机科学系毕业后， Vlad 被奖与一个由 $n$ 个非负整数组成的数组 $a_1,a_2, \dots , a_n$。他很自然地想到构建一个有 $n$ 个点，编号为 $1,2,\dots,n$ 的图。点 $i$ 和 $j$ 之间有边当且仅当 $a_i\& a_j >0$，其中 $\&$ 表示按位与。 Vlad 希望这张图连通，虽然最初可能不是这样。为了使图连通，他可以对这个数组做下列两种操作： 1. 选择一个元素 $a_i$ 并将它加一。 2. 选择一个元素 $a_i$ 并将它减一（仅能在 $a_i>0$ 时做此操作）。 可以证明存在一个有穷的操作序列使得这张图连通。所以，你能帮 Vlad 找到最少的可能操作数以达成这个目标并给出操作方法吗？ #### 输入格式 输入多组数据。 第一行一个整数 $t$ $(1 \le t \le 1000)$ 表示数据组数。 对于每组数据，第一行一个整数 $n$ $(2 \le n \le 2000)$。 第二行包含 $n$ 个整数 $a_1 , a_2 , \dots ,a_n$ $(0 \le a_i < 2^{30} )$表示给出的数组 $a$ 中各个元素。 保证所有数据中 $n$ 之和不超过 2000。 #### 输出格式 对于每组数据，第一行输出一个整数 $m$ 表示最少操作数。 第二行输出经过一系列有效操作后使得对应的图连通的数组。 如果存在多种解，输出任意一个。Output
**题目大意：**
Vlad 毕业于计算机科学系后，获得了一个由 $n$ 个非负整数组成的数组 $a_1, a_2, \dots, a_n$。他想要构建一个包含 $n$ 个点（编号为 $1, 2, \dots, n$）的图，其中点 $i$ 和 $j$ 之间有边当且仅当 $a_i \& a_j > 0$，这里的 $\&$ 表示按位与操作。Vlad 希望这张图是连通的，虽然最初可能不是。为了使图连通，他可以执行以下两种操作：
1. 选择一个元素 $a_i$ 并将其加一。
2. 选择一个元素 $a_i$ 并将其减一（仅在 $a_i > 0$ 时可执行此操作）。
可以证明，存在一个有限的操作序列使得这张图连通。要求帮助 Vlad 找到最少的操作数以达成这个目标，并给出操作方法。
**输入格式：**
输入包含多组数据。
第一行一个整数 $t$ $(1 \le t \le 1000)$，表示数据组数。
对于每组数据，第一行一个整数 $n$ $(2 \le n \le 2000)$。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(0 \le a_i < 2^{30})$，表示数组 $a$ 的各个元素。
保证所有数据中 $n$ 的总和不超过 2000。
**输出格式：**
对于每组数据，第一行输出一个整数 $m$，表示最少操作数。
第二行输出经过一系列有效操作后使得对应的图连通的数组。
如果存在多种解，输出任意一个。**题目大意：** Vlad 毕业于计算机科学系后，获得了一个由 $n$ 个非负整数组成的数组 $a_1, a_2, \dots, a_n$。他想要构建一个包含 $n$ 个点（编号为 $1, 2, \dots, n$）的图，其中点 $i$ 和 $j$ 之间有边当且仅当 $a_i \& a_j > 0$，这里的 $\&$ 表示按位与操作。Vlad 希望这张图是连通的，虽然最初可能不是。为了使图连通，他可以执行以下两种操作： 1. 选择一个元素 $a_i$ 并将其加一。 2. 选择一个元素 $a_i$ 并将其减一（仅在 $a_i > 0$ 时可执行此操作）。 可以证明，存在一个有限的操作序列使得这张图连通。要求帮助 Vlad 找到最少的操作数以达成这个目标，并给出操作方法。 **输入格式：** 输入包含多组数据。 第一行一个整数 $t$ $(1 \le t \le 1000)$，表示数据组数。 对于每组数据，第一行一个整数 $n$ $(2 \le n \le 2000)$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(0 \le a_i < 2^{30})$，表示数组 $a$ 的各个元素。 保证所有数据中 $n$ 的总和不超过 2000。 **输出格式：** 对于每组数据，第一行输出一个整数 $m$，表示最少操作数。 第二行输出经过一系列有效操作后使得对应的图连通的数组。 如果存在多种解，输出任意一个。
Vlad 毕业于计算机科学系后，获得了一个由 $n$ 个非负整数组成的数组 $a_1, a_2, \dots, a_n$。他想要构建一个包含 $n$ 个点（编号为 $1, 2, \dots, n$）的图，其中点 $i$ 和 $j$ 之间有边当且仅当 $a_i \& a_j > 0$，这里的 $\&$ 表示按位与操作。Vlad 希望这张图是连通的，虽然最初可能不是。为了使图连通，他可以执行以下两种操作：
1. 选择一个元素 $a_i$ 并将其加一。
2. 选择一个元素 $a_i$ 并将其减一（仅在 $a_i > 0$ 时可执行此操作）。
可以证明，存在一个有限的操作序列使得这张图连通。要求帮助 Vlad 找到最少的操作数以达成这个目标，并给出操作方法。
**输入格式：**
输入包含多组数据。
第一行一个整数 $t$ $(1 \le t \le 1000)$，表示数据组数。
对于每组数据，第一行一个整数 $n$ $(2 \le n \le 2000)$。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(0 \le a_i < 2^{30})$，表示数组 $a$ 的各个元素。
保证所有数据中 $n$ 的总和不超过 2000。
**输出格式：**
对于每组数据，第一行输出一个整数 $m$，表示最少操作数。
第二行输出经过一系列有效操作后使得对应的图连通的数组。
如果存在多种解，输出任意一个。**题目大意：** Vlad 毕业于计算机科学系后，获得了一个由 $n$ 个非负整数组成的数组 $a_1, a_2, \dots, a_n$。他想要构建一个包含 $n$ 个点（编号为 $1, 2, \dots, n$）的图，其中点 $i$ 和 $j$ 之间有边当且仅当 $a_i \& a_j > 0$，这里的 $\&$ 表示按位与操作。Vlad 希望这张图是连通的，虽然最初可能不是。为了使图连通，他可以执行以下两种操作： 1. 选择一个元素 $a_i$ 并将其加一。 2. 选择一个元素 $a_i$ 并将其减一（仅在 $a_i > 0$ 时可执行此操作）。 可以证明，存在一个有限的操作序列使得这张图连通。要求帮助 Vlad 找到最少的操作数以达成这个目标，并给出操作方法。 **输入格式：** 输入包含多组数据。 第一行一个整数 $t$ $(1 \le t \le 1000)$，表示数据组数。 对于每组数据，第一行一个整数 $n$ $(2 \le n \le 2000)$。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ $(0 \le a_i < 2^{30})$，表示数组 $a$ 的各个元素。 保证所有数据中 $n$ 的总和不超过 2000。 **输出格式：** 对于每组数据，第一行输出一个整数 $m$，表示最少操作数。 第二行输出经过一系列有效操作后使得对应的图连通的数组。 如果存在多种解，输出任意一个。