山西人工智能建站系统软件,有没有免费的推广平台,社群运营,衡阳衡南网站建设题意#xff1a;
给定数 x #xff0c;每次可以选择将 x 变为 x*2 #xff0c;或是将 x 变为 x1#xff0c;求 x 变为 2 20 2^{20} 220倍数的最小代价。
思路#xff1a;
因为对于 2 20 2^{20} 220次方倍数的点无意义#xff0c;所以总共的点数只用 2 20 2^{20} 220即…题意
给定数 x 每次可以选择将 x 变为 x*2 或是将 x 变为 x1求 x 变为 2 20 2^{20} 220倍数的最小代价。
思路
因为对于 2 20 2^{20} 220次方倍数的点无意义所以总共的点数只用 2 20 2^{20} 220即可。那么对于 x 的两种变换方式我们可以把其抽象为 x 和 x*2 间连了一条边x 和 x1之间连了一条边。然后去bfs跑最短路即可。 但因为是多组询问我们可以预处理上述的最短路信息然后之间询问即可。 所以我们把终点当作起点然后反向建边即可。
#include bits/stdc.husing namespace std;
const int N 2e6 5;
typedef long long ll;
typedef pairll, ll pll;
typedef arrayll, 3 p3;
int mod 998244353;
const int maxv 4e6 5;
// #define endl \n
vectorint e[N];void add(int u,int v)
{e[u].push_back(v);
}
int d[N];
void init()
{int res1;for(int i1;i20;i) res*2;for(int i0;ires;i){add((i1)%res,i);add((i*2)%res,i);}queueint q;q.push(0);memset(d,0x3f,sizeof d);d[0]0;while(!q.empty()){auto tq.front();q.pop();for(auto x: e[t]){if(d[x]d[t]1){d[x]d[t]1;q.push(x);}}}
}
void solve()
{ int n;cinn;n%(1ll20);coutd[n]endl;}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t1;cint;init();while(t--){solve();}system(pause);return 0;
}
