PDF《NOI 模拟赛试题讨论》

80 - 90pts 对于这一部分数据,m ≤ 2. wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80 - 90pts 对于这一部分数据,m ≤ 2. 以上的递推算法显然可以通过矩阵乘法加速,如果常数较好可以 通过 m =

3 的数据. wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80 - 90pts 对于这一部分数据,m ≤ 2. 以上的递推算法显然可以通过矩阵乘法加速,如果常数较好可以 通过 m =

3 的数据. 时间复杂度为 O(k3 log n),其中 k = ∑ |str| * 2m . wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 我们发现以上的算法瓶颈在于矩阵的阶太高,考虑用容斥原理代 替状态压缩. wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 我们发现以上的算法瓶颈在于矩阵的阶太高,考虑用容斥原理代 替状态压缩. 设g(S) 表示肯定不会包含 S 中的模板串的长度为 n 的密码串数, 则ans = ∑ (?1)|S| * g(S). wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100pts 我们发现以上的算法瓶颈在于矩阵的阶太高,考虑用容斥原理代 替状态压缩. 设g(S) 表示肯定不会包含 S 中的模板串的长度为 n 的密码串数, 则ans = ∑ (?1)|S| * g(S). g(S) 可以很容易用矩阵乘法加速动态规划的算法求出,时间复杂 度为 O(2m * k3 log n),其中 k = ∑ |str|. wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . paint 画心 渠是一名画师.渠有一支神奇的画笔,可以画尽因果. 渠要画一幅画,这幅画由 n 个线段组成,线段从

1 开始编号,第i条线段有一个特殊的因果值 Ai. 渠打算将这 n 条线段分成若干组来画,每一组的长度要求在 [l, r] 之间,且必须是编号连续的一段. 对于因果值之和为 x 的一组线段,渠画完后种下的因果为 ax2 + bx + c.渠想知道渠将这 n 条线段画完,最多收获多少因果呢?

1 ≤ l ≤ r ≤ n ≤ 152501, |Ai| ≤

109 wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20pts 对于这一部分数据,n ≤ 10. wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20pts 对于这一部分数据,n ≤ 10. 直接枚举分段情况,简单计算即可. wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20pts 对于这一部分数据,n ≤ 10. 直接枚举分段情况,简单计算即可. 时间复杂度为 O(n * 2n ). wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40pts 对于这一部分数据,n ≤ 501. wzj52501 NOI 模拟赛试题讨论 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40pts 对于这一部分数据,n ≤ 501. 设fi 表示前 i 条线段全画完最多收获的因果数,设Si 表示 Ai 的 前缀和. wzj52501 NOI 模拟赛试题讨论 . . . . . . . .........