Educational Codeforces Round 71 Div.2 解题报告 (CF1207)

D – Numbers of Permutations

思考量很小的一道题。

先用间接法来算。初始答案为\(n!\),然后考虑容斥掉那些符合排序规则的方案。发现,我们可以分开来考虑,按照容斥的顺序:先考虑只算第一维、第二维的,在加回来两维都考虑的。

第一维和第二维的做法非常显然:排序之后用多重集的排列就行了,考虑每一个相同的区间里面内部乘起来。如果有\(k\)个连续的数段,那么部分的答案就是\(\prod_{i = 1}^l len_k!\)。

继续阅读Educational Codeforces Round 71 Div.2 解题报告 (CF1207)

LCT 的一类题目

LCT 简述

LCT (Link Cut Tree) 是一种维护树链的灵活的数据结构。与线段树不同的是,LCT 一般使用 Splay 这种非常优雅、灵活的数据结构来维护树链。因为 LCT 支持动态增边、删边,所以很多题目就可以打破一些限制进行求解。

继续阅读LCT 的一类题目

[Fortuna OJ]Aug 5th – Group A 解题报告

A – 矩阵游戏

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

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

继续阅读[Fortuna OJ]Aug 5th – Group A 解题报告

[Fortuna OJ]Aug 4th – Group A 解题报告

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

A – Forging 锻造

在考场上我推了个有后效性的 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} \]

继续阅读[Fortuna OJ]Aug 4th – Group A 解题报告

主席树总结

简述

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

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

From Wikipedia.org

继续阅读主席树总结

单调队列学习笔记

简单的问题引入

例题:CH1201

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

以前写的题解:CH1201:最大子序和题解

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

继续阅读单调队列学习笔记