大部分是手机打的,可能有些错字。


萌新刚学 oi,第一次来 ctt(

Read more »

Day -1

Starship IFT-2 推迟到 NOIP 当天晚上了,所以不用纠结考试前一天要不要早睡了(

Read more »

好久没发东西了,把 NOI 2023 的游记在这补一下。

感觉还是没太想好博客应该用来干什么,最近还是比较倾向用云剪切板写一些更像 “笔记” 的东西。

原文是 2023-07-31 23:10:42 写的。

Read more »

支配树

定义点比较大小为 dfs 序。

定义 sdom[x] 为 x 的半支配点,其含义为最小的一个点使得存在一条从它开始到 x 的路径使得路径上除起点和终点的点都大于 x。

Read more »

QwQ

http://47.92.197.167:5283/contest/268/problem/3

发现一组匹配的答案是两棵树上深度相同的祖先对数量, dep1,i=dep2,j(u,v)[u,vT1,i][u,vT2,j]\sum_{dep_{1,i}=dep_{2,j}}\sum_{(u,v)} [u,v \in T_{1,i}][u,v \in T_{2,j}],这个式子最大值能取到 dep1,i=dep2,jT1,iT2,j2\sum_{dep_{1,i}=dep_{2,j}}\lfloor\frac{|T_{1,i} \cap T_{2,j}|}{2}\rfloor,构造方式就是深度从大到小一层层考虑,每层尽量匹配,最多一个匹配不上,而且也不可能出现冲突。

Read more »
0%