【题解】华南理工大学“三七互娱杯”程序设计竞赛（重现赛）

A: HRY and codefire

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

这里的转移涉及到了环，可以联立下面的方程组：

消元之后得到：

可以通过先计算i+j大的dp(i,j)来计算整个dp数组.

时间复杂度O(n^2) 。

B: HRY and fibonacci

先计算fib(n)的前n(n>=3)项和：

可以通过类似的方法求出 fid(n)=fid(n-1)+fid(n-2)+n,fid(1)=1,fid(2)=3.

线性递推，考虑矩阵快速幂优化。此题是区间操作，考虑线段树。

线段树每个节点维护

,然后区间加1的时候，相当于做矩阵乘法：

如果是加正整数x的话同理，先用矩阵快速幂求出转移矩阵的x次方，再进行线段树节点值的更新。时间复杂度O（4^3Qlog(le14)) 。

C: HRY and Abbas

枚举每个位置，计算从它开始下一颗子弹在的位置。有一个简单的写法，考虑每两个相邻子弹之间的长度（不含有子弹的位置）

,那么

D: HRY and array

要求输出30位小数，模拟除法即可。

时间复杂度O(n) 。

E: HRY and balls

盒子数很少，而且可以知道每个盒子最多***作一次，考虑状态压缩dp 。

首先去掉不需要操作的盒子，即那些一开始的时候，盒子里面的球所在的位置均已经是正确的盒子，显然这些盒子不需要进行操作。

cnt(s,i)表示已经操作了集合s的盒子，盒子i当前的球数。

dp(s)表示操作完集合s的盒子需要最少的时间。

F: HRY and ec-final

首先意识到10^9内最大的素数间隔不会很大，打表暴力计算一下可以知道最大素数间隔不到300,也就是说，如果给定的序列是从1-10^9 的欧拉函数截取下来的，那么肯定有一个位置是素数，素数p的欧拉函数是p-1,枚举每个位置，假设这个位置是素数，然后暴力计算相应位置的欧拉函数，看是否能对应上。理论时间复杂度是

，但是远远达不到这个数值，加上剪枝（每当有一个位置对应不上的时候就退出这个位置的计算）之后非常快。

G: HRY and tree

考虑计算每个边的贡献，按边从小到大排序，每次取出最小的边插入，并计算边连接的两个联通块的大小，这条边的贡献是

.正确性显然。

维护联通块大小可以用并查集。

时间复杂度O(kn),此处k指反阿克曼函数，在这里可以看作一个非常小的常数。
可能也能用点分治卡过去，这是点分治裸题，为了让套点分治板子的选手难受一点，特意把数据开到百万级，要是还能用点分治过这题，说明常数十分的优秀。。。

H: HRY and Fight the landlord

没啥好说的，照着题意模拟就行了，祝大家打牌开心。。。

给几个特殊数据好了：

A A A A 2 2 2 2是N0； 3 3 3 3 4 4 4 4是Ye5

I: HRY and Repeaters

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

时间复杂度O(300000log) 。

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

K: HRY and ball 2

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

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