C++中priority_queue存储结构体时重载操作符的说明

priority_queue中存储结构体时，需要自定义比较规则，比较绕，这里记录一下。作为大根堆使用时priority_queue<int> heapstruct Seg{int l, r, v; bool operator< (const & t) const{
算法 2023年03月05日 309次浏览

数位DP板子

——该板子来自凌乱之风，风神的总结~，ORZ
算法 2023年03月04日 265次浏览

关于set和multiset自带的lower_bound和upper_bound

lower_bound(a.begin(), a.end(), x)：查找大于等于x的第一个位置，返回的是迭代器。upper_bound(a.begin(), a.end(), x)：查找大于x的第一个位置，返回的是迭代器。C++对set容器使用二分查找时，不能用上面的两个属于alogrithm库的
算法 2023年03月03日 204次浏览

并查集之——单链表式并查集

普通并查集（树状）: p[i]表示节点i的父节点，i所在树的根节点是代表元素。单链表式并查集（单链表状）时间复杂度 O(m元素值域+n)O(m_{元素值域}+n)O(m元素值域​+n)元素值域​+n) ，空间复杂度不同问题不一样。p [ i ] p[i]p[i] 表示 i ii 在单链表形式并查集中
算法 2023年03月02日 400次浏览

单源最短路和最长路总结

单源最短路和最长路一共分为(1) 加法最短路(2) 加法最长路(3) 乘法最短路(4) 乘法最长路套用最短路和最长路就能求啊，所以SPFA当然可以求，SPFA的正确性是基于它的松弛操作，所以自然是可以求乘积最小值和乘积最大值的。考虑Dij为什么不一定行，因为Dij的最短路算法是贪心的，它贪心的选最小
算法 2023年02月27日 186次浏览

关于逆序对

逆序对一般可以用归并排序来做一般的求逆序对如下：给定一个长度为 n的整数数列，请你计算数列中的逆序对的数量。逆序对的定义如下：对于数列的第 iii 个和第 jjj 个元素，如果满足 i<ji<ji<j 且 a[i]>a[j]a[i]>a[j]a[i]>a[j]，则
算法 2023年02月07日 221次浏览

0/1分数规划

最近入门了 0/1 分数规划，于是写篇博客纪念分数规划是一项不常用到的（但还蛮实用的）算法，一般来讲就是求一个最优比率。分数规划的简单介绍分数规划顾名思义就是求一个分数表达式的最大（小）值。比如说有 n 个物品，每个物品有两个权值 a 和 b ，然后让你选出任意件数（但可能会有限制）的物品，使得两个
算法 2023年01月06日 324次浏览

权值线段树

  线段树的两个拓展：动态开点线段树和权值线段树。  线段树有两种写法：堆形式存储和结点形式存储  通常来说，线段树占用空间是总区间长的常数倍，空间复杂度是 。然而，有时候很巨大，而我们又不需要使用所有的节点，这时便可以动态开点——不再一次性建好树，而是一边修改、查询一边建立。我们不再用堆形式中p
算法 2022年12月08日 276次浏览

算法—线段树

线段树之所以称为“树”，是因为其具有树的结构特性。线段树由于本身是专门用来处理区间问题的。对于每一个子节点而言，都表示整个序列中的一段子区间;对于每个叶子节点而言，都表示序列中的单个元素信息;子节点不断向自己的父亲节点传递信息，而父节点存储的信息则是他的每一个子节点信息的整合。线段树就是分块思想的树
算法 2022年12月06日 199次浏览

算法—扫描线

扫描线一般用于解决面积并的问题，最简单的应用是求矩形的面积并。使用针对不同数据范围可以有两种方式。方式一： 利用区间合并暴力求解，时间复杂度为O(n^2*logn)，可以用于解决数据量为1e3级别的问题。方式二： 利用线段树 + 扫描线，时间复杂度为O(nlogn)，可以用于解决数据量为1e5级别的
算法 2022年12月05日 282次浏览