题解：Atcoder Regular Contest++ 220 D - Long Trail

题目描述给定正整数n，考虑一个包含1,2,…,n共n个顶点的无向完全图（任意两点间都有且仅有一条无向边）。你需要构造一条顶点序列v₁,v₂,…,vₖ，满足以下两个核心条件：边不重复：序列中所有相邻点对对应的边互不相同，即每条边最多走一次。奇偶间隔约束：对所有合法的i，满足|vᵢ₊₂ − vᵢ| = 1。通俗来说：隔一个位置的两个数一定相差 1。同时要求路径长度满足下界：$k \ge \dfrac{(n-2)^2}{2}$。输出格式第一行输出序列长度k；第二行输出合法的顶点序列v₁ v₂ … vₖ。数据范围$3 \le n \le 1000$。解题思路1. 图论转网格模型（本题核心）我们将完全图的每条边(i,j) (ij)映射为上三角网格的一个格子。此时原题的所有约束可以完美等价转化：边不重复→ 网格中走过的格子不重复；隔位差1约束→ 网格行走必须严格横、竖交替换向（横→竖→横→竖……）；路径长度下界→ 只需遍历足够多的网格格子，满足数量要求即可。2. 分规模构造策略针对不同大小的n，采