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

如果每个点都是基站，问题即求完全图最小生成树的最大边。 那么如果去掉原图中不是基站的点，即建一个新图，两个基站连一条边权为最短路的边，题目就变成上面的情况了。 因此可以考虑优化这个连边。设 表示离 最近的基站，跑多源最短路即可求出。那么对于一条边 ，如果 ，则在 和 间连一条边权为 的边即可。这样子正确性比较显然。 然后就是 Kruskal 的事了。 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ===========================...

仔细观察一下，发现要求的就是环上两段最大子段和，因为你总是可以通过翻转把这两段拼在一起。 这是一个经典问题（Luogu），直接正反贪心一遍拼在一起，取相反数后再做一次即可。 需要注意的是可能要特判全是负数的情况。 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(#x".i...

模拟出一次操作后的排列，那么一次操作相当于乘上了这样一个置换。找出所有环，则每个数会在环上移动 步，按顺序求出环上的元素，那么加上 后对环长取模即可得到最后的数。 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) freopen(#x".in","r",stdin); freopen(#x...

考虑容斥，即任意拆分的方案数减去拆分成不喜欢的数的方案数。 先考虑前者。设 表示 任意拆分的方案数，则有 即 再考虑后者。考虑 DP，设 为 拆分为不喜欢的数的方案数，则有 因为 ，所以把相邻的 个状态存到矩阵里，然后矩阵快速幂即可。 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #define file(x) fr...

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