小男娘

分类

题解(3)

/ 注册

全部文章（共53篇）

O(n) 做法

进行一个树形 DP记录向下路径是否包含共四种情况，DP 合并过程中统计答案 #include <array> #include <iostream> #include <vector> using namespace std; using ll = long l...

2026-03-31

5 17

题解 | 小红开宝箱

注意到，于是我们可以将每一个条件当作一条边建立无向图（可以转为并建立自环）。目标为将每一个点匹配一条边。第一步，不断寻找度数为的点并将其唯一邻边和此点匹配；第二步，对于剩余的点，如果度数为，则无解，否则此时图必然为若干个环，对于每一个环，按同一方向匹配环上的边和点即可。维护点的度数，在...

2026-03-26

7 17

题解 | Kevin的矩阵

考虑枚举最终的列数，显然固定列数检查答案时间复杂度是。枚举时进行一个简单的剪枝：从开始分别向左右枚举列数，保证列数始终小于当前最优解。正确性显然。考虑复杂度：首先答案至多为。所以向左枚举的数量至多为，最坏情况此值为。向右枚举同理故最坏时间复杂度为。 #include <climi...

2026-03-25

2 24

一个 O(n^2) 的正解

直接暴力做所有操作即可实测即使区间全卡满也只跑不到三秒，对于测试用例跑的比自己写的分块还要快upd: 不到三秒是错的，因为操作二开销要比操作一更大，会超过三秒。不过全操作二仍然不到四秒，还是稳稳通过。 #include <iostream> using namespace std; u...

2026-03-23

4 50

打假运行时间前十名的线段树做法，附分块做法复杂度分析

只需要一组数据：数组和交替，操作全都是，因为只记录最大以及最小值时询问一定会递归到所有叶子，单次询问时间复杂度，故即可将时间复杂度卡为。附如下分块 + 排序 + 二分做法。如何选取块长：根据代码中的做法，设块长为，则初始化复杂度为，修改复杂度为，查询复杂度为，选取最优，此时...

2026-03-23

3 28

题解 | 不是解的解

目前两个题解都有问题第一篇题解：1000000 可以作为根 1 -1000000 1000000000000 -1000000000000000000 第二篇题解：出题人应能够想到从小到大枚举的做法并且刻意将其卡超时，不存在“通常的假设是测试数据不会极端地将所有小数都设置为解”的说法正解一：显然根最...

2026-03-04

0 37

题解 | 压岁钱

同小红升装备 #include <deque> #include <iostream> #include <vector> using namespace std; int n; int x; int y; int t; int main() { io...

2026-03-02

0 26

题解 | 烟花

初始化全，操作视为区间与，之后区间查或看是否满足条件以上操作都可以使用线段树 #include <iostream> using namespace std; int n; int m; struct Lrv { int l; int r; int v; };...

2026-03-02

0 28

简易题解

A 略 B 答案 C 发现，于是答案为减去最大频数 DE 倍增预处理，倍增找步数时保持，如果最终则可以变成，反之亦然 F set 维护所有的非零元素位置，维护总体异或和，询问在 set 上寻找需要操作的下标然后暴力除，如果变成零就从 set 中移除 G 令距离为。记度数...

C++ 男娘萝莉小男娘小萝莉

2026-02-27

3 63

以防不知道这题可以 O(n) 做

参考铺设道路，我们对于每一个 x 计算 cnt[x]-cnt[x-1] 就做完了使用哈希表可以避免排序复杂度__gnu_pbds::gp_hash_table 比 std::unordered_map 快，并使用 splitmix64 防造数据卡 #include <cctype> #i...

2026-02-09

1 48