komorebi edited 1 年，10 月前
This is a past version of blog 2023 年上海市大学生程序设计竞赛 - 一月赛 题解
By lbromine
签到题，如果朋友回答的不是No，则把两个名字都用 $map$ 打上标记。
最后再枚举一遍所有朋友，如果没有标记就 $ans++$。
By Amuzi
注意到$5+8=13$。
首先考虑$n$为$13$的倍数的情况，即$n=13\times k$。因此总的解题思路是：先把$1$到$13$的数重新排列，再每连续$13$个数分成一组，把$n$分成$k$组，最后使用鸽笼原理求解答案。
先思考第一个问题，把$1$到$13$的数重新排列，使任意$2$个相邻的数差为$5$或$8$。
这个问题只能逐步尝试，从$1$开始尝试不难得到：$1、6、11、3、8、13、5、10、2、7、12、4、9，$就是满足题目要求的一个排列。
再思考第二个问题，每连续$13$个数为$1$组，每个组都按步骤$1$的方法排序，任意一个组中最多取出多少个数，使任意两个数的差不是$5$也不是$8$？
这个问题比较简单，注意到每组第$1$个数和第$13$个数差为$8$，且任意相邻$2$个数都不满足条件，故最多是隔一个数取一个，且第一个数和最后一个数不同时取，因此每个组最多取出$6$个数。
综合上述几个问题，考虑原题目的答案。把这$k$组当作鸽笼，根据鸽笼原理，对任意$k\times 6+1$个数来说，定有一个组中至少有$7$个数。结合步骤2的结论可得：对$1$到$n=13\times k$中的任意$k\times 6+1$个数，一定有$2$个数的差是$5$或$8$。因此本题的答案不大于$k\times 6$，下面将构造出$k\times 6$个数满足条件：
按照在步骤1的规律，第$1$组取$1、2、4、5、8、11$，第$2$组取$14、15、17、18、21、24$，以此类推，第$k$组取$13k-12、13k-11、13k-9、13k-8、13k-5、13k-2$。则取出的$k\times 6$个数满足题目要求。
然后考虑$n$不为$13$倍数并且大于$13$的情况，易发现最优取法与成倍数时并无区别。
最后考虑$n$小于$13$的情况，答案易知。
By Komorebi
把正确的阵法里的#和目前的阵法里的#连边，代价为他们之间的欧氏距离，就是一个带权二分图最优匹配的问题，套KM算法即可。
可以涉及到一些优化，例如.较多时用.进行连边。
时间复杂度 $O(T\times n^6)$ ，优化后常数可以很小。
By Amuzi
观察到$P1\gt P2\gt P3$。这是个典型的枪手博弈，不难想到，Komorebi会先攻击Amuzi再攻击lbromine，而其他两个人都会先攻击Komorebi。
那么弄清楚攻击顺序之后，就是个简单的状压$DP$。用个二维$dp$数组表示下第$n$轮各种情况的概率。然后按照对应概率直接暴力转移即可。
当然，还有一些分类讨论的做法，本质其实是一样的。
这个简单的状压$DP$显然可以用矩阵快速幂优化。矩阵大小是$6\times 6$的。也就是说$n$可以开到$1e9$及更高，那么有一些比较纯粹的讨论就会被卡掉。
By Komorebi
我们把$x,y,k$看作常数，令
$$F[n]=\sum_{i=0}^{\lfloor \frac{n}{k} \rfloor}x^{n-k\times i}y^iC_{n-(k-1)\times i}^{i}$$
通过打表或推导会发现这个式子等价于
$$F[n]=xF[n-1]+yF[n-k]$$
对于$n\lt k$的部分暴力求，$n\gt k$的部分可以套矩阵快速幂求解。
对于$k=1$的情况再矩阵快速幂过程中需要小心处理，或者直接拎出来特判。
时间复杂度 $O(k^3\times \log~n)$
By lbromine
题意可抽象为给定一颗 $n$ 个节点的树，有边权，$q$ 次询问，每次询问一个区间 $[l,r]$
求 $min[\ dis(u,v)\ |\ \forall u,v\in [l,r],u\ne v\ ]$
如果只有一个区间，则可以考虑点分治
每个点在点分树上最多有 $log\ n$ 个祖先，于是可以把每个点在点分树上的所有祖先和该点到它的的距离预处理出来。然后枚举$[l,r]$的所有点，对于每个点更新他所有祖先到$[l,r]$的最小和次小距离。最后枚举所有祖先，对最小距离与次小距离之和求最小值即可得到答案。
对于 $q$ 次询问，可以将询问离线，使用回滚莫队即可解决。
时间复杂度 $O((q+n)\sqrt n logn)$