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]$。
每次操作,你可以选择数组中的任意一个元素 $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)$ 。
对于每个测试用例第一行为一个整数 $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}$ 都会被视为正确答案)。
你可以输出 $\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++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?