QOJ.ac

QOJ

Límite de tiempo: 2.0 s Límite de memoria: 1024 MB Puntuación total: 100 Hackeable ✓

#10981. LIS 三角形

Estadísticas

给定三个正整数 $N, K$ 和 $L$。你的任务是确定是否存在一个长度为 $N$ 的整数序列 $P$,满足以下所有条件。如果存在这样的序列,请输出其中一个。

  • $P$ 是序列 $(K, K + 1, \dots, K + N - 1)$ 的一个排列。
  • $P$ 的最长上升子序列*的长度恰好为 $L$。
  • 对于每个满足 $1 \le i \le N - 2$ 的整数 $i$,以 $P_i, P_{i+1}$ 和 $P_{i+2}$ 为边长可以构成一个非退化三角形$^\dagger$。

你有 $T$ 组测试数据。请分别回答每组测试数据。

输入格式

输入按以下格式给出:

$T$ $case_1$ $case_2$ $\vdots$ $case_T$

每组测试数据按以下格式给出:

$N \ K \ L$

  • 所有输入值均为整数。
  • $1 \le T \le 50000$。
  • $3 \le N \le 2 \times 10^5$。
  • $1 \le K \le 2 \times 10^5$。
  • $1 \le L \le N$。
  • 所有测试数据的 $N$ 之和不超过 $2 \times 10^5$。

输出格式

如果不存在满足所有条件的序列 $P$,输出:

No

否则,输出:

Yes $P_1 \ P_2 \ \dots \ P_N$

任何满足所有条件的有效序列 $P$ 均可被接受。


*序列 $P$ 的子序列是指通过删除零个或多个元素而不改变剩余元素顺序所形成的序列。$P$ 的最长上升子序列是 $P$ 的一个严格递增子序列,其长度达到最大可能值。 $^\dagger$非退化三角形是指三个顶点不在同一直线上的三角形。

样例

输入 1

3
6 3 4
5 5 5
7 1 2

输出 1

Yes
3 6 4 7 5 8
Yes
5 6 7 8 9
No

说明

在第一个样例中,一个有效的序列是 $P = (3, 6, 4, 7, 5, 8)$。可能还存在其他有效序列。 在第二个样例中,唯一的有效序列是 $P = (5, 6, 7, 8, 9)$。 在第三个样例中,不存在满足所有条件的序列 $P$。

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.