当前位置：首页 > news >正文

Codeforces Round 761 (Div. 2) E. Christmas Chocolates（思维题树的直径二进制性质 lca）

news 2025/8/7 19:34:59

题目

n(n<=2e5)个值，第i个值ai(0<=ai<=1e9)，所有ai两两不同

初始时，选择两个位置x,y(x≠y)，代表需要对这两个位置进行操作，要把其中一个值变成另一个

你可以执行若干次操作，每一次，你可以将一个值沿着 $2^k$ 对称翻折，具体来说，

当前值是v，你可以选择一个值k(k>=0，满足 $2^k$ >=v)，令v变为 $2^k$ -v，

不难发现，当选择策略最优时，x变成y一定是可行的，并且存在一个最小步数

输出你选择的位置(x,y)，使得a[x]变到a[y]的最小步数最大，并且输出最大的步数

思路来源

官方题解

题解

两年前补的题，当时ac了但是没写题解，今天写一下

注意到，如果令i+j= $2^k$ ，并且j<i的话，那么对于一个固定的i来说，( $2^k$ ,j)是唯一的

也就是说，对于每个i来说，比i小的数中，只有一个数j，能和i之和凑成2的幂次，反证法显然

如果每个i->j(j<i)连这么一条边，由于最后每个值越连越小，且二进制位只有一位的数会直接连向0

所以这是一棵树形结构，并且在0点处连通

问题等价于在这棵树上，标记n个点，求n个点两两距离的最大值和点号，

实际并不用建出完整的数，由于ai<=1e9，往上暴力爬lca只会爬log层（30层），

找到这30n的点建一棵残缺的数，把原来n个点也就是叶子结点标记一下，

求树的直径即可，即从任意点出发（不妨0），搜到带标记的最远一侧点x，

再从x搜一遍，搜到带标记的最远点y，（x、y、二者距离dis）即为所求

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10,M=31*N;
int n,a[N],b[32],x[M],c,d[M],mxd,pos,pos2,to[M];
vector<int>e[M];
void dfs(int u,int fa){for(auto &v:e[u]){if(v==fa)continue;//printf("u:%d v:%d\n",u,v);d[v]=d[u]+1;if(d[v]>mxd && to[v]){mxd=d[v];pos=v;}dfs(v,u);}
}
int main(){b[0]=1;for(int i=1;i<=30;++i){b[i]=b[i-1]<<1;}scanf("%d",&n);for(int i=1;i<=n;++i){scanf("%d",&a[i]);int lg=30;for(int j=a[i];j;j=b[lg]-j){x[c++]=j;while(lg>=0 && b[lg]>=j)lg--;lg++;}}x[c++]=0;sort(x,x+c);assert(c<=5000000);c=unique(x,x+c)-x;for(int i=1;i<c;++i){int fa=*lower_bound(b,b+31,x[i]);fa=fa-x[i];int id=lower_bound(x,x+c,fa)-x;e[id].push_back(i);e[i].push_back(id);}assert(c<=2000000);for(int i=1;i<=n;++i){int id=lower_bound(x,x+c,a[i])-x;to[id]=i;}dfs(0,-1);pos2=pos;d[pos]=mxd=0;dfs(pos,-1);printf("%d %d %d\n",to[pos2],to[pos],d[pos]);return 0;
}

查看全文

http://www.lryc.cn/news/275624.html