swift's blog

QOJ5042 & $k$ 进制线性基

https://www.luogu.com.cn/paste/dek7642f

一些之前做过的 AT 题（

支配树

定义点比较大小为 dfs 序。

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

D

http://47.92.197.167:5283/contest/270/problem/4

连成一个环就相当于给每一个点找一个出边连到的点匹配，

QwQ

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

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

UOJ748

UOJ751

找出所有二进制有 $\frac{\log_2 n}{2}$（因为要求是偶数，所以取 $\frac{14}{2}$,${\frac{20}{2}}$） 个 1 的数，把每条边依次用这些数分配一个编号，数量一定是够的。

一个给 B 层的模拟赛，感觉题选的不错（？

只改了题面、写了题解和删掉题目来源。

E 类，(100) + (100+15+0) + (100+8+0) = 323，Ag

感觉这届 NOI 各方面体验特别好。