D题_牛客博客

题目可以转换成
对 $a[i]$ 取反，得到 $b[i]$ ，如果 $a[j]$ 是 $b[i]$ 在二进制下的子集，则可以建边 $i->j$
因为这是基于数的建边(可能有多个值相同)，复杂度简单考虑：
如果每个数只出现一次，那么至多出现的二进制( $1<<17$ )的子集数( $3^{17}$ )
并且边的长度都是 $1$ ，所以可以这么 $bfs$ 出去。

特殊情况，基于值所以，对于 $dis[s]=0$ ,同样值的别的点就不是 $0$ 了。
对于这一类点：
判断是不是 $a[s]=0$ ，因为 $0$ 只要一步到达。
如果不是，若能发出一条边，那么距离是 $2$ ，因为 $s\to t,t\to j(a[j]=a[s])$ ,上面建边的过程永远都是可以相互走的。
否则无法到达。

一直卡这个特判，看了别人的才反应过来

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int K = 19;
const int maxn  = 1e6 + 100;
const int inf = 0x3f3f3f3f;
const int all = (1<<18)-1;

int dp[maxn],ans[maxn];
int n,s,a[maxn],vis[maxn],cnt[maxn];
queue<int>q;

int main(){
    cin>>n>>s;
    for(int i=1;i<=n;i++)scanf("%d",a+i),cnt[a[i]]++;
    memset(dp,0x3f,sizeof(dp));
    dp[a[s]]=0;
    q.push(a[s]);
    while(!q.empty()){
        int u=q.front();q.pop();
        if(vis[u])continue;
        vis[u]=1;
        int tmp=all^u;
        for(int v=tmp;;v=((v-1)&tmp)){
            if(cnt[v]){
                dp[v]=min(dp[v],dp[u]+1);
                q.push(v);
            }
            if(v==0)break;
  //          cout<<((v-1)&u)<<endl;
        }
    }
    bool ok=false;
    int tmp=a[s]^all;
    for(int v=tmp;;v=((v-1)&tmp)){
        if(cnt[v])ok=true;
        if(v==0)break;
    }
    for(int i=1;i<=n;i++){
        if(dp[a[i]]==inf)ans[i]=-1;
        else if(a[i]==a[s]){
            if(a[i]==0)ans[i]=1;
            else if(ok)ans[i]=2;
            else ans[i]=-1;
        }
        else ans[i]=dp[a[i]];
    }
    ans[s]=0;
    for(int i=1;i<=n;i++)printf("%d%c",ans[i],i==n?'\n':' ');
}

SOS $dp$ 看懂了，但是用在这里真心写不来