题解：AT_arc220_d [ARC220D] Long Trail

· · 题解

更好的阅读体验

这题太好了，arc 的题目就该这样！

我们需要解决这样一个问题：在一个 n 点无向完全图上，找到一条边不重的路径 v_1 \rightsquigarrow v_k，使对于任意 i 有 |v_{i+2} - v_i| = 1 且 k \ge \frac{(n-2)^2}{2}。

先考虑一个很牛的转化。由于边不能重复经过，因此我们考虑将一条边 (i, j) 表示成 n \times n 的网格图中的一个格子。这里令 i < j，则所有格子应该会组成一个上三角，如下图中黑色折线以上的部分。 :::align{center} :::

我们希望知道题目要求的“路径”在这个网格图上表示为什么。考虑我们走的相邻两条边 (u, v) 和 (v, w)。由于 |u - w| = 1, v \not = u, v \not = w，则 v 要么同时小于 u, w，要么同时大于 v, w。这意味着这两条边所代表的格子要么位于同一行，要么位于同一列。更进一步地，由于 |u - w| = 1，因此这两个格子应该是在上下左右四个方向上相邻的格子。

因此我们看出完全图上的一条合法路径应该对应着网格图的一条不经过重复点的路径。而由于完全图经过的相邻三条边一定不会经过同一个点，因此网格图上的路径一定也不存在连续三个格子在同一行或者同一列，也就是说每走一步都必须改变一次方向。

就此，问题转化为，在 n-1 阶的上三角网格图中，选出一条经过的格子数不少于 \frac{(n-2)^2}{2} 的路径，使每一步行走的方向都和上一步不同。

我们假设网格图的高度为 x。我们接下来考虑上述这个问题的构造。首先分析一下限制：我们网格图上的点数是 \frac{n(n+1)}{2}，而限制是 \frac{(x-1)^2}{2}，也就是说我们总共只能浪费 1.5n + 1 个格子，结合下面的构造，你会发现这是一个卡得非常死的界。

\boldsymbol{x} 较小的情况

由于 x 比较小的情况比较特殊，我们先从这些情况开始构造。

当 x=1，由于只有一个格子，我们不动就可以了。

当 x=2，我们先向右走一步，再向下走一步，即可经过全部格子。

当 x=3，我们重复两次“向右走一步，再向下走一步”的过程，可以经过 5 个格子

当 x=4，同 x=3，重复三次“向右走一步，再向下走一步”的过程，可以经过 7 个格子，容易验证符合题意。

当 x=5，如下图构造，可经过 13 个格子。 :::align{center} :::

当 x=6，如下图构造，可经过 15 个格子。

:::align{center} :::

对于 x 比较大的情况，我们根据 x 的奇偶性进行分类讨论。

\boldsymbol{x} 为奇数

我们希望通过一些手法了来缩小 x 的规模。在这种情况下，我们从网格的左上角出发，每次砍掉上三角网格的前 4 行，然后又会到达下半部分的左上角，构造如图。

:::align{center} :::

容易发现，这样操作之后 x 都变成了 x-4。当 x<4 时我们套用 x 比较小的构造就可以了。我们分析一下这样浪费了多少个格子。容易发现，我们每让 x 减小 4，就会浪费 6 个格子，如图中蓝色 \boldsymbol {\color{0000FF} \times}。因此总共大约浪费 1.5n - O(1) 个格子，符合题目要求。

\boldsymbol{x} 为偶数

我们依然希望通过一些办法减小 x 变成规模更小的子问题，但是如果按照上面每次删除 4 行的话，由于多了一列，因此每让 x 减少 4 会浪费 10 个格子，不符合题意。

但是，聪明的人类发现，将这个阶梯状物的最外面一圈格子剥掉，里面还是一个完全一样的子问题。因此我们得到了一个非常巧妙的构造，如图。

:::align{center} :::

我们同样从左上角出发，图中红色折线就是我们的一次操作，让问题缩小到了黄色的部分，经过计算可知，这样的操作让 x 减少了 6。而我们浪费的格子有 9 个，如图中蓝色 \boldsymbol {\color{0000FF} \times}。这意味着，每让 x 减少 6，会浪费 9 个格子，最后浪费的格子数依然是 1.5 n - O(1)，同样符合题目要求！

得到格子上的路径后，我们容易根据这个求出完全图上的路径。至此，问题在 O(n^2) 的时间内得到解决。

#include<bits/stdc++.h>
#define endl '\n'
#define N 1006
using namespace std;
constexpr int dx[]={0,0,1,-1},dy[]={1,-1,0,0}; //R L D U
//R: 0, L: 1, D: 2, U: 3
int n;
vector<int> vec,ans;
inline void R() {vec.push_back(0);}
inline void L() {vec.push_back(1);}
inline void D() {vec.push_back(2);}
inline void U() {vec.push_back(3);}
void solve(int x)
{
  if(x==1)return;
  if(x==2)return R(),D();
  if(x==3)return R(),D(),R(),D();
  if(x==4)return R(),D(),R(),D(),R(),D();
  if(x==5)return R(),D(),R(),U(),R(),D(),R(),D(),L(),D(),R(),D();
  if(x==6)return R(),D(),R(),U(),R(),D(),R(),D(),L(),D(),R(),D(),R(),D();
  if(x&1)
  {
    for(int i=1;i<=(x-3)/2;i++)R(),D(),R(),U();
    R(),D(),R(),D(),L(),D(),L();
    for(int i=1;i<=(x-7)/2;i++)U(),L(),D(),L();
    D(),solve(x-4);
  } else {
    for(int i=1;i<=x-3;i++)R(),D();
    R(),U();
    for(int i=1;i<=(x-4)/2;i++)R(),U(),L(),U();
    for(int i=1;i<=(x-8)/2;i++)L(),D(),L(),U();
    L(),D(),L(),D(),solve(x-6);
  }
}
void solve()
{
  scanf("%d",&n),vec.clear(),ans.clear();
  solve(n-1),ans.push_back(2);
  int x=1,y=2;
  for(int i:vec)
  {
    if(i<2)ans.push_back(x);
    else ans.push_back(y);
    x+=dx[i],y+=dy[i];
  }
  assert(ans.size()*2>=(n-2)*(n-2));
  printf("%d\n",(int)ans.size());
  for(int i:ans)printf("%d ",i);
  putchar(10);
}
main()
{
  int T; scanf("%d",&T);
  while(T--)solve();
  return 0;
}