【题解】南华大学第16届ACM程序设计大赛（重现赛）

A.地理学带师:模拟，签到

n比较小，模拟即可.

B.Matrix multiplication: dp

在某些情况下，矩阵乘法的方案比较多(比如 所有矩阵行列全等的情况,这将是一个阶乘级别的大小)，但是n比较小，而且需要所有矩阵都要能连乘起来。考虑状态压缩dp。

输出字典序最小的方案就逆着全集贪心输出即可。

另一种思考方式。将每个矩阵抽象成一个点，两点之间连一条边当且仅当两个矩阵能够相乘。那么问题转化为在一张图上统计哈密顿通路个数。也是经典状压dp。

C.拦截导弹:数据结构

核心在于：快速找到序列中从左至右第一个小于导弹高度h的位置。n比较大，暴力行不通。考虑引入高级数据结构维护。

①建立线段树，在维护区间最大值,线段树上二分的查找一下即可。复杂度

②分块。暴力按块找即可。复杂度可以证明为

D.只不过是另一个高斯罢了:组合数学，数学定理优化

①通过打表找规律或者从定义式出发化简式子可以发现递推式g(h,n)=g(h–1,n)+g(h,n–1)

②熟悉组合数学/dp 的朋友不难发现这样的递推式的一种实际含义为：在二维网格上求起点到终点的非降路径和方案。存在一种组合数的求法。所以问题转化为求解组合数。

③观察到h,n十分大，但是模数很小，考虑使用Lucas定理进行优化。

E.吃豆豆:前缀和，STL优化。

比赛的时候发现很多人用尺取，二分去写。其实题目中说明了数据可能是负的，故不符合单调性，需要引入STL去给前缀和排序，再二分。

题目条件转化为:sum[R] – sum[L] <= Max ，要使得不等式左边尽量大，枚举右端点.转换为让sum[L]尽量小。又需要Sum[L]>=sum[R] – Max.  显然用Map记录下每一个前缀和,形如二元组(前缀和,出现次数).然后Map上二分一下求出Sum[L]对于R符合上述条件(注:Sum[L]的值可以保证是唯一的，但出现次数是不一定的，所以要用二元组去保存它们),这个过程中维护最优解Ans。

很容易发现对于每个右端点，它不一定有确定的左端点，但是会有确定的前缀和的值。所以对于每个右端点，存一个二元组(sum[R] – sum[L] , 对应sum[L]个数). 最后O(n)扫一遍，当 二元组的第一维 == 最优解Ans就将二元组的第二维统计进答案就好.

F.Strang multiset:数论，筛法，预处理

通过阅读伪代码发现:函数功能就是求一个数的最小素因子。由于询问比较多且数比较小，可以预处理利用素数筛将所有数的最小质因子筛出来，进行模拟即可。

直接模拟行不通，假设询问的都是质数，那么复杂度会跑到