企业网站设计北京,设计师销售管理软件,wordpress源码安装,昭通网站开发公司题目
题目链接
题意 n2h−1#xff0c;且1≤n≤1023n2h−1#xff0c;且1≤n≤1023你可以最多询问2.5∗logn12∗n2.5∗log2n1∗n次#xff0c;任意两点的距离#xff0c;让你还原一颗完全二叉树。
题解
第一步、肯定要求整棵树的根节点。
由于这是一颗完全二叉树…题目
题目链接
题意
n2h−1且1≤n≤1023n2h−1且1≤n≤1023n = 2^h-1，且1≤n≤1023 你可以最多询问2.5∗logn12∗n2.5∗log2n1∗n2.5*log_2^{n+1}*n次任意两点的距离让你还原一颗完全二叉树。
题解
第一步、肯定要求整棵树的根节点。
由于这是一颗完全二叉树我们可以求出树的一个直径以及直径上的两个点f1、f2f1、f2f1、f2然后枚举点到f1、f2f1、f2f1、f2的距离当这个点到两点的距离相等的时候这个点就是根节点。 所使用询问次数3n。
第二步、递归求解。
计算出所有的点到根节点的距离。询问次数:n找出距离根节点为1的点就是根节点的两个儿子c1,c2c1,c2c1,c2设置fa[c1]fa[c2]rtfa[c1]fa[c2]rtfa[c1] = fa[c2] = rt将剩下的点分配给左右子树用c1去遍历所有剩下的点若距离减小说明该点属于c1c1c1子树否则属于c2c2c2子树将这个点分配给对应的子树并重新更新距离。询问次数:size(rt的子树)次。重复23步骤直至到叶节点。总的询问次数logn12∗nlog2n1∗nlog_2^{n+1}*n
代码
#include iostream
#include cstdio
#include unordered_map
using namespace std;
const int maxn 1024;
int dis[maxn][maxn];
int fa[maxn];
int n,h,root;
int ask(int u,int v){if(dis[u][v]) return dis[u][v];printf(? %d %d\n,u,v);fflush(stdout);scanf( %d,dis[u][v]);return dis[v][u] dis[u][v];
}
void dfs(int rt,unordered_mapint,int mp){if(!mp.size()) return ;int c1 -1,c2 -1;for(auto p : mp){if(p.second 1){if(c1 -1) c1 p.first;else c2 p.first;}}unordered_mapint,int mp1,mp2;for(auto p : mp){if(p.first c1 || p.first c2) continue;if(ask(p.first,c1) p.second)mp1[p.first] p.second-1;elsemp2[p.first] p.second-1;}fa[c1] rt;fa[c2] rt;dfs(c1,mp1);dfs(c2,mp2);
}
int main(){//coutask(1,2)endl;scanf(%d,n);if(n 1){return 0*puts(! 0);}int t n1;while(t) h,t 1;h--;int f1 1,f2 1;for(int i 1;i n;i)if(ask(i,1) ask(f1,1))f1 i;for(int i 1;i n;i)if(ask(i,f1) ask(f2,f1))f2 i;for(int i 1;i n;i){if(ask(i,f1) ask(i,f2)){root i;break;}}unordered_mapint,int mp;for(int i 1;i n;i){if(root i) continue;mp[i] ask(i,root);}dfs(root,mp);printf(! );for(int i 1;i n;i){printf(%d ,fa[i]);}
}
