题解：P9361 [ICPC 2022 Xi'an R] Contests

· · 题解

引言

思路上，其它题解已经讲得很清楚了，就是预处理再倍增。但是具体的转移方程和代码实现迄今为止却没有一篇题解讲清楚，导致本蒟蒻狂调一整天。

这里我参考 @under_the_time 的题解里的处理方式，讲一讲相关状态的定义和转移、预处理和倍增的具体过程是怎样的。

前置

名词解释

先解释一下将要用到的名词：

结构体

首先，定义一个结构体类型 Rank，内含一个大小为 m 的数组，存储的是一个点在各个组内的排名信息、一个点在各个组的可达最高排名/可达范围（每组内都是一段后缀）的起点。

struct Rank{
    int c[M];
};

我们要让它支持两种操作：比较和合并。

先说合并。在预处理过程中，我们会得到某个点通过某种单一路径可以得到不同的最高排名信息。而这些信息需要合并成一个完整的排名信息，即这个点通过所有路径所能到达每组的最高排名。

合并的代码也很简单，直接取各个方式的最高排名即可，本文中重载为加号 +：

Rank operator + (const Rank &x,const Rank &y)
{
    Rank res;
    for(int i=1;i<=m;i++)
        res.c[i]=min(x.c[i],y.c[i]);
    return res;
}
void operator += (Rank &x,const Rank &y){x=x+y;}

（其实这里重载的加号更像是一个 \min 操作？）

再说比较。在倍增过程中，我们要判断某个点 x 是否已经可以一步到达另一个点 y。这种情况发生当且仅当 x 所能到达的最高排名中存在一个位于 y 的前面。

bool operator < (const Rank &x,const Rank &y) //x能够一步走到y当且仅当x<y 
{
    for(int i=1;i<=m;i++)
        if(x.c[i]<y.c[i]) return true;
    return false;
}

以上单次操作时间复杂度均为 O(m)。

状态表示

然后是倍增的状态表示（姑且先这么叫）。

以上三个状态都是 Rank 类型。

（迄今为止所有题解都没有提到需要用 g 来辅助计算 f，导致本蒟蒻迷惑了很久。）

解释：

特别注意

本题千万不要把不同组内同一个数的来回切换看做一步！

（这个错误想法导致我挂了很多次，甚至写这篇题解时也差点又这么想。）

预处理

g 数组

对于倍增的预处理，首先需要计算 g，前面已经提到它是一个后缀和，所以直接这样计算就行，时间复杂度 O(m^2 n)。

g(i,j) = \sum_{k=j}^{n} p(a_{i,j}) = p(a_{i,j}) + g(i,j+1)

（求和符号 \sum 所用为上文重载过的加号，下同。）

for(int i=1;i<=m;i++)
    for(int j=n;j>=1;j--)
    {
        if(j==n) g[i][j]=pos[a[i][j]];
        else g[i][j]=pos[a[i][j]]+g[i][j+1];
    }

f(i,0) 初始化

有了 g 以后就可以据此来初始化 f(i,0) 了，时间复杂度 O(m^2 n)。

f(i,0) = \sum_{j=1}^{m} g(j,p(i)_j)

这里面的 j 用来枚举 i 所属的组。对于某一个 j，p(i)_j 表示 i 在第 j 组中所处的位置。根据定义，f(i,0) 表示每一组内 i 的后缀跳 1 步的最高排名。若当前在第 j 组，那么这一段后缀就是 [p(i)_j,n]，g(j,p(i)_j) 就表示了这段后缀在所有组上可达的最大排名（走的这 1 步就是将这些最大排名扩展为后缀）。将所有组内的 m 段后缀合并起来得到 f(i,0)， 所表示即为 m 段后缀在全局的可达最大排名。

for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        if(j==1) f[i][0]=g[1][pos[i].c[1]];
        else f[i][0]+=g[j][pos[i].c[j]];
    }

剩下的 f

最后就可以求出所有 f 值了，时间复杂度 O(m^2 n \log n)。

f(i,k) = \sum_{j=1}^{m} f(a_{j,f(i,k-1)_j},k-1)

该方程中 j 的作用为枚举中转点，我们只需要记录排名最高的那个中转点就行了。

解释一下为什么只用记录最高排名就行了。因为这里方程所转移的只是将这个最高排名点作为中转点，从而便于走到该组内其它点的（以最高点走向组内其它点一定最优）。

反之，若某条路径无需以它作为中转点就可直达，那么这条路径的贡献应该在枚举这个中转点之前就已经计算完毕。如果加上中转点，多出来了一段长度，比已有的路径更劣，也不会更新和影响现有答案。

