Codeforces 1169E And Reachability 题解

题意简述

给定$n$个数$a1,a2…an$。如果$i<j$且$a[i]\&a[j]$（$\&$ 是按位与运算）非零，则$i\rightarrow j$连一条有向边。$q$次询问，每次给定$xi$和$yi$，查询$xi$是否能到$yi$。

每个输入的数都<=3e5，并且1<=xi<yi<=n。

思路框架

处理$dp[i][j]$表示$i$往后第一个能到并且包含二进制第$j$位的位置。

然后看是否存在$k$使得$dp[x][k]<y$即珂。

具体思路

讲讲$nex$如何处理。显然$dp[n+1][x]=n+1$，对于所有$x$。维护$dp$同时维护一个$nex[]$，$nex[j]$表示当前位置往后第一个包含二进制第$j$位的数在哪个位置。

显然，$i\rightarrow nex[j]$是联通的（$\&$一下，至少还有第$j$位）。
然后对于一个$i$，枚举$j$如果$i$包含第$j$位，则对于所有$k$，用$dp[nex[j]][k]$更新$dp[i][k]$的最小值。

然后我们不是枚举$i$中包含第$j$位么，更新完$dp$之后，更新$nex$：$nex[j]=i$。然后记得$dp[i][j]=i$。（自己也能到自己）

代码

复制

#include <bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
    #define N 1666666
    #define F(i,l,r) for(int i=l;i<=r;++i)
    #define D(i,r,l) for(int i=r;i>=l;--i)
    #define Fs(i,l,r,c) for(int i=l;i<=r;c)
    #define Ds(i,r,l,c) for(int i=r;i>=l;c)
    #define MEM(x,a) memset(x,a,sizeof(x))
    #define FK(x) MEM(x,0)
    #define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
    #define p_b push_back
    #define sz(a) ((int)a.size())
    #define iter(a,p) (a.begin()+p)
    void R1(int &x)
    {
        x=0;char c=getchar();int f=1;
        while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
        x=(f==1)?x:-x;
    }
    void Rd(int cnt,...)
    {
        va_list args;
        va_start(args,cnt);
        F(i,1,cnt) 
        {
            int* x=va_arg(args,int*);R1(*x);
        }
        va_end(args);
    }

    int n,q,a[N];
    void Input()
    {
        Rd(2,&n,&q);F(i,1,n) R1(a[i]);
    }

    int dp[N][22];
    int nex[22];
    void Soviet()
    {
        MEM(dp,0x3f);
        F(i,0,20) nex[i]=n+1,dp[n+1][i]=n+1;
        D(i,n,1) F(j,0,20) if (a[i]&(1<<j))
        {
            F(k,0,20) dp[i][k]=min(dp[i][k],dp[nex[j]][k]); 
            dp[i][j]=i;
            nex[j]=i;
        }

        F(i,1,q)
        {
            int x,y;Rd(2,&x,&y);
            bool flag=0;
            F(j,0,20) 
            {
                if ((a[y]&(1<<j)) and dp[x][j]<=y) {flag=1;break;} //找到一个就有解
            }
            puts(flag?"Shi":"Fou");
        }
    }

    #define Flan void
    Flan IsMyWife()
    {
        Input();
        Soviet();
    }
}
int main()
{
    Flandre_Scarlet::IsMyWife();
    getchar();getchar();
    return 0;
}