map数组思想处理差分数组

用map来处理差分有两个原因1.个别题目中牵扯的数据范围会远远超过普通数组的存储能力，导致空间爆炸。（这种情况也可以用离散化处理）2.需要实时给出结果的，不能全部存下来后处理，这样就不能使用离散化的方式了。如 ====> leetcode 731 我的日程安排表2用map处理的好处还有：  普
算法 刷题 2025年01月03日 24次浏览

自定义排序辨析

C++中通过重载<或者写一个cmp，即可实现自定义排序。但是注意，sort的自定义逻辑和priority_queue的自定义逻辑有区别（本质是底层实现逻辑不同）！以下是关于在 std::sort 中 return a > b 如何反转 < 的逻辑的解释：解释说明：std::sort
算法 2024年12月29日 31次浏览

Topk问题

100亿个数中找topK个数？方法一：堆如果用堆来解决，直观来说，应该建立大根堆。时间复杂度为O(nlogn)+ O(klogn)。但是正确的做法是建立小根堆，思路如下：首先用k个数建立小根堆，然后用剩下的数一个个与堆顶比较。比堆顶大的就和堆顶交换，再调整。最后剩下来的就是top。时间复杂度:O(n
2024年08月16日 231次浏览

链式前向星（存的是边）

e[idx] = b：表示第 idx 条边通向 b 点w[idx] = c：表示第 idx 条边的权值为 cne[idx] = h[a]：表示以a为起点的第 idx 条边的下一条边为 h[a]（-1表示无边）h[a] = idx++：表示点 a 的上一条边为 idx其中 h 数组的大小是点数，其他三
算法 2024年08月09日 242次浏览

ICPC校赛小记&感想

—— 一腔热情最终还是在失败中落寞离场  就以这样的形式记录一下吧。  今年的ICPC校赛原以为是最有希望的一年，队伍实力相较去年也有了较大提升。  初赛中题目过得很顺（除了我上来签到题一发WA），队友猛猛发力，队友BRR更是在一道2D Gray Code题中做出巨大贡献，立马就想出了关键思路，导
算法 2023年11月27日 456次浏览

启发式合并与树链剖分

启发式合并[HNOI2009] 梦幻布丁 - 洛谷#include <bits/stdc++.h>using namespace std;const int N = 1e6 + 10;int now[N], a[N];vector<int> g[N];int n, m, an
算法 刷题 2023年11月07日 425次浏览

MINIEYE杯第十六届华中科技大学程序设计邀请赛补题

MINIEYE杯第十六届华中科技大学程序设计邀请赛——F题=====>《K-th Power》容斥原理：求1~n中可被质数2, 3, 5整除的数的个数。根据容斥原理特点，一般有三种做法：数据量较小时，可用状压方式枚举dfs搜索莫比乌斯函数AC代码：一：dfs方式#include <bit
算法 刷题 2023年11月06日 494次浏览

LRU&LFU实现方式C++

参考文章1、LRUhttps://leetcode.cn/problems/lru-cache/typedef pair<int, int> PII;class LRUCache {public: int cap, cnt; //pair<第几个插入的，val>
算法 刷题 2023年09月25日 423次浏览

三分算法

https://www.acwing.com/file_system/file/content/whole/index/content/1631225/
算法 2023年09月07日 372次浏览

二维偏序问题

知识讲解  二维偏序模板题。把 (a[i], b[i]) 看成二维平面上的一个红点，(q[i][0], q[i][1]) 看成二维平面上的一个蓝点。我们要对每个蓝点求出它的右上方横纵坐标之和最大的红点。  我们将所有点先按横坐标从大到小排序，然后依此枚举每个点。这样遇到一个蓝点 (x, y)，我们只
算法 刷题 2023年06月11日 497次浏览