308077: CF1463D. Pairs

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Pairs

题意翻译

## 题目描述 你有 $2n$ 个整数 $1,2,\cdots,2n$,你需要将其分成 $n$ 对,然后选择其中 $x$ 对,取出其中的较小数,并取出其余 $n-x$ 对中的较大数,使得最终取出的数组成的集合为 $\{b_1,b_2,\cdots,b_n\}$。问有多少个满足题意的 $x$。 数据范围:$1 \le t \le 1000$,$\sum n \le 2 \cdot 10^5$。 ## 输入格式 输入形如: $t$ $case_1$ $case_2$ $\vdots$ $case_t$ 其中 $case_i$ 表示第 $i$ 组数据,具体形如: $n$ $b_1,b_2,\cdots,b_n$ ## 输出格式 输出形如: $ans_1$ $ans_2$ $\vdots$ $ans_t$ 其中 $ans_i$ 表示第 $i$ 组数据的答案。 ## 样例解释 在第一组数据中,只有 $x=1$ 符合题意:取 $(1,2)$ 的较小数。 在第二组数据中,$x=1,2,3$ 符合题意,具体方案如下: 若 $x=1$,将所有数分成 $(1,6)$,$(2,4)$,$(3,5)$,$(7,9)$,$(8,10)$,取 $(1,6)$ 的较小数和其余对的较大数。 若 $x=2$,将所有数分成 $(1,2)$,$(3,4)$,$(5,6)$,$(7,9)$,$(8,10)$,取 $(1,2)$,$(5,6)$ 的较小数和其余对的较大数。 若 $x=3$,将所有数分成 $(1,3)$,$(4,6)$,$(5,7)$,$(2,9)$,$(8,10)$,取 $(1,3)$,$(4,6)$,$(5,7)$ 的较小数和其余对的较大数。 在第三组数据中,只有 $x=0$ 符合题意:将所有数分成 $(1,3)$,$(2,4)$,取这两对的较大数。

题目描述

You have $ 2n $ integers $ 1, 2, \dots, 2n $ . You have to redistribute these $ 2n $ elements into $ n $ pairs. After that, you choose $ x $ pairs and take minimum elements from them, and from the other $ n - x $ pairs, you take maximum elements. Your goal is to obtain the set of numbers $ \{b_1, b_2, \dots, b_n\} $ as the result of taking elements from the pairs. What is the number of different $ x $ -s ( $ 0 \le x \le n $ ) such that it's possible to obtain the set $ b $ if for each $ x $ you can choose how to distribute numbers into pairs and from which $ x $ pairs choose minimum elements?

输入输出格式

输入格式


The first line contains a single integer $ t $ ( $ 1 \le t \le 1000 $ ) — the number of test cases. The first line of each test case contains the integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ). The second line of each test case contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ 1 \le b_1 < b_2 < \dots < b_n \le 2n $ ) — the set you'd like to get. It's guaranteed that the sum of $ n $ over test cases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式


For each test case, print one number — the number of different $ x $ -s such that it's possible to obtain the set $ b $ .

输入输出样例

输入样例 #1

3
1
1
5
1 4 5 9 10
2
3 4

输出样例 #1

1
3
1

说明

In the first test case, $ x = 1 $ is the only option: you have one pair $ (1, 2) $ and choose the minimum from this pair. In the second test case, there are three possible $ x $ -s. If $ x = 1 $ , then you can form the following pairs: $ (1, 6) $ , $ (2, 4) $ , $ (3, 5) $ , $ (7, 9) $ , $ (8, 10) $ . You can take minimum from $ (1, 6) $ (equal to $ 1 $ ) and the maximum elements from all other pairs to get set $ b $ . If $ x = 2 $ , you can form pairs $ (1, 2) $ , $ (3, 4) $ , $ (5, 6) $ , $ (7, 9) $ , $ (8, 10) $ and take the minimum elements from $ (1, 2) $ , $ (5, 6) $ and the maximum elements from the other pairs. If $ x = 3 $ , you can form pairs $ (1, 3) $ , $ (4, 6) $ , $ (5, 7) $ , $ (2, 9) $ , $ (8, 10) $ and take the minimum elements from $ (1, 3) $ , $ (4, 6) $ , $ (5, 7) $ . In the third test case, $ x = 0 $ is the only option: you can form pairs $ (1, 3) $ , $ (2, 4) $ and take the maximum elements from both of them.

Input

题意翻译

## 题目描述 你有 $2n$ 个整数 $1,2,\cdots,2n$,你需要将其分成 $n$ 对,然后选择其中 $x$ 对,取出其中的较小数,并取出其余 $n-x$ 对中的较大数,使得最终取出的数组成的集合为 $\{b_1,b_2,\cdots,b_n\}$。问有多少个满足题意的 $x$。 数据范围:$1 \le t \le 1000$,$\sum n \le 2 \cdot 10^5$。 ## 输入格式 输入形如: $t$ $case_1$ $case_2$ $\vdots$ $case_t$ 其中 $case_i$ 表示第 $i$ 组数据,具体形如: $n$ $b_1,b_2,\cdots,b_n$ ## 输出格式 输出形如: $ans_1$ $ans_2$ $\vdots$ $ans_t$ 其中 $ans_i$ 表示第 $i$ 组数据的答案。 ## 样例解释 在第一组数据中,只有 $x=1$ 符合题意:取 $(1,2)$ 的较小数。 在第二组数据中,$x=1,2,3$ 符合题意,具体方案如下: 若 $x=1$,将所有数分成 $(1,6)$,$(2,4)$,$(3,5)$,$(7,9)$,$(8,10)$,取 $(1,6)$ 的较小数和其余对的较大数。 若 $x=2$,将所有数分成 $(1,2)$,$(3,4)$,$(5,6)$,$(7,9)$,$(8,10)$,取 $(1,2)$,$(5,6)$ 的较小数和其余对的较大数。 若 $x=3$,将所有数分成 $(1,3)$,$(4,6)$,$(5,7)$,$(2,9)$,$(8,10)$,取 $(1,3)$,$(4,6)$,$(5,7)$ 的较小数和其余对的较大数。 在第三组数据中,只有 $x=0$ 符合题意:将所有数分成 $(1,3)$,$(2,4)$,取这两对的较大数。

加入题单

上一题 下一题 算法标签: