省选联测41
冤家路窄
意义不大题，先建出最短路图，总方案减去不合法方案，枚举相遇的点和相遇的边即可，但是记得方案数都要按平方算
总结：垃圾大样例
夹克姥爷win了win了
意义不完全大题，结论是 \(k!+k\) 高精度即可，开始你会猜一个 \((k-1)!+k\) 的结论，然后发现不对改一改就对了
证明：Alice 和 Bob 会提前商量，也就是说我们 \((k-1)!\) 个方案不用对应所有剩下的的 \(n-k+1\) 个数，只需要 \(P_n^{k-1}\) 能对应所有的集合 \(C_n^k\) 即可，所以 \(n\) 至少为 \((k-1)!+k\)
那么如何证明 \(n\le(k-1)!+k-1\) 时一定有解呢？考虑构造一张二分图，左部点是集合，右部点是所有 \(k-1\) 个数的排列，那么每个左部点都有 \(k!\) 条边，每个右部点都有 \(n-k+1\) 条边，所以任意挑出 \(x\) 个左部点和跟它们相连的 \(y\) 个右部点，一定满足 \(x\le y\)（因为 \(k!\ge n-k+1\) ），根据 hall 定理，这张二分图一定有完美匹配
总结：维生素B
39与93
考虑将 \(b[i]\) 按照从小到大排序，那么数组每次只用转移到 \(2^{b[i] 的最高位}-1\)，因为 \(\sum_i^nb[i]=m=1e7\)，所以复杂度莫名其妙对了，为 \(\mathcal{O(能过)}\)
总结：卡复杂度
Zbox的刷题I
第一部分不说，答案为 \(\frac{n}{1-p}\),考虑第二部分直接 MiniMax 容斥
因为每道题独立，所以所求即为 \(Max(S)\)，表示的是最后一道题被做对的时间，其中 \(S\) 为全集
\[\begin{aligned} Max(S)&=\sum_{T\subseteq S}(-1)^{|T|+1}Min(T)\\ &=\sum_{i=1}^n(-1)^{i+1}\begin{pmatrix}n\\i\end{pmatrix}\sum_{j=1}^\infty \left(p^i\right)^j\\ &=\sum_{i=1}^n(-1)^{i+1}\begin{pmatrix}n\\i\end{pmatrix}\frac{1}{1-p^i}\\ \end{aligned}\]总结：不会 MiniMax 容斥，维生素B
本场总结
倒序开题，维生素B，没看T2，维生素B，但是倒序开题不是问题，倒序开了三个小时还没切掉，才是问题，维生素B
下次每道题都必须思考之后才开始打，必须先打签到题
省选联测42
猜数字
开动脑筋人类智慧题，取 \(\log\) 二分判断即可
吵架
发现所求的是点集直径，一开始想的是维护虚树最外圈点，发现维生素B，其实就是维护直径，点集直径典中典了，维护直径端点即可
线段树分治+\(\mathcal{O(1)}\) LCA 即可，这样不用删点，或者直接线段树维护，pushup 来带修
总结：直接用线段树维护这个思路没想到，因为这个东西支持较为快速的合并，所以线段树这种分层的结构可以让复杂度达到 \(\log\)，但是下次我还打线段树分治
选数问题 V2
对于一个数出现的偶数次只因子直接无视，所以等于每个数就是俩只因子，\(1\) 也看做只因子，俩 \(1\) 直接特判掉即可，考虑每个数相当于给两个只因子连边，答案就是最小环
发现一个数不可能有俩大于 \(1000\) 的只因子，所以一个环上最多只有一个编号大于 \(1000\) 的点
当我们从一个点开始 bfs/dfs 时，考虑一个环只要有两条非树边就无法被直接搜出来，但是只要从这个环上任意一个点出发 bfs/dfs 这个环就一定能被搜到，因为我们排除了自环并且一个环上最多只有一个编号大于 \(1000\) 的点，即这个环上至少有一个编号小于 \(1000\) 的点，所以从每个 \(1000\) 以内的质数出发做一遍 bfs/dfs 即可遍历所有环
复杂度：\(\mathcal{O(\frac{n\sqrt{n}}{\log n})}\)
总结：以为到了找最小环就变成普遍问题了，结果还要找性质
nnntxdy
先算方案，结果方案不是等概率的，可以考虑在此基础上先 dp 求概率加权，或者先处理方案数，直接 dp 求期望
总结：打 NTT 没调出来，维生素B
本场总结
T1 看错题，耽误极长的时间，T1 T2 打完就十点多了，T3 T4 时间不够，暴力也没搞完
标签：总结,维生素,省选,sum,42,即可,联测,线段,1000 From： https://www.cnblogs.com/Sakura-Lu/p/17167729.html