儿童节快乐喵
jun头吉吉
·
·
题解
题意
给你 n,m，有 m 个长度为 n 的排列 a_1,\dots,a_m，有 q 组询问，每次给出 x,y，要求找到最小的 l 使得存在一个长为 l+1 的序列 b_1,\dots,b_{l+1} 满足：
或者输出 -1 表示不存在。
## 题解
看成每次可以跳一步，$x$ 可以跳到 $y$ 当且仅当存在一个序列使得 $y$ 出现在 $x$ 后面，问最少跳几步。
然后我们发现每一次如果不能直接跳到终点，那么可以跳的选择只有 $m$ 种，因为我们每一步肯定是跳到某个序列中最前的能跳到的点。
然后我们就可以倍增了，预处理出从每个点出发，跳 $2^i$ 步在序列 $a_j$ 中最前的点，然后每次询问倍增就能得到答案了。
时间复杂度 $\mathcal O((n+q)m^2\log n)$。
## 代码
```cpp
struct vi{int arr[5];int&operator[](int x){return arr[x];}vi(){memset(arr,0x3f,sizeof arr);}};
const int N=1e5+10,M=5,K=17,inf=0x3f3f3f3f;
int n,m,q,a[M][N],b[M][N];vi f[K][N];
bool ok(vi now,int y){
for(int i=0;i<m;i++)if(now[i]<=b[i][y])return 1;
return 0;
}
vi trans(vi now,int p){
vi res;
for(int i=0;i<m;i++)for(int j=0;j<m;j++)
chkmn(res[j],f[p][a[i][now[i]]][j]);
return res;
}
signed main(){
read(n,m);
for(int i=0;i<m;i++)for(int j=1;j<=n;j++)read(a[i][j]),b[i][a[i][j]]=j;
for(int i=0;i<m;i++)for(int j=0;j<m;j++)
for(int mn=0x3f3f3f3f,k=n;k;k--)chkmn(mn,b[i][a[j][k]]),chkmn(f[0][a[j][k]][i],mn);
for(int i=1;i<K;i++)for(int j=1;j<=n;j++)f[i][j]=trans(f[i-1][j],i-1);
read(q);while(q--){
int x,y;read(x,y);
int cnt=0;vi now;for(int i=0;i<m;i++)now[i]=b[i][x];
for(int i=K-1;~i;i--)if(!ok(trans(now,i),y))
cnt+=1<<i,now=trans(now,i);
if(!ok(trans(now,0),y))writeln(-1);
else{
if(!ok(now,y))cnt++,now=trans(now,0);
int t=1;
for(int i=0;i<m;i++)if(now[i]==b[i][y])t=0;
writeln(cnt+t);
}
}
}
```