百度之星初赛（全）
初赛一
打疫苗去了，最后\(30min\)看了看题，打了一题还有一题没调出来。
自己的思路太慢以及打代码速度太慢，别人可以\(40min\)切\(5\)题啊。。。
初赛相对来说不算太难的。
\(T4,T8\)是简单的模拟题。
\(T6\)需要超级快读。感觉自己也需要背背这个板子。
\(T3\)是简单的\(DP\)。
初赛二
这次是准时(迟了\(10min\))开始打的。
从\(T1\)开始打的，是道简单小学数学题。
\(T2\)简单模拟，\(T7\)简单拓扑序，\(T4\)是简单数学题。
\(T3\)是超简单弱化版的欧拉回路(甚至不需要找回路)。
\(T5\)的题意和样例没看懂：
给一个排列，排列可能由两种方式生成：
- 初始为\(1,2,...,n\)，每次等概率随机交换两位，交换\(3n\)次。
- 初始为\(1,2,...,n\)，每次等概率随机交换两位，交换\(7n\)次。
求这个排列是由哪种方式生成。\(50000\le n\le 100000\)
结果这题题解也来了个捉摸不透的解释：
交换 \(3n\) 次之后排列的环的个数或不动点个数会远大于交换 \(7n\) 次之后排列环的个数或不动点个数，直接判断大小即可。
看了看别人的代码，就是判断不动点个数是否大于\(10/50/20/2/...\)，感觉很神奇。。。
\(T6\)感觉并不难，考场有两种想法。
-
以每个叶子(且是直径一段)为根做一波，乘积之和。
-
想的是找重心然后看每个深度的个数，\(C(2,t[dep])\)的乘积，但是错了。
看来是我考虑不够周全。。。
正解和我的第一个想法其实很相似了，但是有些情况会算重：
就是刚好\(S\)中的点是一条直径的情况，这样直径两端都可以算到这种情况，需要特别减去这种情况即可。
而减去这个极其容易，只需要在\(dfs\)的时候顺便记录一下\(mxdep\)的个数，最后的\(ans\)减去\(sum/2\)即可。
初赛三
咕咕咕了。