跳到主要内容

P5335. 小美的三角形图游走

场次：2026年9月1日 · 来源：CodeFun2000 P5335

题目描述​

层台景区把观景栈道按三角形分层铺设。封园前巡检组必须从指定台位出发，把每一段栈道恰好走一遍后再回到起点，才能确认廊道全部可通行。栈道的接法由园方巡检规程固定：同层相邻台位之间有栈道，相邻两层之间再按小三角补上两条斜向栈道。在本题给出的层数范围内，这样的巡回路线一定存在。

巡检区域共有 hh 层。第 rr 层有 rr 个台位，从左到右编号依次为 r(r−1)2+1, r(r−1)2+2, …, r(r−1)2+r\frac{r(r-1)}{2}+1,\ \frac{r(r-1)}{2}+2,\ \ldots,\ \frac{r(r-1)}{2}+r。

当 2≤r≤h2 \le r \le h 时，对每个 1≤c<r1 \le c < r，下列三段栈道都存在（无向）：

  • 同层相邻：编号为 r(r−1)2+c\frac{r(r-1)}{2}+c 与 r(r−1)2+c+1\frac{r(r-1)}{2}+c+1 的台位之间；
  • 连向上一层：编号为 r(r−1)2+c\frac{r(r-1)}{2}+c 与 (r−1)(r−2)2+c\frac{(r-1)(r-2)}{2}+c 的台位之间；
  • 另一条斜向：编号为 r(r−1)2+c+1\frac{r(r-1)}{2}+c+1 与 (r−1)(r−2)2+c\frac{(r-1)(r-2)}{2}+c 的台位之间。

请给出一条从台位 ss 出发、每段栈道恰好经过一次、并回到 ss 的巡回。若有多种走法，输出任意一种即可。

层数满足 2≤h≤1032 \le h \le 10^3，出发台位满足 1≤s≤h(h+1)/21 \le s \le h(h+1)/2。一次输入中任务数 kk 满足 1≤k≤5×1011 \le k \le 5 \times 10^1，且所有任务的 hh 之和不超过 10310^3。

输入格式​

第一行一个整数 kk（1≤k≤501 \le k \le 50），表示随后的巡检任务数量。

接下来 kk 行，每行两个整数 hh、ss（2≤h≤1032 \le h \le 10^3，1≤s≤h(h+1)/21 \le s \le h(h+1)/2），表示该次任务的层数和出发台位。

保证所有任务的 hh 之和不超过 10310^3。

输出格式​

对每个任务输出一行，包含 3×h×(h−1)/2+13 \times h \times (h-1)/2+1 个整数，依次给出巡回经过的台位编号（第一个和最后一个都必须是 ss）。

若存在多种合法路线，输出任意一种即可。评测会判定路线是否走遍每段栈道恰好一次。

示例​

示例 1​

输入：

1
2 3

输出：

3 2 1 3

说明：

只有 2 层，三个台位 1、2、3 构成一个三角形，共 3 段栈道。从 3 出发，依次走 3→23\to 2、2→12\to 1、1→31\to 3，每段恰好一次并回到起点。路径上应有 3×2×1/2+1=43\times 2\times 1/2+1=4 个编号。

示例 2​

输入：

1
3 4

输出：

4 5 2 3 5 6 3 1 2 4

说明：

3 层共 9 段栈道。从底层左侧台位 4 出发的一条合法巡回是 4→5→2→3→5→6→3→1→2→44\to 5\to 2\to 3\to 5\to 6\to 3\to 1\to 2\to 4。 相邻编号都是规程里的栈道，且九段各出现一次，首尾都是 4。

示例 3​

输入：

2
2 2
4 7

输出：

2 3 1 2
7 8 4 5 2 3 5 6 9 8 5 9 10 6 3 1 2 4 7

说明：

  • 第一项任务只有 2 层，从台位 2 出发，走 2→3→1→22\to 3\to 1\to 2 即可。
  • 第二项任务有 4 层、18 段栈道，从台位 7 出发给出一条长为 19 的巡回；评测只要求每段栈道恰好经过一次，不要求与该输出逐点相同。
加载评论中...