「Fortuna OJ」Aug 5th – Group A 解题报告

A – 矩阵游戏

这道题看了题解之后发现就是一道 sb 题。

考虑将每一列看成一个数，发现如果忽略掉列的操作，这些数仍然满足等差的条件，所以我们只要暴力算完第一列就可以进行等差了。如果考虑列的操作，那么我们就大力暴力就行了，时间复杂度是\(O(n + m)\)。

今天被各路神仙吊打，顺利 gg。

在考场上我推了个有后效性的 DP，还以为是高斯消元，然后看到数据范围就 GG 了。这道题主要是把一些东西给转换掉了。

首先，对一个概率为\(p\)的事件，它的期望次数是\(\frac{1}{p}\)（参见这里）。然后，考虑一个状态\(dp[i]\)代表合成第\(i\)级武器的期望花费。显然\(dp[0] = a\)。

考虑\(dp[1]\)的求法，首先需要两个级别为\(0\)的武器，然后发现无论失败与否都可以保证至少又一个\(0\)级武器，所以我们只需要注意另外一个武器的花费就可以了：

\[ dp[1] = dp[0] + dp[1] \times \frac{1}{p} \]

主席树是一个很有意思的数据结构，其全称其实是「可持久化线段树」，至于为什么叫「主席树」是因为：

由于发明者黄嘉泰姓名的缩写与前中共中央总书记、国家主席胡锦涛（H.J.T.）相同，因此这种数据结构也可被称为总书记树或主席树。

From Wikipedia.org

例题：CH1201

输入一个长度为n的整数序列，从中找出一段不超过m的连续子序列，使得整个序列的和最大。

首先思考暴力：枚举端点和不大于\(m\)的长度，前缀和搞一搞就好，时间复杂度为\(O(n^2)\)，肯定超时。我们可以考虑优化这个算法。