CF1168C And Reachability

2023-10-17 08:04

文章标签 cf1168c reachability

本文主要是介绍CF1168C And Reachability，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Toad Pimple 有一个整数数组 $a_1,\cdots,a_n$ ，我们称 $x$ 到 $y$ 可达当且仅当：

$x < y$
存在一个数组 $p$ ，其中 $x=p_1<p_2<...<p_k=y$ ，并且对于任意 $1\le i<k$ ，满足 $a_{p_i}\&a_{p_{i+1}}>0$

现在给定 $Q$ 组下标 $X_i,Y_i)$ ，请检查它们是否可达。

考虑从 $y$ 跳到 $x$ ，如果我们可以找到一个 $a_i$ 满足第 $j$ 位是 $1$ 且 $a_l$ 在这一位也是 $1$ ，并且 $r$ 可以跳到这个位置 $i$ ，就是可行的。

显然，我们要尽可能让这个位置贴近 $r$ ，因为这样更有“优势”，可以让更多的 $l$ 可行。

设 $f_{i,j}$ 表示一个最大的下标 $x$ 满足小于等于 $i$ ， $a_x$ 第 $j$ 位是 $1$ 。

有朴素转移： $f_{i,j}=\max\limits_{k=1}^{i-1}f_{k,j}$ ，转移条件 $a_i\&a_k>0$ ；特殊地，当 $a_i$ 第 $j$ 为是 $1$ 时， $f_{i,j}=i$ 。

这是 $O(n^2)$ 的，思考如何优化。

发现转移条件 $a_i\&a_k>0$ ，可以转换为枚举第 $x$ 位，如果 $a_i$ 和 $a_k$ 的第 $x$ 为都为 $1$ ，这样就可以转移。

又有性质 $f_{i,j}$ 随 $i$ 单调递增，那么肯定是选最大的 $k$ 一定最优。

所以用 $pre_j$ 记录当前上一个下标 $x$ 满足 $a_x$ 的第 $j$ 位为 $1$ 。转移就变成

$f_{i,j}=\max\limits_{k=0}^{m}f_{pre_{k},j}$

对每个 $i$ 转移完后记得更新 $pre_j$ 。

时间复杂度 $O(n\log^2n+q\log n)$

#include<bits/stdc++.h>
using namespace std;
const int N=3e5+1,NN=19;
int n,q,a[N],f[N][NN+1],pre[NN];
int main()
{scanf("%d%d",&n,&q);for(int i=1;i<=n;i++) scanf("%d",&a[i]);for(int i=1;i<=n;i++){for(int j=0;j<NN;j++){for(int k=0;k<NN;k++){if(a[i]>>k&1){f[i][j]=max(f[i][j],f[pre[k]][j]);}}}for(int j=0;j<NN;j++){if(a[i]>>j&1){pre[j]=i;f[i][j]=max(f[i][j],i);}}}for(int i=1,x,y;i<=q;i++){scanf("%d%d",&x,&y);for(int j=0;j<NN;j++){if(a[x]>>j&1){if(f[y][j]>=x){puts("Shi");goto a;}}}puts("Fou");a:;}
}