广东注册公司在哪个网站申请,苏州网站建设报价,注册网站的公司名字,阿里巴巴对外贸易平台题目
n(n2e5)个值#xff0c;第i个值ai(0ai1e9)#xff0c;所有ai两两不同
初始时#xff0c;选择两个位置x,y(x≠y)#xff0c;代表需要对这两个位置进行操作#xff0c;要把其中一个值变成另一个 你可以执行若干次操作#xff0c;每一次#xff0c;你可…题目
n(n2e5)个值第i个值ai(0ai1e9)所有ai两两不同
初始时选择两个位置x,y(x≠y)代表需要对这两个位置进行操作要把其中一个值变成另一个 你可以执行若干次操作每一次你可以将一个值沿着对称翻折具体来说
当前值是v你可以选择一个值k(k0满足v)令v变为-v
不难发现当选择策略最优时x变成y一定是可行的并且存在一个最小步数 输出你选择的位置(x,y)使得a[x]变到a[y]的最小步数最大并且输出最大的步数
思路来源
官方题解
题解
两年前补的题当时ac了但是没写题解今天写一下 注意到如果令ij并且ji的话那么对于一个固定的i来说(,j)是唯一的
也就是说对于每个i来说比i小的数中只有一个数j能和i之和凑成2的幂次反证法显然 如果每个i-j(ji)连这么一条边由于最后每个值越连越小且二进制位只有一位的数会直接连向0
所以这是一棵树形结构并且在0点处连通 问题等价于在这棵树上标记n个点求n个点两两距离的最大值和点号
实际并不用建出完整的数由于ai1e9往上暴力爬lca只会爬log层30层
找到这30n的点建一棵残缺的数把原来n个点也就是叶子结点标记一下
求树的直径即可 即从任意点出发不妨0搜到带标记的最远一侧点x
再从x搜一遍搜到带标记的最远点yx、y、二者距离dis即为所求
代码
#includebits/stdc.h
using namespace std;
const int N2e510,M31*N;
int n,a[N],b[32],x[M],c,d[M],mxd,pos,pos2,to[M];
vectorinte[M];
void dfs(int u,int fa){for(auto v:e[u]){if(vfa)continue;//printf(u:%d v:%d\n,u,v);d[v]d[u]1;if(d[v]mxd to[v]){mxdd[v];posv;}dfs(v,u);}
}
int main(){b[0]1;for(int i1;i30;i){b[i]b[i-1]1;}scanf(%d,n);for(int i1;in;i){scanf(%d,a[i]);int lg30;for(int ja[i];j;jb[lg]-j){x[c]j;while(lg0 b[lg]j)lg--;lg;}}x[c]0;sort(x,xc);assert(c5000000);cunique(x,xc)-x;for(int i1;ic;i){int fa*lower_bound(b,b31,x[i]);fafa-x[i];int idlower_bound(x,xc,fa)-x;e[id].push_back(i);e[i].push_back(id);}assert(c2000000);for(int i1;in;i){int idlower_bound(x,xc,a[i])-x;to[id]i;}dfs(0,-1);pos2pos;d[pos]mxd0;dfs(pos,-1);printf(%d %d %d\n,to[pos2],to[pos],d[pos]);return 0;
}
