已结束 GESP挑战赛#1
← 上一题 下一题 →

A1767 | 算术排列

时间限制1s
内存限制128MB
通过 / 提交0/0

题目描述

给你一个包含 $n$ 个正整数的数组 $a$ ,你可以对其执行以下操作。

每次操作,你可以选择数组中的任意一个元素 $a_i$ 并使用 $\lfloor \frac{a_i}{2} \rfloor$ 替换它,也就是 $a_i$ 除以 $2$ 的整数部分(向下取整)。

试试看,如果你可以执行任意次上述操作,是否能够使数组 $a$ 变为数字 $1$ 到 $n$ 的一个排列--也就是说使数组 $a$ 包含 $1$ 到 $n$ 之间的所有整数,每个数字正好出现一次。

比如如果 $a = [1, 8, 25, 42], n = 4$ ,你可以对其进行以下操作:

1. 将 $8$ 替换为 $\lfloor \frac{8}{2} \rfloor = 4$,然后 $a = [1, 4, 25, 2]$;
2. 将 $25$ 替换为 $\lfloor \frac{25}{2} \rfloor = 12$,然后 $a = [1, 4, 12, 2]$;
3. 将 $12$ 替换为 $\lfloor \frac{12}{2} \rfloor = 6$,然后 $a = [1, 4, 6, 2]$;
4. 将 $6$ 替换为 $\lfloor \frac{6}{2} \rfloor = 3$,然后 $a = [1, 4, 3, 2]$。

输入格式

输入的第一行为一个正整数 $t (1 \le t \le 10^4)$ 表示共有 $t$ 个测试用例 。

对于每个测试用例第一行为一个整数 $n (1 \le n \le 50)$ 表示数组的大小;第二行有 $n$ 个正整数 $a_i (1 \le a_i \le 10^9)$ 。

输出格式

对于每个测试用例,如果能够执行上述操作使得 $a$ 成为 $1$ 到 $n$ 的一个排列则输出 $\tt{YES}$ 否则输出 $\tt{NO}$ 。

你可以输出 $\tt{YES}$ 和 $\tt{NO}$ 的任意大小写形式(例如,字符串 $\tt{yEs}$、$\tt{yes}$、$\tt{Yes}$ 和 $\tt{YES}$ 都会被视为正确答案)。

输入输出样例

输入 #1
6
4
1 8 25 2
2
1 1
9
9 8 3 4 2 7 1 5 6
3
8 2 1
4
24 7 16 7
5
22 6 22 4 22
输出 #1
YES
NO
YES
NO
NO
YES
C++ 编辑器
输入
输出