swift's blog

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 各方面体验特别好。

引理：有两个线性基 $A,B$ , 设 $B$ 中能被 $A$ 表示的集合为 $W$，且 $(B\setminus W)\cup A$ 线性无关，则 $W$ 为 $A,B$ 所表示张成的空间的交的一组基。

模拟赛 T1 ddtt

http://47.92.197.167:5283/contest/258/problem/1

一个点集为原图，边集极小的强连通图一定可以从一个只包含一个点的强连通分量，每次加一条两端在当前强连通分量里，而中间不在的链或环扩展而成（容易发现这样加入后仍然是强连通分量）。

草莓蛋糕

赛时写了两个 log 的线段树分治+平衡树上二分的做法，没有前途（毕竟线段树分治就一个 log 了，O(1) 计算不太可能）。

CF1369F

发现当所有点权值小于度数时一定无解，考虑最后一条删的边，当删除它时它的两个端点权值一定都是 0。

于是找到一个权值大于等于度数的点，发现即使所有连到它的边都依靠它来删，也是一定合法的，于是把它的所有连接它的边删掉，因为这个点已经发挥了最大可能的贡献，所以如果原图有解，删后的图也一定有解。

2022.7.15 模拟赛 T1

http://47.92.197.167:5283/contest/241/problem/1

考虑在序列上怎么做，对于每一个数 x 设 $v_i$ 表示 i 是否在 x 左面出现，存在一组解的条件显然就是存在一个 a 使得 $v_{x-a} \neq v_{x+a}$，这个不太好处理，于是考虑没有界的条件，就是不存在一个 a 满足上述条件，也就是原串以 x 为中心回文，而回文串可以用正反哈希相等来判断，于是可以线段树维护 $v$ 的区间哈希值。

模拟赛 T2

http://47.92.197.167:5283/contest/236/problem/2