[海军国际项目办公室]二叉搜索树

2024-03-16 22:48

本文主要是介绍[海军国际项目办公室]二叉搜索树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

二叉搜索树

题解

首先,我们发现对于任何一棵子树内,他所包含带你的权值映射到我们所有加入了树内的点一定是连续的。
所以如果我们倒着来,每次将两棵子树接在一个根上,接出来的根的值域也一定是连续的,我们可以考虑区间dp。
对于顺序固定的点,我们明显可以直接知道它两边的子树是哪些,直接连起来即可。
对于那些顺序不顾定的点,我们就只能通过区间dp进行处理。
但事实上,我们每次 d p dp dp的必须是一个连续段,也就是说,我们总共的 d p dp dp总共会被按照 [ 1 , l ) [1,l) [1,l)建出来的树分为多个小段,我们要对这些小段内部分别进行区间dp。
我们不妨将 [ l , r ] [l,r] [l,r]中的点全部按照大小排序,记 d p l , r dp_{l,r} dpl,r表示值域范围为 [ a l , a r ] [a_{l},a_{r}] [al,ar]的点所构成的子树的深度和,容易得到转移方程式
d p l , r = max ⁡ m i d = l r d p l , m i d − 1 + d p m i d + r , r + r − l dp_{l,r}=\max_{mid=l}^{r}dp_{l,mid-1+dp_{mid+r,r}}+r-l dpl,r=mid=lmaxrdpl,mid1+dpmid+r,r+rl
但显然这样是不完全的,因为我们要考虑后面那些顺序固定的点的贡献,也就是说,如果我们枚举的根恰好是左右端点之一,我们要将它那一侧的顺序固定的点所建成的子树大小加进去。
求出这个这一段区间的 d p dp dp值后,我们可以随便钦定一个节点作为根,然后继续处理前面那一段。
至于维护某个节点所处子树的根,我们可以用并查集进行维护。

时间复杂度 O ( α ( n ) n + ( r − l ) 3 ) O\left(\alpha(n)n+(r-l)^3\right) O(α(n)n+(rl)3)

源码

#include<bits/stdc++.h> 
using namespace std;
#define MAXN 100005
#define lowbit(x) (x&-x)
#define reg register
#define pb push_back
#define mkpr make_pair
#define fir first
#define sec second
#define lson (rt<<1)
#define rson (rt<<1|1)
typedef long long LL;
typedef unsigned long long uLL;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int mo=1e9+7;
const int inv2=499122177;
const int jzm=2333;
const int zero=10000;
const int lim=30000;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
const double eps=1e-5;
typedef pair<int,int> pii;
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
int add(int x,int y,int p){return x+y<p?x+y:x+y-p;}
void Add(int &x,int y,int p){x=add(x,y,p);}
int qkpow(int a,int s,int p){int t=1;while(s){if(s&1LL)t=1ll*a*t%p;a=1ll*a*a%p;s>>=1LL;}return t;}
int n,b[MAXN],fa[MAXN],L[MAXN],R[MAXN],l,r;LL dp[MAXN],g[405][405]; 
int findSet(int x){return fa[x]==x?x:fa[x]=findSet(fa[x]);}
signed main(){read(n);for(int i=1;i<=n;i++)read(b[i]);read(l);read(r);for(int i=n;i>r;i--){fa[b[i]]=b[i];L[b[i]]=b[i];R[b[i]]=b[i];dp[b[i]]=1;if(fa[b[i]-1]){int x=findSet(b[i]-1);L[b[i]]=L[x];dp[b[i]]+=dp[x]+1ll*(R[x]-L[x]+1);fa[x]=b[i];}if(fa[b[i]+1]){int x=findSet(b[i]+1);R[b[i]]=R[x];dp[b[i]]+=dp[x]+1ll*(R[x]-L[x]+1);fa[x]=b[i];}}sort(b+l,b+r+1);for(int i=l,j;i<=r;i=j+1){j=i;while(j<r){if(b[j+1]==b[j]+1){j++;continue;}if(!fa[b[j]+1]||!fa[b[j+1]-1])break;if(findSet(b[j]+1)==findSet(b[j+1]-1)){j++;continue;}break;}for(int len=1;len<=j-i+1;len++)for(int li=1,ri=len;ri<=j-i+1;li++,ri++){g[li][ri]=INF;for(int mid=li;mid<=ri;mid++){LL tmp=0;int lt=b[li+i-1]-1,rt=b[ri+i-1]+1;if(li==mid){if(fa[lt])tmp+=dp[findSet(lt)];}else tmp+=g[li][mid-1];if(ri==mid){if(fa[rt])tmp+=dp[findSet(rt)];}else tmp+=g[mid+1][ri];g[li][ri]=min(g[li][ri],tmp); }int lt=fa[b[li+i-1]-1]?L[findSet(b[li+i-1]-1)]:b[li+i-1];int rt=fa[b[ri+i-1]+1]?R[findSet(b[ri+i-1]+1)]:b[ri+i-1];g[li][ri]+=1ll*(rt-lt+1);}for(int k=i;k<=j;k++){fa[b[k]]=b[k];L[b[k]]=b[k];R[b[k]]=b[k];if(fa[b[k]-1]){int x=findSet(b[k]-1);fa[x]=b[k];L[b[k]]=L[x];}if(fa[b[k]+1]){int x=findSet(b[k]+1);fa[x]=b[k];R[b[k]]=R[x];}}	dp[findSet(b[j])]=g[1][j-i+1];}for(int i=l-1;i>0;i--){fa[b[i]]=b[i];L[b[i]]=b[i];R[b[i]]=b[i];dp[b[i]]=1;if(fa[b[i]-1]){int x=findSet(b[i]-1);L[b[i]]=L[x];dp[b[i]]+=dp[x]+1ll*(R[x]-L[x]+1);fa[x]=b[i];}if(fa[b[i]+1]){int x=findSet(b[i]+1);R[b[i]]=R[x];dp[b[i]]+=dp[x]+1ll*(R[x]-L[x]+1);fa[x]=b[i];}}printf("%lld\n",dp[findSet(b[1])]);return 0;
}

