INWF

学习一下LCA算法最近公共祖先算法在算法和数据结构的学习中，树结构是一种非常重要且常见的数据结构。在树结构中，节点之间的关系错综复杂，而最近公共祖先（Lowest Common Ancestor，LCA）算法则是解决这些关系的一种关键算法。LCA问题在实际应用中非常广泛，例如家谱树、文件目录树、计算机网络中的路由选择等。 LCA算法的定义和应用背景LCA算法，即最近公共祖先算法，指的是在一棵树中找到两个节点的最近的共同祖先节点。最近公共祖先可以简单地理解为在从这两个节点到根节点的路径中，最深的那个共同节点。 常见应用场景 家谱树: 确定两个家庭成员的最近共同祖先。 找到宇智波佐助和宇智波鼬的最近共同祖先 文件目录树: 找出两个文件或目录的最近公共上级目录。 计算机网络: 确定网络节点间的最短路径。 深度优先搜索（DFS）在LCA算法中的应用深度优先搜索（DFS）是一种遍历或搜索树或图的算法。DFS从根节点开始，沿着树的深度进行搜索，直到访问所有节点为止。在LCA算法中，DFS用于计算每个节点的深度并记录其祖先信息。 二进制提升（Binary Lifting）方法的原理二进制提升是一种 ...

6bff9e0034a7ab19c181f77c4247aa4d4bc19fdd86a9d15c064feadb00bf18484a5688a39183b7261472c699008eb21eee037dab7158ed698339d49b45dec9da56993a59042cf36217d5bc4236ab75b90ac36d4e126271079f5cc9449d2f2737d6e4a54ab18bb39c05a6acfdbd4d21e4a1a7cadc07de21e4629bb9bd5a84e835027bb0d18413bd030651a4a1d2c6a83819db1ccc3a40d0a6e99032d008e4b5c3b259992b45ee1621474042beff7d6570afc5bcfce6f7b5a15f3b1384bd19e615117d7aa5a4661ccf786f083811c19cae5cdda9f9de2d0b4aa77a8eb3b417eb9cb811e0aab2362488886951f92a3412e04e2cb81f38c028547 ...

零门槛打造个人图床：感谢Telegraph-Image幕前小话很早之前，我就用 GitHub 和 Cloudflare 搭建了自己的图床，不过没多久就发现 cf 自带的 dev 域名被墙了，于是就没再管它。直到上周，我在课上无聊时用手机随便翻了翻后台，没想到竟然又能打开了！并且后台多出了200多张网友上传的图片。既然又能用了，我就想着，把这个教程分享出来，也许能帮到需要的人。 注意： 本文中的图片均使用该图床服务，如果图片无法加载，则意味着教程可能已失效。 准备工作 一个 GitHub 账号 一个 Cloudflare 账号 在 GitHub 上创建和配置仓库 访问 Telegraph-Image 并将其 fork 到你的账号下。 使用 Cloudflare Pages 搭建图床服务 登录 Cloudflare，并根据下图指示连接到 GitHub。 选择你刚才 fork 的仓库并开始设置。 按照默认设置保存并部署。 部署成功后，会显示一个页面，其中包含图床的网址。 绑定个人域名（可选）如果你有个人域名，可以将其托管到 Cloudflare 上，并在自定义域名设 ...

Codeforces Round 920 (Div. 3) D、E题解D. Very Different Array E. Eat the Chip D. Very Different Array 题解解题思路在这个问题中，我们使用了贪心算法来最大化Vasya数组和Petya数组之间的总差异$D$。 1. 排序首先对Petya的数组$a_i$和Vasya可选的数字集合$b_i$进行排序，为双指针操作做准备。 2. 双指针策略使用两个指针，分别指向$a_i$的两端和 $b_i$ 的两端。 3. 贪心选择 在每一步中，计算$a_i$两端与$b_i$两端的差的绝对值。 选择四种可能差值中的最大值，并累加到结果变量$D$中。 相应地移动指针。 4. 重复以上步骤直到$a_i$中的所有元素都被处理完毕。 通过这个过程，我们每步都选择当前最大的差异，确保了$D$的值尽可能大。最后输出最大总差异$D$。 代码实现1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515 ...

