华南理工大学软件文化节“三七互娱杯”程序设计竞赛题解

未分类

---

A: HRY and signin problem

签到题，直接输出就好了。时间复杂度 $O(1)$。

B: HRY and codefire
令$dp(i,j)$表示当前两个账号分别是$i,j$级，并且下一场比赛使用$i$级的账户参赛，达到$n$级仍需要的参赛次数的期望。那么初始化$dp(n,i)=dp(i,n)=0,i \geq 0$，然后转移是:

$$dp(i,j)=p_idp(i+1,j)+(1-p_i)dp(j,i),0 \leq i,j < n$$ .
这里的转移涉及到了环，可以联立下面的方程组：
$$dp(i,j)=p_idp(i+1,j)+(1-p_i)dp(j,i)+1\\dp(j,i)=p_jdp(j+1,i)+(1-p_j)dp(i,j)+1$$
消元之后得到：
$$dp(i,j)=\frac{p_idp(i+1,j)+1+(1-p_i)(p_jdp(j+1,i)+1)}{1-(1-p_i)(1-p_j)}\\dp(j,i)=\frac{p_jdp(j+1,i)+1+(1-p_j)(p_idp(i+1,j)+1)}{1-(1-p_i)(1-p_j)}$$
可以通过先计算$i+j$大的$dp(i,j)$来计算整个$dp$数组.
时间复杂度$O(n^2)$。

C: HRY and fibonacci
先计算$fib(n)$的前$n(n \geq 3)$项和：

$$\begin{align*} fic(n) &= \sum_{i=1}^nfib(i) \\ &= fib(1) + \sum_{i=2}^n fib(i) \\ &= fib(1) + fib(2) + \sum_{i=3}^n fib(i-1)+fib(i-2) \\ &= fib(1) + fib(2) + \bigg (fic(n-1)-fib(1)\bigg )+fic(n-2) \\ &= 1+fic(n-1)+fic(n-2) \end{align*}$$
$fic(1)=1,fic(2)=2.$

可以通过类似的方法求出$fid(n)=fid(n-1)+fid(n-2)+n,fid(1)=1,fid(2)=3.$
线性递推，考虑矩阵快速幂优化。此题是区间操作，考虑线段树。
线段树每个节点维护$\sum_{i=l}^r fid(a_i),\sum_{i=l}^r fid(a_i-1),\sum_{i=l}^r a_i,r-l+1$，然后区间加$1$的时候，相当于做矩阵乘法：

$$\begin{matrix} \bigg[\sum_{i=l}^r fid(a_i), & \sum_{i=l}^r fid(a_i-1), & \sum_{i=l}^r a_i, & r-l+1 \bigg] \end{matrix} \times \begin{bmatrix} 1,1,0,0\\ 1,0,0,0\\ 1,0,1,0\\ 1,0,1,1 \end{bmatrix}$$
如果是加正整数$x$的话同理，先用矩阵快速幂求出转移矩阵的$x$次方，再进行线段树节点值的更新。
时间复杂度$O(4^3Qlog(1e14))$。

D: HRY and Abbas

枚举每个位置，计算从它开始下一颗子弹在的位置。
有一个简单的写法，考虑每两个相邻子弹之间的长度（不含有子弹的位置）$len_i$，那么$ans_1,ans_2,...,ans_{len_i+1}$都加上$\frac{1}{n}$。
时间复杂度$O(n+m)$。

E: HRY and array
考虑$a_ib_j$对答案的贡献为$\frac{(n-1)!}{n!}=\frac{1}{n}$，所以$S$的期望是

$$\sum_{i=1}^n\sum_{j=1}^n \frac{a_ia_j}{n}=\frac{(\sum_{i=1}^na_i)(\sum_{i=1}^nb_i)}{n}$$
要求输出$30$位小数，模拟除法即可。
时间复杂度$O(n)$。

F: HRY and balls
盒子数很少，而且可以知道每个盒子最多被操作一次，考虑状态压缩$dp$。
首先去掉不需要操作的盒子，即那些一开始的时候，盒子里面的球所在的位置均已经是正确的盒子，显然这些盒子不需要进行操作。
$cnt(s,i)$表示已经操作了集合$s$的盒子，盒子$i$当前的球数。
$dp(s)$表示操作完集合$s$的盒子需要最少的时间。
转移式子是$dp(s+\{i\})=min\bigg(dp(s+\{i\}),dp(s)+cnt(s,i) \bigg),i \notin s$
$cnt(s,i)$可以$O(n+m2^m)$预处理出来。
总时间复杂度为$O(n+m2^m)$。

