Mio and Lucky Array

题意翻译

Mio 有一个长度为 $n$ 的数组 $a$ 和一个长度为 $m$ 的数组 $b$。 Mio 可以对 $a$ 进行如下操作： - 选择一个之前未被选择的数字 $i(1\le i\le n)$，并让 $a_i$ 加 $1$，$a_{i+1}$ 减 $2$，$a_{i+2}$ 加 $3$……换句话说，就是对所有的 $i\le j\le n$，令 $a_j$ 加上 $(-1)^{j-i}\cdot (j-i+1)$。 Mio 想要对 $a$ 进行若干次这样的操作使得 $b$ 成为 $a$ 的一个**连续**子序列。判断是否可行，如果可行输出一个合法的操作序列。

题目描述

Mio has an array $ a $ consisting of $ n $ integers, and an array $ b $ consisting of $ m $ integers. Mio can do the following operation to $ a $ : - Choose an integer $ i $ ( $ 1 \leq i \leq n $ ) that has not been chosen before, then add $ 1 $ to $ a_i $ , subtract $ 2 $ from $ a_{i+1} $ , add $ 3 $ to $ a_{i+2} $ an so on. Formally, the operation is to add $ (-1)^{j-i} \cdot (j-i+1) $ to $ a_j $ for $ i \leq j \leq n $ . Mio wants to transform $ a $ so that it will contain $ b $ as a subarray. Could you answer her question, and provide a sequence of operations to do so, if it is possible? An array $ b $ is a subarray of an array $ a $ if $ b $ can be obtained from $ a $ by deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

输入输出格式

输入格式

The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The description of test cases follows. The first line of each test case contains one integer $ n $ ( $ 2 \leq n \leq 2 \cdot 10^5 $ ) — the number of elements in $ a $ . The second line of the test case contains $ n $ integers $ a_1, a_2, \cdots, a_n $ ( $ -10^5 \leq a_i \leq 10^5 $ ), where $ a_i $ is the $ i $ -th element of $ a $ . The third line of the test case contains one integer $ m $ ( $ 2 \leq m \leq n $ ) — the number of elements in $ b $ . The fourth line of the test case contains $ m $ integers $ b_1, b_2, \cdots, b_m $ ( $ -10^{12} \leq b_i \leq 10^{12} $ ), where $ b_i $ is the $ i $ -th element of $ b $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

If it is impossible to transform $ a $ so that it contains $ b $ as a subarray, output $ -1 $ . Otherwise, the first line of output should contain an integer $ k $ ( $ 0 \leq k \leq n $ ), the number of operations to be done. The second line should contain $ k $ distinct integers, representing the operations done in order. If there are multiple solutions, you can output any. Notice that you do not need to minimize the number of operations.

输入输出样例

输入样例 #1

5
5
1 2 3 4 5
5
2 0 6 0 10
5
1 2 3 4 5
3
3 5 3
8
-3 2 -3 -4 4 0 1 -2
4
10 -6 7 -7
5
1 2 3 4 5
4
1 10 1 1
5
0 0 0 0 0
2
10 12

输出样例 #1

1
1 
1
4 
5
1 3 4 6 8 
-1
-1

说明

In the first test case, the sequence $ a $ = $ [1,2,3,4,5] $ . One of the possible solutions is doing one operation at $ i = 1 $ (add $ 1 $ to $ a_1 $ , subtract $ 2 $ from $ a_2 $ , add $ 3 $ to $ a_3 $ , subtract $ 4 $ from $ a_4 $ , add $ 5 $ to $ a_5 $ ). Then array $ a $ is transformed to $ a $ = $ [2,0,6,0,10] $ , which contains $ b $ = $ [2, 0, 6, 0, 10] $ as a subarray. In the second test case, the sequence $ a $ = $ [1,2,3,4,5] $ . One of the possible solutions is doing one operation at $ i = 4 $ (add $ 1 $ to $ a_4 $ , subtract $ 2 $ from $ a_5 $ ). Then array $ a $ is transformed to $ a $ = $ [1,2,3,5,3] $ , which contains $ b $ = $ [3,5,3] $ as a subarray. In the third test case, the sequence $ a $ = $ [-3, 2, -3, -4, 4, 0, 1, -2] $ . One of the possible solutions is the following. - Choose an integer $ i=8 $ to do the operation. Then array $ a $ is transformed to $ a $ = $ [-3, 2, -3, -4, 4, 0, 1, -1] $ . - Choose an integer $ i=6 $ to do the operation. Then array $ a $ is transformed to $ a $ = $ [-3, 2, -3, -4, 4, 1, -1, 2] $ . - Choose an integer $ i=4 $ to do the operation. Then array $ a $ is transformed to $ a $ = $ [-3, 2, -3, -3, 2, 4, -5, 7] $ . - Choose an integer $ i=3 $ to do the operation. Then array $ a $ is transformed to $ a $ = $ [-3, 2, -2, -5, 5, 0, 0, 1] $ . - Choose an integer $ i=1 $ to do the operation. Then array $ a $ is transformed to $ a $ = $ [-2, 0, 1, -9, 10, -6, 7, -7] $ . The resulting $ a $ is $ [-2, 0, 1, -9, 10, -6, 7, -7] $ , which contains $ b $ = $ [10, -6, 7, -7] $ as a subarray. In the fourth test case, it is impossible to transform $ a $ so that it contains $ b $ as a subarray. In the fifth test case, it is impossible to transform $ a $ so that it contains $ b $ as a subarray.

