xixike

# Description P4178 Tree # Solution 前两天 vp 时碰到一道需要在每个点维护一棵平衡树，同时需要树上启发式合并的题，然鹅发现自己不会写。 无意中发现这道题似乎也可以使用同样的做法。 大概思路是，对于每个点，先继承它的重儿子的平衡树，然后依次枚举所有的轻儿子，先统计答案，再合并平衡树。 统计答案与合并平衡树时，直接遍历轻儿子平衡树内所有的点即可。 具体来说，平衡树中存的值是子树内每个点到当前平衡树的根的点的距离。 假设当前处理到 xxx 节点，我们先计算一端为 xxx，另一端在重儿子子树内的合法点对数，即在重儿子的平衡树中查找小于等于...

Here's something encrypted, password is required to continue reading.

输入两个整数 n,mn, mn,m，要求找到一组 x,yx, yx,y，使得 x+y=nx + y = nx+y=n 且 lcm(x,y)=mlcm(x, y) = mlcm(x,y)=m，输出 x,yx, yx,y。 考虑最暴力的做法，枚举 xxx，暴力计算，时间复杂度 O(nlog⁡n)O(n\log n)O(nlogn)。 转化一下条件，gcd⁡(x,y)=x×ylcm(x,y)\gcd(x, y) = \frac{x\times y}{lcm(x, y)}gcd(x,y)=lcm(x,y)x×y​，由于 x+y=nx + y = nx+y=n，即 y=n−xy = n -...

# 浙江省选集训游记 # 3.5 昨天刚考完春季测试，今天就要 run 去诸暨海亮了。 上午 9:30 的火车，坐 7 个半小时，先到杭州再转车去诸暨。 上车先码了一会春季测试的游记，还没有码完就 11 点了，跟 AcestarAcestarAcestar 和 fzj2007fzj2007fzj2007 组队打 thupc\text{thupc}thupc。 开场先看 CCC，感觉不是很可做的样子，过了两分钟去看了下榜，发现有一车人过了 MMM。于是去看 MMM，题意就是直接输出五支球队中小 EEE 认为最强的球队，看见法国两次世界杯冠军于是直接输出 France...