A1446 | 美丽数字
时间限制1s
内存限制128MB
通过 / 提交0/0
题目描述
给定 $1$ ~ $n$ 的一个全排列 $a_1$ ~ $a_n$,如果存在两个下标 $l$ 和 $r$ ($1 \le l \le r \le n$)使得 $[a_l, a_{l+1}......a_r]$ 是 $m$ 的一个全排列,我们称数字 $m$ ($1 \le m \le n$)是美丽的。
例如,$a = [4,5,1,3,2,6]$,
* $l = 3$,$r = 3$,对于 $m = 1$,$a_3$ 是 $m$ 的一个全排列。
* $l = 3$,$r = 5$,对于 $m = 3$,$a_3,a_4,a_5$ 是 $m$ 的一个全排列。
* $l = 1$,$r = 5$,对于 $m = 5$,$a_1,a_2,a_3,a_4,a_5$ 是 $m$ 的一个全排列。
* $l = 1$,$r = 6$,对于 $m = 6$,$a_1$~$a_6$ 是 $m$ 的一个全排列。
而 $m = 2$ 和 $m = 4$,不存在 $l$ 和 $r$,使 $a_l$ ~ $a_r$ 为 $m$ 的全排列。
给定 $1$ ~ $n$ 的一个全排列,对于所有的 $m$,判断它是否是一个美丽数字。
例如,$a = [4,5,1,3,2,6]$,
* $l = 3$,$r = 3$,对于 $m = 1$,$a_3$ 是 $m$ 的一个全排列。
* $l = 3$,$r = 5$,对于 $m = 3$,$a_3,a_4,a_5$ 是 $m$ 的一个全排列。
* $l = 1$,$r = 5$,对于 $m = 5$,$a_1,a_2,a_3,a_4,a_5$ 是 $m$ 的一个全排列。
* $l = 1$,$r = 6$,对于 $m = 6$,$a_1$~$a_6$ 是 $m$ 的一个全排列。
而 $m = 2$ 和 $m = 4$,不存在 $l$ 和 $r$,使 $a_l$ ~ $a_r$ 为 $m$ 的全排列。
给定 $1$ ~ $n$ 的一个全排列,对于所有的 $m$,判断它是否是一个美丽数字。
输入格式
第一行包含唯一的整数 ($1 \le T \le 100$) — 表示测试用例的数量
每个测试用例的第一行包含一个数字 $n$ ($1 \le n \le 2 \times 10^5$)。
下一行包含 $n$ 整数 $a_1$ ~ $a_n$。
每个测试用例的第一行包含一个数字 $n$ ($1 \le n \le 2 \times 10^5$)。
下一行包含 $n$ 整数 $a_1$ ~ $a_n$。
输出格式
对于每个测试用例输出一个 $01$ 字符串,如果 $m = i$ 时 $m$ 是美丽的,则字符串的第 $i$ 位是
1,否则为 0。($1 \le i \le n$)输入输出样例
输入 #1
3 6 4 5 1 3 2 6 5 5 3 1 2 4 4 1 4 3 2
输出 #1
101011 11111 1001
在第二个测试用例中:
* $l = 3$ 和 $r = 3$ $[1]$ 为 $m = 1$ 的全排列。
* $l = 3$ 和 $r = 4$ $[1,2]$ 为 $m = 2$ 的全排列。
* $l = 2$ 和 $r = 4$ $[3,1,2]$ 为 $m = 3$ 的全排列。
* $l = 2$ 和 $r = 5$ $[3,1,2,4]$ 为 $m = 4$ 的全排列。
* $l = 1$ 和 $r = 5$ $[5,3,1,2,4]$ 为 $m = 5$ 的全排列。
* $l = 3$ 和 $r = 3$ $[1]$ 为 $m = 1$ 的全排列。
* $l = 3$ 和 $r = 4$ $[1,2]$ 为 $m = 2$ 的全排列。
* $l = 2$ 和 $r = 4$ $[3,1,2]$ 为 $m = 3$ 的全排列。
* $l = 2$ 和 $r = 5$ $[3,1,2,4]$ 为 $m = 4$ 的全排列。
* $l = 1$ 和 $r = 5$ $[5,3,1,2,4]$ 为 $m = 5$ 的全排列。
C++ 编辑器
输入
输出
可保存默认模板;新题优先使用已保存模板。
当前快捷键仅展示,暂不支持修改。
- 撤销
Ctrl / ⌘ + Z - 重做
Ctrl / ⌘ + Y - 查找
Ctrl / ⌘ + F - 全选
Ctrl / ⌘ + A - 复制
Ctrl / ⌘ + C - 剪切
Ctrl / ⌘ + X - 粘贴
Ctrl / ⌘ + V - 自动排版
工具栏排版按钮 - 草稿保存
编辑时自动保存到本机
历史
提交记录
状态说明时间源码
AI
作答助手
你好,我是作答助手。可以问思路、复杂度、样例含义或代码报错原因;不会直接给出完整 AC 代码。
确定要清空代码吗?