谢谢!!!

这篇关于[海军国际项目办公室]二叉搜索树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/816978

相关文章

这15个Vue指令,让你的项目开发爽到爆

1. V-Hotkey 仓库地址: github.com/Dafrok/v-ho… Demo: 戳这里 https://dafrok.github.io/v-hotkey 安装: npm install --save v-hotkey 这个指令可以给组件绑定一个或多个快捷键。你想要通过按下 Escape 键后隐藏某个组件,按住 Control 和回车键再显示它吗?小菜一碟: <template

如何用Docker运行Django项目

本章教程,介绍如何用Docker创建一个Django,并运行能够访问。 一、拉取镜像 这里我们使用python3.11版本的docker镜像 docker pull python:3.11 二、运行容器 这里我们将容器内部的8080端口,映射到宿主机的80端口上。 docker run -itd --name python311 -p

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

在cscode中通过maven创建java项目

在cscode中创建java项目 可以通过博客完成maven的导入 建立maven项目 使用快捷键 Ctrl + Shift + P 建立一个 Maven 项目 1 Ctrl + Shift + P 打开输入框2 输入 "> java create"3 选择 maven4 选择 No Archetype5 输入 域名6 输入项目名称7 建立一个文件目录存放项目,文件名一般为项目名8 确定

hdu 4517 floyd+记忆化搜索

题意: 有n(100)个景点,m(1000)条路,时间限制为t(300),起点s,终点e。 访问每个景点需要时间cost_i,每个景点的访问价值为value_i。 点与点之间行走需要花费的时间为g[ i ] [ j ] 。注意点间可能有多条边。 走到一个点时可以选择访问或者不访问,并且当前点的访问价值应该严格大于前一个访问的点。 现在求,从起点出发,到达终点,在时间限制内,能得到的最大

Vue3项目开发——新闻发布管理系统(六)

文章目录 八、首页设计开发1、页面设计2、登录访问拦截实现3、用户基本信息显示①封装用户基本信息获取接口②用户基本信息存储③用户基本信息调用④用户基本信息动态渲染 4、退出功能实现①注册点击事件②添加退出功能③数据清理 5、代码下载 八、首页设计开发 登录成功后,系统就进入了首页。接下来,也就进行首页的开发了。 1、页面设计 系统页面主要分为三部分,左侧为系统的菜单栏,右侧

AI基础 L9 Local Search II 局部搜索

Local Beam search 对于当前的所有k个状态,生成它们的所有可能后继状态。 检查生成的后继状态中是否有任何状态是解决方案。 如果所有后继状态都不是解决方案,则从所有后继状态中选择k个最佳状态。 当达到预设的迭代次数或满足某个终止条件时,算法停止。 — Choose k successors randomly, biased towards good ones — Close

hdu4277搜索

给你n个有长度的线段,问如果用上所有的线段来拼1个三角形,最多能拼出多少种不同的? import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOException;import java.io.InputStream;import java.io.InputStreamReader;

SpringBoot项目是如何启动

启动步骤 概念 运行main方法,初始化SpringApplication 从spring.factories读取listener ApplicationContentInitializer运行run方法读取环境变量,配置信息创建SpringApplication上下文预初始化上下文,将启动类作为配置类进行读取调用 refresh 加载 IOC容器,加载所有的自动配置类,创建容器在这个过程