日记

上午#

正如昨天所说，今天考 NOIp 模拟赛（我何德何能能考 NOIp 模拟赛啊）。这题也是难得有点遭不住。
打不起一点的模拟赛 似乎能看的题解

T1：经过一番的暴力，也是直接试出来一个结论：把 $a$ 中最小的 $\frac{n}{2}$ 个和 $b$ 中最大的 $\frac{n}{2}$ 个来配。这之间，$a$ 中的 $\frac{n}{2}$ 个和 $b$ 中的 $\frac{n}{2}$ 个的顺序是不用考虑的。因为它们之间的顺序如何交换 $value$ 都是一样的。剩下的 $\frac{n}{2}$ 个也一样。这对于偶数 $n$ ，情况就很明确。但是对于奇数 $n$ ，好像对于上面的 $a$ 中最小的 $x$ 个和 $b$ 中最大的 $x$ 个，这个 $x$ 取 $\frac{n+1}{2}$ 或者 $\frac{n-1}{2}$ 都可以。但是结论推出来了，要知道要 swap 多少次还不容易。在这里卡了 $2h$ 最后还是放弃了。

T2：把第一个特殊性质打了，然后又打了一个 dfs 暴力。只拿了 $30$ 分。

T3&T4：没看，不写。

总结：我何德何能打 NOIp 模拟赛啊

下午#

改题，没甚说的。

T1：source
结论如上文所说。然后把 $a$ 中大的和 $b$ 中小的一一对应，然后求逆序对。具体参照题解（其实是我没理解透）
我在赛时的时候都把结论推对了，但是没写出来，我菜啊！！！

T2：source
用最短路树求最小环，但是下午没改出来，所以晚上再说。

晚上#

改中午没改完的题（啊虽然只改了T2）

T2：枚举每一个 $u$ ，对于每一个 $u$ 跑单源最短路，建最短路径树。用并查集维护每个点属于哪个子树。对于每一个在最短路径树上的点 $v$ ，它与根节点组成的环的长度是 $dis_v + a_{u,v}$ ，其中 $a_{u,v}$ 表示 $u$ 到 $v$ 的边长（其实该是 $a_{v,u}$ 的，但是是无向图，所以就无所谓啦）然后对于每条非树边，设这条边从 $a$ 到 $b$ ，如果 $lca(a,b)$ 是 $u$ （就是它俩在不同的子树里），就用 $dis_a + dis_b + a_{a,b}$ 更新答案。时间复杂度 $O(n \times mlogm + n^3)$

小插曲（怎么又是小插曲）：改完T2顿感肚子里翻江倒海，大抵是昨天的烤肉没烤熟。然后就去厕所窜。窜完之后，我只能说：草神说的对。

Attribute Checks#

设 $dp_{i,j}$ 表示智商为 $i$ ，力量为 $j$ 的情况，那么转移就非常显然（啊其实是没时间写），用桶统计就行了。
具体参照这篇题解