G: HRY and ec-final
首先意识到$10^9$内最大的素数间隔不会很大，打表暴力计算一下可以知道最大素数间隔不到$300$，也就是说，如果给定的序列是从$1-10^9$的欧拉函数截取下来的，那么肯定有一个位置是素数，素数$p$的欧拉函数是$p-1$，枚举每个位置，假设这个位置是素数，然后暴力计算相应位置的欧拉函数，看是否能对应上。理论时间复杂度是$O(300^2\sqrt{10^9})$，但是远远达不到这个数值，加上剪枝（每当有一个位置对应不上的时候就退出这个位置的计算）之后非常快。

H: HRY and tree
考虑计算每个边的贡献，按边从小到大排序，每次取出最小的边插入，并计算边连接的两个联通块的大小，这条边的贡献是$w_i\times size_l \times size_r$。正确性显然。
维护联通块大小可以用并查集。
时间复杂度$O(kn)$，此处$k$指反阿克曼函数，在这里可以看作一个非常小的常数。
可能也能用点分治卡过去，这是点分治裸题，为了让套点分治板子的选手难受一点，特意把数据开到百万级，要是还能用点分治过这题，说明常数十分的优秀。。。

I: HRY and mobius
显然只需要考虑$k=0,1,2$的情况。
$k=0$时 $ans=n$。
$k=1$时 $ans=\sum_{i=1}^n\mu(i)$，用杜教筛计算。
$k=2$时 $ans=\sum_{i=1}^n|\mu(i)| = \sum_{i=1}^{\lfloor \sqrt n \rfloor } \mu(i)\lfloor \frac{n}{i*i} \rfloor$。
时间复杂度$O(n^{\frac{2}{3}})$。

J: HRY and Fight the landlord
没啥好说的，照着题意模拟就行了，祝大家打牌开心。。。
给几个特殊数据好了：
A A A A 2 2 2 2是N0； 3 3 3 3 4 4 4 4是Ye5

K: HRY and Repeaters
先把$n$个母串用不同的特殊符号串起来，求出后缀数组和高度数组来。对每个后缀，记录它是原先的$n$个母串中的第几个的后缀。对每个查询，二分出它在后缀数组中的位置$L,R$，最后需要算的是在后缀数组的$L$到$R$个后缀中，有多少个后缀所在母串是在$l-r$范围内。这个可以建立一个可持久化线段树来计算。
时间复杂度$O(300000log)$。

L: HRY and cats

首先枚举有向线段$ij$（表示第$i$个树桩到第$j$个树桩的向量），判断是否所有猫都在这个向量的左边（用叉乘算），只留下判断结果为“是”的有向线段，然后满足条件的多边形肯定是由这些有向线段组成的。那么可以枚举起点，求起点到其他点最少使用的线段数，也就是求最短路。如果$i$能到$j$且$ji$这个有向线段是合法的，那么$dis(i,j)+1$是一个可行解。对所有可行解求最小值即可。无解输出$-1$。

M: HRY and ball 2
这题是最后加进来的防AK题，题目本身不难，但是因为上面的题都相对简单而且码量不大所以。。
这题是我2017年在去西安参加区域赛的路上想到的问题，当时很久才想出解法来，也写了很久，时隔一年多终于把它拿出来祸害人了。。

令$g(n)=\sum_{i=1}^n(f,i)$，也就是$g(n)$表示把$n$个球分成若干组的方案数。这里盒子是一样的，球是不一样的。那么我们可以枚举前$n-1$个球有哪些和$n$在同一个盒子里，那么就有：

$$g(n)=\sum_{i=0}^{n-1} g(i)C_{n-1}^i$$
转换一下就成了：
$$g(n)=(n-1)!\sum_{i=0}^{n-1}\bigg(\frac{g(i)}{i!} \times \frac{1}{(n-1-i)!} \bigg)$$

令$h(n)=\frac{g(n)}{n!},u(n)=\frac{1}{n!}$，那么就是：

$$h(n)=\frac{1}{n}\sum_{i=0}^{n-1}\bigg( h(i)\times u(n-1-i) \bigg)$$
和式内是卷积形式，考虑$NTT$，不过是自身卷上另一个序列的卷积。。
考虑$cdq$分治，计算$[l,r]$的$h(n)$时，先计算$[l,mid]$的，然后把$[l,mid]$的答案贡献到$[mid+1,r]$中（用$NTT$），然后再计算$[mid+1,r]$。由于给定的模数本身就是可以用的费马素数，所以直接$NTT$就行了。时间复杂度$O(nlog^3n)$。