题意：给n个数，给定一个转换规则跟计算方法，找两两转化的最小值。
看完大佬的代码我就来出题解了！！！
由于这个东西我感觉好难，我还是写详细的题解吧。。。。
这是题目给的fairy的定义。那么x^(2^(i))这个东西肯定要预处理出来，方便后面的爆搜emmm
那么这个东西的预处理公式是：x^2^(i)=x^(2*2^(i-1))=x^(2^(i-1))*x^(2^(i-1))
这个东西就是要我们找在给出的那些值中，两两相互转换的最小值多大。。。
#include <bits/stdc++.h> using namespace std; #define ll long long #define re register #define P pair<int,int> #define mp make_pair #define pb push_back #define fi first #define se second const int N=1<<18; const int mod=19260817; void read(int &a) { a=0; int d=1; char ch; while(ch=getchar(),ch>'9'||ch<'0') if(ch=='-') d=-1; a=ch-'0'; while(ch=getchar(),ch>='0'&&ch<='9') a=a*10+ch-'0'; a*=d; } void write(int x) { if(x<0) putchar(45),x=-x; if(x>9) write(x/10); putchar(x%10+'0'); } struct note { int id; int v; bool operator < (const note &x) const { return x.v<v; } }; int vis[N],a[N],f[N][20],dis[N];///f数组为i^(2^(j)),vis[i]=j表示i从j转换而来,dis[i]表示到达i这个点的最小转化值 bool mark[N],book[N];///book标记出队 vector <P> s[N]; priority_queue <note> q; int main() { int n; ll ans=0x3fffffff; int x; read(n); bool flag=false; for(re int i=0;i<n;i++) { read(a[i]); if(mark[a[i]]) flag=1; mark[a[i]]=1; } if(flag) return puts("0"),0; for(re int i=0;i<N;i++) { f[i][0]=i; for(re int j=1;j<18;j++) f[i][j]=1ll*f[i][j-1]*f[i][j-1]%mod;///预处理 } for(re int i=0;i<N;i++) { for(re int j=0;j<18;j++) { x=max(i,i^(1<<j)); s[i].pb(mp(i^(1<<j),f[x][j]+1));///记录所有的fairy(i,j) } if(mark[i]) { vis[i]=i; dis[i]=0; q.push({i,0}); } else { vis[i]=-1; dis[i]=0x3fffffff; } } note t; while(!q.empty())///爆搜emmm { t=q.top(); q.pop(); if(t.v>=ans)///优先队列按小的排，如果已经大于ans了，那么可以退出了。 break; if(book[t.id]) continue; book[t.id]=1; for(re int i=0;i<s[t.id].size();i++) { int j=s[t.id][i].fi; int k=s[t.id][i].se; if(vis[j]!=-1&&vis[j]!=vis[t.id])///vis[j]!=vis[t.id]的原因是如果相等，那么这个点是由t.id拓展来的，再算多一次就重复计算了 ans=min(ans,1ll*(dis[j]+k+t.v));///dis[j]表示跑来j这个点的花费 if(dis[j]<=k+t.v) continue; dis[j]=k+t.v; vis[j]=vis[t.id];///更新这个点的来源 q.push({j,dis[j]});///更新j的值并加入队列 } } printf("%lld",ans%mod); return 0; }