题解：AT_agc077_b [AGC077B] Long Increasing Walk

· · 题解

更好的阅读体验

这应是我第一次独立做出黑题！这是一个思路和实现都比其他题解简单的做法。

我们需要解决这样一个问题：给一个左右各 n 个点的完全二分图上的 n^2 条边分别确定边权，使最长上升路径的长度恰好为 k，或报告无解。

首先如果见过 arc220d 的 trick 就会知道，完全图上的一条边可以看作网格图上的一个格子；完全二分图也可以。考虑一条完全二分图上的路径在网格上表现为什么：假设边 (l_i, r_j) 代表格子 (i, j)，格子的权值就是 (l_i, r_j) 这条边的边权，那么一条二分图上的路径，一定可以看作网格图上的一条“路径”，使相继经过的两个格子在同一行或同一列，且横着走和竖着走交替进行，且所经过的格子权值递增。

那么我们先考虑判断无解的问题。先考虑答案下界，我们声称，对于左右各 n 个点的完全二分图，其最长上升路径的长度，至少为 n。

考虑假如给定了二分图上每条边的边权数组 a，我们应该如何求出这个二分图的最长上升路径？

假设 f_{i, j, 0/1} 表示以 (i, j) 结束的路径，最后一步是横向/纵向移动，的最长上升路径。

那么我们先将所有 f 赋值为 -\infty。然后按照 a_{x, y} 从小到大遍历每个格子 (x, y)。

注意到 f_{x, y, 0} 的转移实际上与 x 无关，因此考虑直接记为 f_{y, 0}；f_{x, y, 1} 的转移与 y 无关，因此直接记为 f_{x, 1}。

接下来考虑 f_{y, 0} + f_{x, 1} 这个东西。容易发现，

f_{y, 0} + f_{x, 1} = \max\limits _i\left({f_{i,1} + 1}\right) + \max\limits _i\left({f_{i,0} + 1}\right) = \max_{i, j} \left(f_{i, 0} + f_{j, 1} + 2\right)

因此对于最后一个格子 (x, y) 所在行和所在列的 2n 个格子（(x, y) 要计算两次），以它们为结尾的路径长度之和为 2n^2，也就是说，一定存在一个格子，存在以它结尾、长度 \ge n 的路径。

至于为什么最小值恰好为 n，下文的构造将会给出验证。

接下来考虑上界。对于上界，我们可以先取出图中最长的一条路径（假设长度为 L），然后在这条路径上依次填上 1 \sim L 即可。

那么当 n 是偶数，图中存在欧拉回路，因此答案上界为 n^2；当 n 是奇数，要删除一些边使原图存在欧拉路。容易计算删除的边数为 n-1。

因此有解条件是，k \ge n，且 k \le n^2（n 为偶数），或 k \le n^2 - (n-1)（n 为奇数）。

接下来考虑构造。

首先我们考虑将 n^2 个格子分成 k 个等价类，每个等价类内部两两不能到达，而第 i 个等价类能够到达第 i+1 个等价类。那么我们只需要保证第 i+1 个等价类的最小值 > 第 i 个等价类的最大值，就可以保证我们从第 i 个等价类进入第 i+1 个等价类后，再也不会回到编号更小的等价类，这样就可以保证最长上升路径的长度恰好是 k。这便是本题中我们构造的总体思路。

考虑得到一个具体的方案。首先当 k=n，那就是说我们要将 n^2 个格子分成 n 组且两两不能到达。那么容易想到根据对角线来进行构造。更具体地，我们按照 (i + j) \bmod n 来划分等价类，那么显然每个等价类中，每行、每列各有一个格子，是符合要求的。

再考虑 k = n^2（偶数）的情况。则此时一个格子就是一个等价类，可以从 (1, 1) 出发，如图构造。图中只展示了这条路径的前半部分。

那么对于一般的 k 要如何构造呢？仍然考虑找到一条长度为 k 的路径，并且我们希望这条路径是最长的。那么我们可以先取出路径上的 k-n 个格子，让它们每个格子分别形成一个等价类。剩下的 n 个格子，按照 k = n 的方法划分等价类，以覆盖整个网格。

这么做需要满足一个条件，就是剩下的 n 个格子所属的等价类必须各不相同。因此我们从 (1, 1) 出发，最开始走到的 n 个格子一定满足这些格子所对应得对角线能够覆盖整个网格！如图进行构造即可。红色的格子表示单独成为一个等价类的格子；不为红色的格子中，颜色相同的表示位于同一个等价类中。

那么这道题就做完了！时间复杂度 O(n^2)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 706
using namespace std;
int n,k,ans[N][N],vis[N][N];
vector<int> col;
vector<pair<int,int> > g[N];
void solve()
{
  scanf("%d%d",&n,&k);
  if(k<n||n&1&&k>n*n-n+1)
    return printf("No\n"),(void)0;
  if(n==1)
    return printf("Yes\n1\n"),(void)0;
  for(int i=0;i<=n;i++)g[i].clear();
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)g[(i+j)%n].push_back({i,j}),ans[i][j]=vis[i][j]=0;
  int i=1,j=1,lst=-1,st=1,tot=0,c=k-n;
  for(col.clear();tot<k;tot++)
  {
    if(j==1&&lst==0) {
      i=st=(st+1)%n+1,lst=1;
      while(vis[i][j])i=i%n+1;
    } else if(lst==0)i=i%n+1,lst=1;
    else if(lst==1)j=j%n+1,lst=0;
    else lst=1;
    if(tot<n)col.push_back((i+j)%n);
    else ans[i][j]=c--;
    vis[i][j]=1;
  }
  reverse(col.begin(),col.end()),tot=k-n;
  for(int i:col)for(auto j:g[i])
    if(!ans[j.first][j.second])ans[j.first][j.second]=++tot;
  printf("Yes\n");
  for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)printf("%d%c",ans[i][j]," \n"[j==n]);
}
main()
{
  int T; scanf("%d",&T);
  while(T--)solve();
  return 0;
}