```cpp for(int k=1;k<=logN;k++) //确定其余 f for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(j==1) f[i][k]=f[a[j][f[i][k-1].c[j]]][k-1]; else f[i][k]+=f[a[j][f[i][k-1].c[j]]][k-1]; } ``` ## 倍增 ### 求解 前面的过程将整个路径分成三部分： + 第一步，将 $x$ 可达范围从 $m$ 个单点扩展为 $m$ 段后缀； + 中间若干步，不断扩展使得 $X$ 的表示的后缀中**刚好**任意一段都**不**包含 $Y$，这也是倍增过程所求的； + 最后一步，因为 $X$ 刚好不能达到 $Y$，所以走这最后一步就可以直接抵达 $y$ 了。 读入 $x$、$y$ 后，我们首先需要获取它们的原始排名，设为 $X$ 和 $Y$，第一步以后它们就将成为多段后缀段。 倒序枚举 $k$ 的同时，**模拟** $X$ 走 $2^k$ 步后的结果 $nxt$，如果 $nxt<Y$（之前已经重载了 `<` 符号，表示能够直接抵达）不成立，则把这一步实实在在走出去，令 $X \gets nxt$，并把步数加上 $2^k$。 最后的步数应该加上前后省略的那两步，时间复杂度 $O(m^2 q \log n)$。 ### 无解 对于每一个有效步，至少能多覆盖一个点，否则未来永远无法覆盖更多点了。 因此，一个全部由有效步构成的路径至多有 $n$ 步。超出 $n$ 步代表有效路径无法覆盖 $y$，因此可判无解。 > 或者你也可以将题目看做图论最短路，$x$ 到 $y$ 至多 $n$ 个点。 ### 特判 注意特判 $x$ 能够一步到达 $y$ 的情况，此时第一步和最后一步是同一步，而中间的步骤根本不存在（因为 $x \neq y$，所以答案至少是 $1$）。 倍增部分代码： ```cpp int px,py; scanf("%d%d",&px,&py); Rank x=pos[px],y=pos[py]; if(x<y) printf("1\n"); //特判一步即达 else { int ans=0; for(int i=logN;i>=0;i--) { Rank nxt=x; for(int j=1;j<=m;j++) nxt+=f[a[j][x.c[j]]][i]; if(!(nxt<y)) ans+=1<<i,x=nxt; //nxt不能抵达y } if(ans>n) printf("-1\n"); //无解 else printf("%d\n",ans+2); } ``` ## 代码 总时间复杂度 $O(m^2 (n+q) \log n)

提交记录：R203561810。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=1e5+5,M=10,logN=17;
int n,m,q,a[M][N];

struct Rank{
    int c[M];
}pos[N],f[N][logN+5],g[M][N];
/*
 * pos[i]：i在每组内的排名/一步后的可达后缀 
 * f[i][j]：i跳2^j步后在每一组的最高排名/可达后缀 
 * g[i][j]：第i组内j~n位置上的所有人在每一组的最高排名/可达后缀 
 */
bool operator < (const Rank &x,const Rank &y) //x能够走到y当且仅当x<y 
{
    for(int i=1;i<=m;i++)
        if(x.c[i]<y.c[i]) return true;
    return false;
}
Rank operator + (const Rank &x,const Rank &y) //合并两个排名信息 
{
    Rank res;
    for(int i=1;i<=m;i++)
        res.c[i]=min(x.c[i],y.c[i]);
    return res;
}
void operator += (Rank &x,const Rank &y){x=x+y;}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%d",&a[i][j]);
            pos[a[i][j]].c[i]=j;
        }
    for(int i=1;i<=m;i++)
        for(int j=n;j>=1;j--) //确定 g 
        {
            if(j==n) g[i][j]=pos[a[i][j]];
            else g[i][j]=pos[a[i][j]]+g[i][j+1];
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) //确定 f[i][0] 
        {
            if(j==1) f[i][0]=g[1][pos[i].c[1]];
            else f[i][0]+=g[j][pos[i].c[j]];
        }
    for(int k=1;k<=logN;k++) //确定其余 f
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
            {
                if(j==1) f[i][k]=f[a[j][f[i][k-1].c[j]]][k-1];
                else f[i][k]+=f[a[j][f[i][k-1].c[j]]][k-1];
            }
    scanf("%d",&q);
    for(int i=1;i<=q;i++)
    {
        int px,py; scanf("%d%d",&px,&py);
        Rank x=pos[px],y=pos[py];
        if(x<y) printf("1\n"); //特判一步即达 
        else
        {
            int ans=0;
            for(int i=logN;i>=0;i--)
            {
                Rank nxt=x;
                for(int j=1;j<=m;j++)
                    nxt+=f[a[j][x.c[j]]][i];
                if(!(nxt<y)) ans+=1<<i,x=nxt; //nxt不能抵达y 
            }
            if(ans>n) printf("-1\n"); //无解 
            else printf("%d\n",ans+2);
        }
    }
    return 0;
}

后记

本人蒟蒻，即使知道了倍增思路以后也难以打出代码，最后因为被 O(m^2(n+q) \log n) 的时空复杂度卡得 MLE+TLE 而选择放弃原有的处理方式而学习题解中的处理方式。花费 30 min 终于（自认为）读懂。于是打算补充大佬们不屑于讲解和证明的部分，写成此篇题解造福后人。

但是，在写题解的过程中，我发现我的理解依然有诸多缺漏，状态的定义和转移仍有许多不完整甚至错误之处，所以这篇题解也经过多次修正，直到整个逻辑自洽，这整个过程也让我受益匪浅。

因为多次修改，本题解难免会有一些前后语言表述不通顺的情况，还请多多包涵、提出意见，谢谢！