#d. 构造排列

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d
    Type: Default 1000ms 256MiB

构造排列

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

排列（组合数学术语）_百度百科 (baidu.com)

一个长度为 nn 的排列是一个包含 1∼n1 \sim n 所有元素的 nn 个数的一个序列, 比如 [4,2,1,3][4, 2, 1, 3] 是一个排列, 而 [3,2,1,2][3, 2, 1, 2] 或者 [1,4,3][1, 4, 3] 都不是排列.

题目描述

我们规定, 两个序列相加的含义为对应下标的元素相加, 即 Ci=Ai+BiC_i = A_i + B_i

例如我们有两个排列 [4,1,3,2,1][4, 1, 3, 2, 1] 和 [1,3,0,0,0][1, 3, 0, 0, 0], 相加之后为 [5,4,3,2,1][5, 4, 3, 2, 1]

我们现在想知道, 给你一个序列 AA, 你能否构造一个序列 BB, 其中 BB 的每一个元素都是非负整数, 使得 A+BA + B 得到的 CC 序列是一个排列.

输入格式

第一行一个整数 tt, 表示有 tt 组数据

接下来 tt 组数据, 每组数据的第一行为一个元素 nn, 表示 AA 序列有 nn 个元素, 第二行为 nn 个元素 aia_i.

输出格式

对于每一组数据, 如果我们能找到一个非负整数序列 BB, 我们输出 YES, 否则输出 NO

样例 #1

样例输入 #1

4
5
4 1 3 2 1
5
2 4 3 4 2
1
1
6
1 1 1 1 6 6

样例输出 #1

YES
NO
YES
NO

提示

  • 1 ≤ t≤ 103 1\ \leq\ t \leq \ 10^3
  • 1 ≤ n≤ 105 1\ \leq\ n \leq \ 10^5
  • 1 ≤ ai≤ n 1\ \leq\ a_i \leq \ n

北辰杯贺岁杯考前模拟赛

Not Attended
Status
Done
Rule
Ledo
Problem
36
Start at
2025-1-3 18:00
End at
2025-1-20 10:00
Duration
400 hour(s)
Host
Partic.
111
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 16ms
  • Powered by Hydro v4.9.27 Community