CF1168C And Reachability（DP）

末蓝、 2021-11-22 15:08 235阅读 0赞

其实也不难。（自己没想到自己打自己脸）

首先定义 $g\[i\]\[j\]$ 表示 $i$ 前面（不包括 $i$）第一个第 $j$ 位是 $1$ 的数的位置。可以随便转移。

再定义 $f\[i\]\[j\]$ 表示 $i$ 前面（包括 $i$）第一个第 $j$ 位是 $1$ 的数，且能通过题面的操作跳到 $i$ 的位置。

也能随便转移。先判断 $i$ 自己可不可以，可以就直接搞，不可以就找一个中介位 $k$（$a\_i$ 的第 $k$ 位必须是 $1$），$f\[g\[i\]\[k\]\]\[j\]$ 一定是可以跳到的。因为 $i$ 肯定能从 $g\[i\]\[k\]$ 跳到（都有第 $k$ 位），$g\[i\]\[k\]$ 肯定能从 $f\[g\[i\]\[k\]\]\[j\]$ 跳到（定义）。

对于询问，找一个中介位 $k$（$a\_l$ 的第 $k$ 位必须是 $1$），那么 $r$ 可以从 $f\[r\]\[k\]$ 跳到。当且仅当 $f\[r\]\[k\]\\ge l$ 时，$f\[r\]\[k\]$ 可以从 $l$ 跳到。 所以判一下所有的 $k$ 即可。

时间复杂度 $O(n\\log^2 v+q\\log v)$。（代码实现优秀一点似乎可以一个 $\\log$？）

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int maxn=300030;
    #define FOR(i,a,b) for(int i=(a);i<=(b);i++)
    #define ROF(i,a,b) for(int i=(a);i>=(b);i--)
    #define MEM(x,v) memset(x,v,sizeof(x))
    inline int read(){
        int x=0,f=0;char ch=getchar();
        while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
        while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
        return f?-x:x;
    }
    int n,q,a[maxn],f[maxn][19],g[maxn][19],hhh[19];
    int main(){
        n=read();q=read();
        FOR(i,1,n) a[i]=read();
        FOR(i,1,n){
            FOR(j,0,18) g[i][j]=hhh[j];
            FOR(j,0,18) if((a[i]>>j)&1) hhh[j]=i;
        }
        FOR(i,1,n){
            FOR(j,0,18) if((a[i]>>j)&1) f[i][j]=i;
            else FOR(k,0,18) if((a[i]>>k)&1) f[i][j]=max(f[i][j],f[g[i][k]][j]);
        }
        while(q--){
            int l=read(),r=read();
            bool flag=false;
            FOR(i,0,18) if((a[l]>>i)&1) flag|=f[r][i]>=l;
            puts(flag?"Shi":"Fou");
        }
    }

转载于:https://www.cnblogs.com/1000Suns/p/11116736.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211122/9232c3e6c9c147639e7a9fbd694510fc.png