309615: CF1707B. Difference Array
Memory Limit：256 MB
Time Limit：1 S
Judge Style：Text Compare
Creator：
Submit：0
Solved：0
Description
Difference Array
题意翻译
### 题目描述 你有一个初始长度为 $n$ 的有序数组 $a$（从小到大）。设 $a$ 当前长度为 $l$，你要对 $a$ 作差分，即令 $b_i = a_{i+1} - a_i(1\le i < l)$，然后将 $b$ 数组从小到大排序，接着让 $a_i = b_i(1 \le i < l)$，并继续执行上述操作。 显然，每一次操作后 $a$ 数组的长度都会减少 $1$；执行 $n - 1$ 次操作之后，$a$ 中只会剩下一个元素，请你输出这个剩下的元素。 ### 输入格式 输入包含多组数据，第一行一个正整数 $t(0 < t \le 10^4)$，表示数据组数。 对于每一组数据： - 第一行一个正整数 $n(1 < n \le 10^5)$，表示 $a$ 数组的初始长度 - 第二行 $n$ 个整数 $a_i(0 \le a_i \le 5\times10^5)$，表示 $a$ 数组。 ### 输出格式 $t$ 行，每行一个正整数，表示每一组数据中 $a$ 数组最终剩下的那个元素。 ### 样例解释 令 $\operatorname{sort}(a)$ 表示将 $a$ 数组从小到大排序。 - 对于第一组数据，初始的 $a = \{1,10,100\}$；在第一次操作后，$a=\operatorname{sort}(\{10-1,100-10\})=\{9,90\}$；在第二次操作后，$a = \operatorname{sort}(\{90-9\})=\{81\}$。故答案为 $81$。 - 对于第二组数据，初始的 $a=\{4,8,9,13\}$；在第一次操作后，$a=\operatorname{sort}(\{8-4,9-8,13-9\})=\{1,4,4\}$；在第二次操作后，$a=\operatorname{sort}(\{4-1,4-4\})=\{0,3\}$；在第三次操作后，$a=\operatorname{sort}(\{3-0\})=\{3\}$。故答案为 $3$。题目描述
You are given an array $ a $ consisting of $ n $ non-negative integers. It is guaranteed that $ a $ is sorted from small to large. For each operation, we generate a new array $ b_i=a_{i+1}-a_{i} $ for $ 1 \le i < n $ . Then we sort $ b $ from small to large, replace $ a $ with $ b $ , and decrease $ n $ by $ 1 $ . After performing $ n-1 $ operations, $ n $ becomes $ 1 $ . You need to output the only integer in array $ a $ (that is to say, you need to output $ a_1 $ ).输入输出格式
输入格式
The input consists of multiple test cases. The first line contains a single integer $ t $ ( $ 1\le t\le 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains one integer $ n $ ( $ 2\le n\le 10^5 $ ) — the length of the array $ a $ . The second line contains $ n $ integers $ a_1,a_2,\dots,a_n $ ( $ 0\le a_1\le \ldots\le a_n \le 5\cdot 10^5 $ ) — the array $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2.5\cdot 10^5 $ , and the sum of $ a_n $ over all test cases does not exceed $ 5\cdot 10^5 $ .
输出格式
For each test case, output the answer on a new line.
输入输出样例
输入样例 #1
5
3
1 10 100
4
4 8 9 13
5
0 0 0 8 13
6
2 4 8 16 32 64
7
0 0 0 0 0 0 0输出样例 #1
81
3
1
2
0说明
To simplify the notes, let $ \operatorname{sort}(a) $ denote the array you get by sorting $ a $ from small to large. In the first test case, $ a=[1,10,100] $ at first. After the first operation, $ a=\operatorname{sort}([10-1,100-10])=[9,90] $ . After the second operation, $ a=\operatorname{sort}([90-9])=[81] $ . In the second test case, $ a=[4,8,9,13] $ at first. After the first operation, $ a=\operatorname{sort}([8-4,9-8,13-9])=[1,4,4] $ . After the second operation, $ a=\operatorname{sort}([4-1,4-4])=[0,3] $ . After the last operation, $ a=\operatorname{sort}([3-0])=[3] $ .Input
题意翻译
### 题目描述 你有一个初始长度为 $n$ 的有序数组 $a$（从小到大）。设 $a$ 当前长度为 $l$，你要对 $a$ 作差分，即令 $b_i = a_{i+1} - a_i(1\le i < l)$，然后将 $b$ 数组从小到大排序，接着让 $a_i = b_i(1 \le i < l)$，并继续执行上述操作。 显然，每一次操作后 $a$ 数组的长度都会减少 $1$；执行 $n - 1$ 次操作之后，$a$ 中只会剩下一个元素，请你输出这个剩下的元素。 ### 输入格式 输入包含多组数据，第一行一个正整数 $t(0 < t \le 10^4)$，表示数据组数。 对于每一组数据： - 第一行一个正整数 $n(1 < n \le 10^5)$，表示 $a$ 数组的初始长度 - 第二行 $n$ 个整数 $a_i(0 \le a_i \le 5\times10^5)$，表示 $a$ 数组。 ### 输出格式 $t$ 行，每行一个正整数，表示每一组数据中 $a$ 数组最终剩下的那个元素。 ### 样例解释 令 $\operatorname{sort}(a)$ 表示将 $a$ 数组从小到大排序。 - 对于第一组数据，初始的 $a = \{1,10,100\}$；在第一次操作后，$a=\operatorname{sort}(\{10-1,100-10\})=\{9,90\}$；在第二次操作后，$a = \operatorname{sort}(\{90-9\})=\{81\}$。故答案为 $81$。 - 对于第二组数据，初始的 $a=\{4,8,9,13\}$；在第一次操作后，$a=\operatorname{sort}(\{8-4,9-8,13-9\})=\{1,4,4\}$；在第二次操作后，$a=\operatorname{sort}(\{4-1,4-4\})=\{0,3\}$；在第三次操作后，$a=\operatorname{sort}(\{3-0\})=\{3\}$。故答案为 $3$。Output
**题目大意：**
给定一个初始长度为 $ n $ 的非负整数数组 $ a $，保证 $ a $ 是从小到大排序的。每次操作生成一个新数组 $ b_i = a_{i+1} - a_i $（对于 $ 1 \le i < n $），然后将 $ b $ 数组从小到大排序，用 $ b $ 替换 $ a $，并将 $ n $ 减 $ 1 $。执行 $ n-1 $ 次操作后，数组 $ a $ 只剩下一个元素，需要输出这个元素。
**输入数据格式：**
输入包含多组数据，第一行是一个正整数 $ t $（$ 1 \le t \le 10^4 $），表示数据组数。
对于每组数据：
- 第一行是一个正整数 $ n $（$ 2 \le n \le 10^5 $），表示数组 $ a $ 的长度。
- 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 0 \le a_1 \le \ldots \le a_n \le 5 \times 10^5 $），表示数组 $ a $。
保证所有测试用例的 $ n $ 之和不超过 $ 2.5 \times 10^5 $，$ a_n $ 之和不超过 $ 5 \times 10^5 $。
**输出数据格式：**
对于每组数据，输出一行，包含数组 $ a $ 最后剩下的那个元素。
**样例解释：**
令 $ \operatorname{sort}(a) $ 表示将数组 $ a $ 从小到大排序。
- 对于第一组数据，初始的 $ a = [1,10,100] $；第一次操作后，$ a = \operatorname{sort}([10-1,100-10]) = [9,90] $；第二次操作后，$ a = \operatorname{sort}([90-9]) = [81] $。所以答案是 $ 81 $。
- 对于第二组数据，初始的 $ a = [4,8,9,13] $；第一次操作后，$ a = \operatorname{sort}([8-4,9-8,13-9]) = [1,4,4] $；第二次操作后，$ a = \operatorname{sort}([4-1,4-4]) = [0,3] $；第三次操作后，$ a = \operatorname{sort}([3-0]) = [3] $。所以答案是 $ 3 $。**题目大意：** 给定一个初始长度为 $ n $ 的非负整数数组 $ a $，保证 $ a $ 是从小到大排序的。每次操作生成一个新数组 $ b_i = a_{i+1} - a_i $（对于 $ 1 \le i < n $），然后将 $ b $ 数组从小到大排序，用 $ b $ 替换 $ a $，并将 $ n $ 减 $ 1 $。执行 $ n-1 $ 次操作后，数组 $ a $ 只剩下一个元素，需要输出这个元素。 **输入数据格式：** 输入包含多组数据，第一行是一个正整数 $ t $（$ 1 \le t \le 10^4 $），表示数据组数。 对于每组数据： - 第一行是一个正整数 $ n $（$ 2 \le n \le 10^5 $），表示数组 $ a $ 的长度。 - 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 0 \le a_1 \le \ldots \le a_n \le 5 \times 10^5 $），表示数组 $ a $。 保证所有测试用例的 $ n $ 之和不超过 $ 2.5 \times 10^5 $，$ a_n $ 之和不超过 $ 5 \times 10^5 $。 **输出数据格式：** 对于每组数据，输出一行，包含数组 $ a $ 最后剩下的那个元素。 **样例解释：** 令 $ \operatorname{sort}(a) $ 表示将数组 $ a $ 从小到大排序。 - 对于第一组数据，初始的 $ a = [1,10,100] $；第一次操作后，$ a = \operatorname{sort}([10-1,100-10]) = [9,90] $；第二次操作后，$ a = \operatorname{sort}([90-9]) = [81] $。所以答案是 $ 81 $。 - 对于第二组数据，初始的 $ a = [4,8,9,13] $；第一次操作后，$ a = \operatorname{sort}([8-4,9-8,13-9]) = [1,4,4] $；第二次操作后，$ a = \operatorname{sort}([4-1,4-4]) = [0,3] $；第三次操作后，$ a = \operatorname{sort}([3-0]) = [3] $。所以答案是 $ 3 $。
给定一个初始长度为 $ n $ 的非负整数数组 $ a $，保证 $ a $ 是从小到大排序的。每次操作生成一个新数组 $ b_i = a_{i+1} - a_i $（对于 $ 1 \le i < n $），然后将 $ b $ 数组从小到大排序，用 $ b $ 替换 $ a $，并将 $ n $ 减 $ 1 $。执行 $ n-1 $ 次操作后，数组 $ a $ 只剩下一个元素，需要输出这个元素。
**输入数据格式：**
输入包含多组数据，第一行是一个正整数 $ t $（$ 1 \le t \le 10^4 $），表示数据组数。
对于每组数据：
- 第一行是一个正整数 $ n $（$ 2 \le n \le 10^5 $），表示数组 $ a $ 的长度。
- 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 0 \le a_1 \le \ldots \le a_n \le 5 \times 10^5 $），表示数组 $ a $。
保证所有测试用例的 $ n $ 之和不超过 $ 2.5 \times 10^5 $，$ a_n $ 之和不超过 $ 5 \times 10^5 $。
**输出数据格式：**
对于每组数据，输出一行，包含数组 $ a $ 最后剩下的那个元素。
**样例解释：**
令 $ \operatorname{sort}(a) $ 表示将数组 $ a $ 从小到大排序。
- 对于第一组数据，初始的 $ a = [1,10,100] $；第一次操作后，$ a = \operatorname{sort}([10-1,100-10]) = [9,90] $；第二次操作后，$ a = \operatorname{sort}([90-9]) = [81] $。所以答案是 $ 81 $。
- 对于第二组数据，初始的 $ a = [4,8,9,13] $；第一次操作后，$ a = \operatorname{sort}([8-4,9-8,13-9]) = [1,4,4] $；第二次操作后，$ a = \operatorname{sort}([4-1,4-4]) = [0,3] $；第三次操作后，$ a = \operatorname{sort}([3-0]) = [3] $。所以答案是 $ 3 $。**题目大意：** 给定一个初始长度为 $ n $ 的非负整数数组 $ a $，保证 $ a $ 是从小到大排序的。每次操作生成一个新数组 $ b_i = a_{i+1} - a_i $（对于 $ 1 \le i < n $），然后将 $ b $ 数组从小到大排序，用 $ b $ 替换 $ a $，并将 $ n $ 减 $ 1 $。执行 $ n-1 $ 次操作后，数组 $ a $ 只剩下一个元素，需要输出这个元素。 **输入数据格式：** 输入包含多组数据，第一行是一个正整数 $ t $（$ 1 \le t \le 10^4 $），表示数据组数。 对于每组数据： - 第一行是一个正整数 $ n $（$ 2 \le n \le 10^5 $），表示数组 $ a $ 的长度。 - 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $（$ 0 \le a_1 \le \ldots \le a_n \le 5 \times 10^5 $），表示数组 $ a $。 保证所有测试用例的 $ n $ 之和不超过 $ 2.5 \times 10^5 $，$ a_n $ 之和不超过 $ 5 \times 10^5 $。 **输出数据格式：** 对于每组数据，输出一行，包含数组 $ a $ 最后剩下的那个元素。 **样例解释：** 令 $ \operatorname{sort}(a) $ 表示将数组 $ a $ 从小到大排序。 - 对于第一组数据，初始的 $ a = [1,10,100] $；第一次操作后，$ a = \operatorname{sort}([10-1,100-10]) = [9,90] $；第二次操作后，$ a = \operatorname{sort}([90-9]) = [81] $。所以答案是 $ 81 $。 - 对于第二组数据，初始的 $ a = [4,8,9,13] $；第一次操作后，$ a = \operatorname{sort}([8-4,9-8,13-9]) = [1,4,4] $；第二次操作后，$ a = \operatorname{sort}([4-1,4-4]) = [0,3] $；第三次操作后，$ a = \operatorname{sort}([3-0]) = [3] $。所以答案是 $ 3 $。