Python 快速入门0.前景知识🧀本教程适用于学过c/cpp语言者快速入门Python 0.1c语言变量的数据类型是事先定义的，而python是后天接受的，即python会在运行时自动识别变量类型0.2123x=1y=2x,y=y,x # 类比swap(x,y) 0.3字符串用单引号双引号都可（3个单/双引号表示长字符串–>解决多换行问题） 12345678print('Life is short,you need Python')print("Life is short,you need Python") # 自带末尾换行\nprint('''aaaab''')print("hello world\n"*20) # 输出二十行相同字符串 0.4 缩进是命📢缩进代表代码块 1.输入a=input() 给 $a$ 赋值 a=input("请输入a:") 终端显示 请输入a: 后，可输入 $a$ 搭配强制类型转换： ...

Better Input：VSCode插件开发指南0.准备工作先安装（更新） node.js 和 nmp node 更新 去 Node.js 官网下载最新版本，然后重新安装在原来的安装路径下（第一次下载可只进行第三步） node -v查看当前版本是否是最新版本 where node 查看之前的安装路径 去 Node.js 官网下载 LTS 版本 执行 node -v 查看现在的版本信息 npm -v 更新 查看当前版本 npm install -g npm 更新版本 npm cache clean --force 清理 npm 缓存数据 1.创建项目 npm install -g yo 安装 Yeoman 工具集 npm install -g generator-code 安装 generator-code 模块 yo code 创建新项目 2.编写插件打开项目，按下 F5 ，会打开一个 扩展开发宿主VSCode 这个窗口包含了你编写的插件 在命令面板( Ctrl+Shift+P )中输入Hello World命令，会在右下角出现 Hello World f ...

Codeforces Round 898 (Div. 4) E题题解E. Building an Aquarium 样例1如图，用二分法找出 $h$ 。因为 $h$ 可能很大，所以初始化的 $r$ 也开大一点 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include<iostream>#include<algorithm>using namespace std;const int N=2e5+10;typedef long long ll;int nums[N];int s[N];int h;int n,x;bool check(ll h){ ll water=x; for(int i=1;i<=n;i++) { if(h>nums[i]) { water=water-(h-nums[i]); } if(water<0) ...

CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!) A-C题解A. MEXanized Array数列为 [0, 1, 2, ··· k-1, x, x, x, x] 的形式，再扣下细节（ x=k-1， k<n 等 ） 123456789101112131415161718192021222324252627282930#include<iostream>#include<cstring>#include<vector>#include<algorithm>using namespace std;const int N=15;int main(){ int _; cin>>_; while (_--) { int n,k,x; cin>>n>>k>>x; // cout<<"ans:="; if(x<k-1||n<k) { cout<<& ...

Pinely Round 2 (Div. 1 + Div. 2)C题题解C - MEX Repetition C - MEX Repetition 题解由于初始数组是由 $n$ 个互不相同的 $0\sim n$ 的整数组成，所以每次替换的数 $Mex(a_1,a_2,a_3,···a_n)=\frac{n*(n+1)}{2}-sum$ 。答案看起来没什么规律，打表出来发现循环节为 $n+1$ ，故先 $k=k%(n+1)$ 。而每次的 $nums$ 每位依次向后移一位， $add$ 放到第一位，最后一位弹出 找到规律：答案数组 $ans$ 分为两部分 $ans$ 的前k位为每次 $add$ 的数（倒序） $ans$ 的后 $n\sim k$ 位是初始数组 $nums$ 的前 $k$ 位， 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172 ...

Codeforces Round 896 (Div. 2) C题题解C. Fill in the Matrix C. Fill in the Matrix 题解特判 $m=1$ 时，输出 $0$ 找规律，当 $n$ 很大时， $ans=m$ ，$m$ 很大的时候， $ans=n+1$ 即最后的矩阵第一列中出现 $0$ 不出现 $1$ ，第二列不出现 $0$ ，第三列出现 $0$ ， $1$ 不出现 $2$ ，最终的 $v_1=1,v_2=0,v_3=2···v_m=m-1$ 即构造出如下矩阵： 0 1 2 3 4 4 0 1 2 3 3 4 0 1 2 2 3 4 0 1 0 1 2 3 4 4 0 1 2 3 3 4 0 1 2 注：第一列不出现 1 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<iostream>#in ...