M_sea

分类

未归档(1) 题解(5)

/ 注册

全部文章（共6篇）

小A的排列题解

一个暴力是枚举左右端点，用 set 求中位数，然而是的。但是我们注意到，在加入一个数后，中位数至多只会移动个位置，即不变或者变成前驱或后继。于是我们需要支持一个插入、求前驱后继的数据结构，发现并找不到。但是我们可以倒过来变成删除，这样子就可以用链表维护了。 // ========...

OI

2020-10-04

0 619

基站题解

如果每个点都是基站，问题即求完全图最小生成树的最大边。那么如果去掉原图中不是基站的点，即建一个新图，两个基站连一条边权为最短路的边，题目就变成上面的情况了。因此可以考虑优化这个连边。设表示离最近的基站，跑多源最短路即可求出。那么对于一条边，如果，则在和间连一条边权为的边...

OI

2020-10-02

6 742

翻转题解

仔细观察一下，发现要求的就是环上两段最大子段和，因为你总是可以通过翻转把这两段拼在一起。这是一个经典问题（Luogu），直接正反贪心一遍拼在一起，取相反数后再做一次即可。需要注意的是可能要特判全是负数的情况。 // ==================================== // ...

OI

2020-10-02

6 757

排列题解

模拟出一次操作后的排列，那么一次操作相当于乘上了这样一个置换。找出所有环，则每个数会在环上移动步，按顺序求出环上的元素，那么加上后对环长取模即可得到最后的数。 // ==================================== // author: M_sea // we...

OI

2020-09-05

6 581

拆分题解

考虑容斥，即任意拆分的方案数减去拆分成不喜欢的数的方案数。先考虑前者。设表示任意拆分的方案数，则有即再考虑后者。考虑 DP，设为拆分为不喜欢的数的方案数，则有因为，所以把相邻的个状态存到矩阵里，然后矩阵快速幂即可。 // ========================...

OI

2020-09-05

3 564

M_sea 真正的博客

http://m-sea-blog.com 欢迎来玩 QAQ

2019-10-29

1 630