2021年度训练联盟热身训练赛第二场 J-Lowest Common Ancestor 进制转换,LCA

本文主要是介绍2021年度训练联盟热身训练赛第二场 J-Lowest Common Ancestor 进制转换,LCA,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接

https://ac.nowcoder.com/acm/contest/12794/J

题意

满二叉树,层序遍历给出编号,多次询问求两点公共祖先。其中点编号以十六进制串给出(1000位),输出也是十六进制

思路

满二叉树层序遍历的LCA没什么好说的,对于u和v,一直对u和v编号大的除二,直到相等就找到了

看到十六进制,加上直接除二这个操作就别考虑十进制数了,用二进制串处理,二进制数除二就是右移,也就是说两个二进制编号的LCA就是他们最长公共前缀。

至于十六进制和二进制转换,直接看代码吧

复杂度

O ( n ) O(n) O(n)

代码
#include<cstdio>
#include<iostream>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<string>
#include<queue>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib> 
#include<chrono>
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl "\n"
#define int long long
//#define double long double
using namespace std;typedef long long ll;const int maxn=200505;const int inf=0x3f3f3f3f;int n,m,k;int sum[maxn],max_[maxn];int a[maxn];struct custom_hash {static uint64_t splitmix64(uint64_t x) {x += 0x9e3779b97f4a7c15;x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;x = (x ^ (x >> 27)) * 0x94d049bb133111eb;return x ^ (x >> 31);}size_t operator()(uint64_t x) const {static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();return splitmix64(x + FIXED_RANDOM);}};string s1,s2,s3,s4;string ans1,ans2;string shiliu_er(string &str){string res;for(int i=0;i<str.size();i++){char ch=str[i];if(ch=='0') res+="0000";else if (ch == '1') res += "0001";else if (ch == '2') res += "0010";else if (ch == '3') res += "0011";else if (ch == '4') res += "0100";else if (ch == '5') res += "0101";else if (ch == '6') res += "0110";else if (ch == '7')res += "0111";else if (ch == '8')res += "1000";else if (ch == '9')res += "1001";else if (ch == 'a')res += "1010";else if (ch == 'b')res += "1011";else if (ch == 'c')res += "1100";else if (ch == 'd')res += "1101";else if (ch == 'e') res += "1110";else if (ch == 'f') res += "1111";}string t;bool over=0;for(int i=0;i<res.size();i++){if(over)    t+=res[i];else{if(res[i]=='0') continue;else{over=1;t+=res[i];}}}return t;}string er_shiliu(string &str){int i=str.size()-1;//cout<<str<<endl;string res;while(i>=3){string t;t+=str[i-3];t+=str[i-2];t+=str[i-1];t+=str[i];if(t=="0000") res+="0";else if (t == "0001") res += "1";else if (t == "0010") res += "2";else if (t == "0011") res += "3";else if (t == "0100") res += "4";else if (t == "0101") res += "5";else if (t == "0110") res += "6";else if (t == "0111")res += "7";else if (t == "1000")res += "8";else if (t == "1001")res += "9";else if (t == "1010")res += "a";else if (t == "1011")res += "b";else if (t == "1100")res += "c";else if (t == "1101")res += "d";else if (t == "1110") res += "e";else if (t == "1111") res += "f";i-=4;}if(i==-1){}else if(i==0){res+='1';}else if(i==1){if(str[i]=='1') res+="3";else            res+="2";}else if(i==2){if(str[1]=='0'){if(str[2]=='1') res+='5';else            res+='4';}else{if(str[2]=='1') res+='7';else            res+='6';}}reverse(res.begin(),res.end());//cout<<res<<endl;return res;}signed main(){IOS#ifndef ONLINE_JUDGEfreopen("D:\\_ACM_code\\IO\\in.txt","r",stdin);freopen("D:\\_ACM_code\\IO\\out.txt","w",stdout);#endifint tn;cin>>tn;for(int jj=1;jj<=tn;jj++){cin>>s1>>s2;s3=shiliu_er(s1),s4=shiliu_er(s2);ans1.clear();for(int i=0;i<min(s3.size(),s4.size());i++){if(s3[i]==s4[i])    ans1+=s3[i];else    break;}ans2=er_shiliu(ans1);cout<<"Case #"<<jj<<": ";cout<<ans2<<endl<<endl;}} 

这篇关于2021年度训练联盟热身训练赛第二场 J-Lowest Common Ancestor 进制转换,LCA的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/858190

相关文章

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

在java中如何将inputStream对象转换为File对象(不生成本地文件)

《在java中如何将inputStream对象转换为File对象(不生成本地文件)》:本文主要介绍在java中如何将inputStream对象转换为File对象(不生成本地文件),具有很好的参考价... 目录需求说明问题解决总结需求说明在后端中通过POI生成Excel文件流,将输出流(outputStre

python+opencv处理颜色之将目标颜色转换实例代码

《python+opencv处理颜色之将目标颜色转换实例代码》OpenCV是一个的跨平台计算机视觉库,可以运行在Linux、Windows和MacOS操作系统上,:本文主要介绍python+ope... 目录下面是代码+ 效果 + 解释转HSV: 关于颜色总是要转HSV的掩膜再标注总结 目标:将红色的部分滤

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark

C语言中的数据类型强制转换

《C语言中的数据类型强制转换》:本文主要介绍C语言中的数据类型强制转换方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录C语言数据类型强制转换自动转换强制转换类型总结C语言数据类型强制转换强制类型转换:是通过类型转换运算来实现的,主要的数据类型转换分为自动转换

Java实现XML与JSON的互相转换详解

《Java实现XML与JSON的互相转换详解》这篇文章主要为大家详细介绍了如何使用Java实现XML与JSON的互相转换,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录1. XML转jsON1.1 代码目的1.2 代码实现2. JSON转XML3. JSON转XML并输出成指定的

Java实现将Markdown转换为纯文本

《Java实现将Markdown转换为纯文本》这篇文章主要为大家详细介绍了两种在Java中实现Markdown转纯文本的主流方法,文中的示例代码讲解详细,大家可以根据需求选择适合的方案... 目录方法一:使用正则表达式(轻量级方案)方法二:使用 Flexmark-Java 库(专业方案)1. 添加依赖(Ma

Java实现将byte[]转换为File对象

《Java实现将byte[]转换为File对象》这篇文章将通过一个简单的例子为大家演示Java如何实现byte[]转换为File对象,并将其上传到外部服务器,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言1. 问题背景2. 环境准备3. 实现步骤3.1 从 URL 获取图片字节数据3.2 将字节数组

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

Python使用PIL库将PNG图片转换为ICO图标的示例代码

《Python使用PIL库将PNG图片转换为ICO图标的示例代码》在软件开发和网站设计中,ICO图标是一种常用的图像格式,特别适用于应用程序图标、网页收藏夹图标等场景,本文将介绍如何使用Python的... 目录引言准备工作代码解析实践操作结果展示结语引言在软件开发和网站设计中,ICO图标是一种常用的图像