抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

就是三倍经验 题意 维护一个序列,每次修改后求出当前序列逆序对个数。 思路 题目让我们求出 \[ \sum_{i=1}^n\sum_{j=i+1}^n[a_i>a_j] \] 也就是让我们求出满足 \[ pos_i<pos_j\&\&a_i>a_j \] 的点对数量。 对于不修改的情况,这显然是一个三维偏序问题,用树状数组或归并处理都可以。...

无用的文字 又是一篇笔记,因为不做题的话太容易忘了啊啊啊QAQ看到一个题目知道用什么算法做但就是想不出来的感觉太难受了…… 二分图最大匹配 二分图 二分图是指可以被分为两个不相交点子集的图,其中相同点集内无连边。 匈牙利算法 匈牙利算法是用来寻找最大匹配的一个算法。 交替路:从一个未匹配点出发,依次经过非匹配边、匹配边、非匹配边……形成的路径叫交替路。 增广路:从一个未匹...

算法描述 基数排序(又叫做桶排序)是一种非比较排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别进行排序。 基数排序的步骤如下: 找出最大数,确定位数。 确定每个位数的范围,并统计每个数字在每个位数上的数量。 位数从低到高按每个位数从小到大进行排序。 输出排序后的数组。 123456789101112131415161718192021222324252...

为了给同学讲课,做了一个平面几何入门的课件,保存在网上。 平面几何入门 奇怪的是明明是平面几何还写了一点三维的东西。应该叫计算几何的。

并查集 并查集是一种树型数据结构,用于处理一些动态集合的合并及查询问题。 并查集的基本操作有: 合并:将两个集合合并为一个集合。 查询:判断两个元素是否属于同一个集合。 并查集的应用场景有: 动态连通性:判断两个点是否连通。 最小生成树:计算最小生成树。 路径压缩:减少树的高度。 并查集优化 并查集有两种启发式优化。第一种是路径压缩,即将每个节点的父节点压...

算法描述 运用了分治的思想,将一个数组分成几乎相等的两份,分别将两段中第一个最小的数拿出来放在一个临时数组中,直到全部取完。因为是递归的,所以每一段的数列都是排序好的。 1234567891011121314void merge_sort(ll *A,ll *B,int x,int y){ if(y-x<=1)return; int mid=x+(y-x)/2; int ...

快速幂 快速幂是在进行底数相同的乘法运算而幂数又极大的情况下使用的一种算法。 将幂次做二进制拆分,然后从低位到高位维护幂次积,同时若该位为 1 乘入答案。 模板 P1226 【模板】快速幂 12345678910111213141516171819202122#include<iostream>#include<cstdio>#define int un...

贝祖定理 如果 \(a\)、\(b\) 是整数,那么一定存在整数 \(x\)、\(y\) 使得 \(ax+by=\gcd(a,b)\)。 换句话说,如果 \(ax+by=m\) 有解,那么 \(m\) 一定是 \(\gcd(a,b)\) 的若干倍。(可以来判断一个这样的式子有没有解) 有一个直接的应用就是 如果 \(ax+by=1\) 有解,那么 \(gcd(a,b)=1\)。 ...

斐波那契数列 \(F(0)=F(1)=1\) 或 \(F(1)=F(2)=1\),\(F(i)=F(i-1)+F(i-2)\). 广义斐波那契数列在转移时有系数且首两项给定。 求法 注意到斐波那契数列的转移为一个矩阵乘 \[ \begin{bmatrix}F(i)&F(i-1)\end{bmatrix} \begin{bmatrix} 1&1\\ 1&...

这是之前博客园的草稿,写得不好,本来想直接删除了事。然而,斜率优化是一个很重要也很基础的优化问题,是需要学习掌握的。但我现在没有精力写一篇新的文章了。 OI wiki: 斜率优化

点击播放键加载歌单