2019年华南理工大学程序设计竞赛（春季赛） B 修仙时在做什么？有没有空？可以来炼丹吗？（思维建图搜索）

https://ac.nowcoder.com/acm/contest/625/B

分析：

全部的状态只有1<<18 个 ， 所以我们可以预处理 f[u][j] , 然后建立出全部的u可以转移的状态的状态图；

有优先队列去搜索

这里需要注意一个坑点 ， 数组f[i][j] , 是不能开到long long ,这样会爆内存；可是 f[i][j-1]* f[i][j-1] 这个操作会爆int ,所以我们需要将

f[i][j-1]* f[i][j-1] 变成long long   1ll*f[i][j-1]* f[i][j-1] 然后再去 mod 

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1<<18;
const int mod = 19260817;
const int INF = 0x3f3f3f3f;

bool vabook[maxn],vis[maxn];
int f[maxn][20];
int fa[maxn];
int dis[maxn];
struct no
{
    int v;
   int  val;
    bool operator < (const no &x) const
    {
        return x.val<val;
    }
}P;
vector<no>G[maxn];
priority_queue<no> que;
int main()
{
    int n;scanf("%d",&n);
    bool T=0;
    int x ;
    for(int i=1 ; i<=n ; i++)
    {
        scanf("%d",&x);
        if(vabook[x]) T=1;
            vabook[x]=1;
    }
    if(T) {puts("0");return 0;} ///如果给出的数有重复出现 ， 肯定是0更优

    for(int i=0 ; i<maxn ; i++)  ///预处理出全部的 f[i][j]
    {
        f[i][0]=i;
        for(int j=1 ; j<18 ; j++)/// a^4=a^2 * a^2 , a^8=a^4*a^4;
        {
            f[i][j] = (1ll*f[i][j-1]* f[i][j-1]) %mod;///先转化为 long long 再去mod
        }


    }
    for(int u=0 ; u<maxn ; u++)
    {
        for(int j=0 ; j<18 ; j++)
        {
            int v=u^(1<<j);
            x = max(u,v);
            G[u].push_back({v , f[x][j]+1});///建立一个图 ， 把u 可以转去的状态于价值都记录
        }
        if(vabook[u])///这是我拥有的点
        {
            fa[u]=u;
            dis[u]=0;
            que.push({u,0});
        }
        else
        {
            fa[u]=-1;
            dis[u]=INF;
        }
    }
    ll ans=0x3f3f3f3f;
    //DJ最短路
    while(!que.empty()) 
    {
        P=que.top();
        que.pop();
        int u=P.v;
        if(P.val>=ans) break;///如果当前的状态最小的价值都小过ans , 就不用跟新了
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=0 ; i<G[u].size() ; i++)
        {
            int v=G[u][i].v;
            int w=G[u][i].val;

            if(fa[v]!=-1 && fa[v]!=fa[u])
            {
                ans=min(ans,1ll*(dis[v]+w+dis[u]));
                //ans%=mod;
            }

            if(dis[v] > w+dis[u])
            {
                dis[v]=w+dis[u];
                fa[v]=fa[u];

                que.push({v,dis[v]});
            }
        }
    }
    printf("%lld
",ans%mod);
    return 0;
}