**题目大意：**
Mio有两个数组，一个长度为$n$的数组$a$和一个长度为$m$的数组$b$。Mio可以对数组$a$执行以下操作：选择一个未被选择过的整数$i$（$1 \leq i \leq n$），然后对$a_i$加1，$a_{i+1}$减2，$a_{i+2}$加3，以此类推，直到数组末尾。具体来说，就是对所有$i \leq j \leq n$，令$a_j$加上$(-1)^{j-i} \cdot (j-i+1)$。Mio想要通过若干次这样的操作使得$b$成为$a$的一个连续子序列。需要判断这是否可行，如果可行，则输出一个合法的操作序列。

**输入输出数据格式：**
- **输入格式：**
- 第一行包含一个整数$t$（$1 \leq t \leq 10^4$），表示测试用例的数量。
- 每个测试用例包含以下内容：
- 第一行包含一个整数$n$（$2 \leq n \leq 2 \cdot 10^5$），表示数组$a$的元素数量。
- 第二行包含$n$个整数$a_1, a_2, \cdots, a_n$（$-10^5 \leq a_i \leq 10^5$），代表数组$a$的元素。
- 第三行包含一个整数$m$（$2 \leq m \leq n$），表示数组$b$的元素数量。
- 第四行包含$m$个整数$b_1, b_2, \cdots, b_m$（$-10^{12} \leq b_i \leq 10^{12}$），代表数组$b$的元素。
- 保证所有测试用例的$n$之和不超过$2 \cdot 10^5$。
- **输出格式：**
- 如果无法通过操作使得$a$包含$b$作为子序列，则输出$-1$。
- 否则，第一行输出一个整数$k$（$0 \leq k \leq n$），表示需要执行的操作次数。
- 第二行输出$k$个不同的整数，代表按顺序执行的操作。
- 如果存在多个解决方案，可以输出任意一个。
- 注意，不需要最小化操作次数。**题目大意：** Mio有两个数组，一个长度为$n$的数组$a$和一个长度为$m$的数组$b$。Mio可以对数组$a$执行以下操作：选择一个未被选择过的整数$i$（$1 \leq i \leq n$），然后对$a_i$加1，$a_{i+1}$减2，$a_{i+2}$加3，以此类推，直到数组末尾。具体来说，就是对所有$i \leq j \leq n$，令$a_j$加上$(-1)^{j-i} \cdot (j-i+1)$。Mio想要通过若干次这样的操作使得$b$成为$a$的一个连续子序列。需要判断这是否可行，如果可行，则输出一个合法的操作序列。 **输入输出数据格式：** - **输入格式：** - 第一行包含一个整数$t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 - 每个测试用例包含以下内容： - 第一行包含一个整数$n$（$2 \leq n \leq 2 \cdot 10^5$），表示数组$a$的元素数量。 - 第二行包含$n$个整数$a_1, a_2, \cdots, a_n$（$-10^5 \leq a_i \leq 10^5$），代表数组$a$的元素。 - 第三行包含一个整数$m$（$2 \leq m \leq n$），表示数组$b$的元素数量。 - 第四行包含$m$个整数$b_1, b_2, \cdots, b_m$（$-10^{12} \leq b_i \leq 10^{12}$），代表数组$b$的元素。 - 保证所有测试用例的$n$之和不超过$2 \cdot 10^5$。 - **输出格式：** - 如果无法通过操作使得$a$包含$b$作为子序列，则输出$-1$。 - 否则，第一行输出一个整数$k$（$0 \leq k \leq n$），表示需要执行的操作次数。 - 第二行输出$k$个不同的整数，代表按顺序执行的操作。 - 如果存在多个解决方案，可以输出任意一个。 - 注意，不需要最小化操作次数。