题解：AT_agc077_e [AGC077E] Hamiltonian Path Inversion

· · 题解

更好的阅读体验

？？？？？？？？？被打的措手不及。

我们需要解决这样一个问题：构造一个 4 \times w 的 01 矩阵，使得对于 \forall n \isin [0, 999900]，都存在这个矩阵的一个欧拉路径，使得路径上经过的数字组成的序列，逆序对数恰好为 n。对于一些 n，你被要求构造方案。

首先考虑假设我们现在有一个 01 串 S，如何让它的逆序对数增加 1。答案是，将一对相邻的 01 修改成 10。容易发现，这样操作对这两个位置之前和之后的逆序对都是没有影响的；而 01 变成 10 增加了一对逆序对。因此这么做是符合要求的。

那么我们为了方便处理，我们希望，对于相邻的 n，我们路径上构成的 01 串不要相差太大。这启发我们，可以令 n=0 时的 S = 00\cdots011\cdots1，然后每次要让 n 增加 1 时，我们找到字符串中最后一个 01 子串，然后将这个字串修改成 10 就可以了。假设 1 的数量是 k，那么一个 0 将会被操作 k 次。

那么我们考虑标记 S 中一个长度为 k+1 的一个连续段。如果 S 中的所有 1 不构成一个连续段，那么我们就标记第一个 1 和最后一个 1 之间的区域，如 0000\color{red}11101\color{black}00；如果所有 1 构成一个连续段，我们就标记这个连续段，以及连续段之前的那个 0，如 0000\color{red}01111\color{black}00。我们会发现，每个被标记的连通块都恰好有一个 0 和 k 个 1。而我们考虑一次“翻转转最后一个 01”的操作会改变什么：

这启发我们，我们可以将 4 \times w 的网格分成内圈和外圈，外圈就是第一行、第四行、第一列、第 w 列构成的区域，内圈就是其余的部分。我们可以用内圈来得到被标记区间的 01 串，用外圈得到剩余部分。仍然是因为被标记区间只有一个 0，因此我们可以得到一个非常巧妙的构造：

\begin{gather} 00000\cdots00000 \nonumber \\ 0\color{red}0111 \cdots 1111\color{black}0 \nonumber \\ 0\color{red}1111 \cdots 1111\color{black}0 \nonumber \\ 00000\cdots00000 \nonumber \end{gather}

考虑我们最终的路径是长什么样的：应该是在外圈走一些 0，然后到内圈走一个“一个 0 镶嵌在 2w - 5 个 1”中的路径，最后再回到外圈走完剩下的 0。当 n 是已知的时候，我们被标记区间在整个 01 串中的位置，以及 0 在被标记区间的位置都是已知的。

由标记区间中 0 的位置，我们可以知道要从哪个位置进入内圈，进而也可以知道从哪个位置走出内圈；由标记区间在整个 01 串中的位置我们可以知道在进入内圈之前我们走了多少个 0；走出内圈后我们将之前没走过的 0 走一遍就好了！如果难以理解本段的构造方法，在题解的最后一张 editorial 里的动图，我认为可以很好地帮助理解。

那么当 w = 500 的时候，我们总共有 2 \times 498 - 1 = 995 个 1，最多可以产生 995 \times (2000 - 995) = 999975 个逆序对，并且 n 可以取遍 [0, 999975] 内的每个值，因此符合题目要求。

假设 4 = O(1)，单次构造的复杂度是 O(w)，问题得到解决。

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
int h,w,q,n,c1;
vector<pair<int,int> > walk_out1(int x,int y,int k)
{
  vector<pair<int,int> > ret;
  for(int i=1;i<=k;i++)
  {
    ret.push_back({x,y});
    if(x==1&&y>1)y--;
    else if(y==1&&x<h)x++;
    else if(x==h&&y<w)y++;
    else if(y==w&&x>1)x--;
  }
  return ret;
}
vector<pair<int,int> > walk_out2(int x,int y,int k)
{
  vector<pair<int,int> > ret;
  for(int i=1;i<=k;i++)
  {
    ret.push_back({x,y});
    if(x==h&&y>1)y--;
    else if(y==w&&x<h)x++;
    else if(x==1&&y<w)y++;
    else if(y==1&&x>1)x--;
  }
  return ret;
}
vector<pair<int,int> > walk_in(int x,int y,int k)
{
  vector<pair<int,int> > ret;
  for(int i=1;i<=k;i++)
  {
    ret.push_back({x,y});
    if(x==2&&y>2)y--;
    else if(y==2&&x<h-1)x++;
    else if(x==h-1&&y<w-1)y++;
    else if(y==w-1&&x>2)x--;
  }
  return ret;
}
void get_out(int &ix,int &iy,int &ox,int &oy)
{
  if(ix==ox&&ix==2)ix--,ox--;
  else if(ix==ox&&ix==h-1)ix++,ox++;
  else if(iy==oy&&iy==2)iy--,oy--;
  else if(iy==oy&&iy==w-1)iy++,oy++;
}
void solve()
{
  scanf("%d",&n);
  int fr=h*w-c1-n/c1-1,num=n%c1;
  auto in=walk_in(2,2,num+2);
  int x_out=in.back().first,y_out=in.back().second;
  in=walk_in(x_out,y_out,c1+1);
  int x_in=in.back().first,y_in=in.back().second;
  reverse(in.begin(),in.end());
  get_out(x_in,y_in,x_out,y_out);
  auto out1=walk_out2(x_in,y_in,fr);
  reverse(out1.begin(),out1.end());
  auto out2=walk_out1(x_out,y_out,h*w-c1-1-fr);
  for(auto i:out1)printf("%d %d\n",i.first,i.second),fflush(stdout);
  for(auto i:in)printf("%d %d\n",i.first,i.second),fflush(stdout);
  for(auto i:out2)printf("%d %d\n",i.first,i.second),fflush(stdout);
}
void construct()
{
  for(int i=1;i<=w;i++)putchar('0');
  putchar(10),fflush(stdout),printf("00");
  for(int i=3;i<w;i++)putchar('1');
  printf("0\n"),fflush(stdout),putchar('0');
  for(int i=2;i<w;i++)putchar('1');
  printf("0\n"),fflush(stdout);
  for(int i=1;i<=w;i++)putchar('0');
  putchar(10),fflush(stdout),c1=2*(w-2)-1;
}
main()
{
  scanf("%d%d%d",&h,&w,&q),construct();
  while(q--)solve();
  return 0;
}