总结

今天是腊月初十咯，大寒。春天要到啦。所以，慢慢熬，一定能熬出一锅粥的熬出来的。

今天的题目很好，做的还是 div 2。div 1 的最后一题看起来很难。简单讲一下几道题。

今天发挥的还是比较稳定，前两道题都通过了。但是还是要注意写代码时候的一些细节，做到尽量一遍写对代码。但是还是发现了我一直以来写的 dinic 时有问题的，可能复杂度不准确。于是改正了过来。还有对网络流建模的经验很少，不能快速建模。

题解

接下来简单讲一下题解。前两道题并不是很难。

A. 真实排名

就是一个序列，每个数的排名为不小于它的数的数量。然后会有随机个数翻倍，对于每个数求有多少种情况排名不变。就组合数学，分为自己翻倍和自己不翻倍讨论一下就行，维护可以排序后使用双指针。

B. 树的重心

就是给你一个树，求连通子树的重心和原来一样的情况数。（数量也要一样）。

可以维护一个子树最后留下多少个点的情况数。每一个子树加进去合并就行，容易发现最后不是而是的。然后两个重心的就很好求了，直接枚举两边的大小乘起来加就行。考虑一个重心的做法。想到容斥，用总的减去不合法的。就枚举不合法的最大的那个子树，再维护一个前缀合并和一个后缀合并的东西，把这两个东西合并，如果合并后点数小于枚举的这个子树枚举的大小，就是不合法的，容易计算到这样也是的。注意由于容斥，所以合并只需要枚举到，不然会被菊花图卡掉。（考场上没注意到，但是过了，太神奇了）。当然还可以用退背包写，考场上不会。

以后也要注意更准确地分析时间复杂度。

C. 匹配

简单来说，一个二分图边权为 0 或，然后要你找到一组完美匹配使得选出边权异或和为 0。这里使用 dinic 找一组，不合法就暴力 dfs 加一点优化找 1 环就行。

考场上死活没有调出来一直 TLE。考后发现自己 dinic 写法有问题，然后参考了 bronya 大神的 dfs 找环代码，深受震撼，犹如醍醐灌顶。

D. deadline

很好的网络流建模题。简单来说，就是一个二分图，左边的点有一个属性，要么是 0，要么是 1。然后现在右边的每一个点都要选择要么只和 1 匹配要么只和 0 匹配。然后求某种选择使得最大匹配最小，求这个最小值。容易发现相当于分成了两个二分图求最大匹配。然后看到特殊性质二，发现可以使用最小点覆盖。然后想到转换成最小点覆盖的模型。根据邓老师说，这一步乱想就能想到。所以需要多做题，积累经验。然后把两个图揉在一起，发现就行了。

后记

没有什么比较大的失误，还是要重点注意细节。多思考，再动手。稳中求进，力争上游。冬末气冷，暖春未到，还是要注意保护好自己。浮冰融化，草木新生，新的一年要开出新的篇章！前后为难，不进则退，虽然举步维艰，但愿攻坚克难，突破重围。心有猛虎，细嗅蔷薇，顺其自然，刚柔兼济，寻天而行，势如破竹！