little_sheep_xiaoen

摘要： 解决的问题描述： 对于三个自然数$a,b,c$，求解$ax + by = c$的$(x,y)$的整数解 算法解决： 首先我们要判断是否存在解，对于这个这个存在整数解的充分条件是$gcd(a,b)$ $|$ $ c$ 也就是说$c$为$gcd(a,b)$的一个倍数 然后判定是否有解后，我们需要在这个基 阅读全文

摘要： 一、二元线性方程与二阶行列式 （一）二元线性方程的解 设有方程： 可看出$x_1,x_2$的分母相同，由$x$的四个系数组成 而两数分子由三对系数组合构成 （二）行列式 引进一个符号表示“四个数分成两对相乘再相减” 其中，$a_{ij}(i = 1,2 ; j = 1,2)$称为行列式中的元素，且： 阅读全文

摘要： ST表嘛，就是一个可以解决可重复贡献问题的东西，并且很快，但是不支持修改 ST 表基于倍增思想，可以做到在$O(n \log_n)$时间内预处理， $O(1)$回答每个询问 实现+原理 先上代码，就着代码讲原理 1 #include <bits/stdc++.h> 2 using namespace 阅读全文

摘要： 归并排序是利用了分治，在$O( n \log_n )$的时间里完成排序 虽然它比$sort$难打，但是它稳定还快啊（快排的最劣复杂度为$O( n^2 )$，而归并的最劣复杂度还是$O( n \log_n )$） 原理 先拆后合，先将每个大的给拆成两个左右区间，一直拆到左右区间大小都为$1$（即只有一 阅读全文

摘要： 又是被吊打的一天....... 之前写过一遍最小生成树的，找不到了，再来一遍 用最简单的话讲，克鲁斯卡尔就是并查集+sort 排序 在一个图里有很多的边连接很多个点，把这些边按照边权排个序 最小生成树的是从小到大排序 最大生成树（如果可以这么叫的话）是从大到小排序 咱就以最小生成树为例子讲： 选出当 阅读全文

摘要： 题干 就是将$add$和$del$函数里的$ans$变化变成组合数嘛， 先预处理出$x$只相同袜子一共有$f[x] = 1+2+...+$$(x-1)$种组合， 要注意，由于$f[x]$是一直加到$x-1$，所以我们要$add,del$两个函数中都要关注这个问题： $add$函数要先更改$ans$数 阅读全文

摘要： 扫描线就是一条直线在坐标系中平移，一点一点扫其有用的平行线 普通扫描线最基本的应用就是对坐标系上多个矩形进行切割来求他们的总覆盖面积 比如 那具体怎么操作呢？ 看到最后一步图片的虚线了吗？ 所以我们来模拟一波 其中这条移动的线就是扫描线 那做法就很明显了： 我们记录每一条竖直方向上的线段（一个含$x 阅读全文

摘要： 洛谷讲解 莫队基本介绍 莫队算法分为两类，一是莫队维护区间答案，二是维护区间内的数据结构。 特殊的也有树上莫队，带修改莫队、二维莫队等等。这篇文章主要介绍的是普通莫队算法 我们考虑一个问题，给一个序列，m次询问，每次询问你区间 [l,r] 有多少种不同的颜色。 其中n,m $\leq$ 100000 阅读全文

摘要： 在线和离线可以简单的理解为对于所有的操作是否需要读入完毕。 在线：询问还没有结束就输出回答，即边问边运行，问一句答一句 如树套树，且带有“可持久化”的算法（主席树(可持久化线段树)） 离线：在所有的询问都输入完毕后进行运算，再一起输出所有答案 如莫队算法（需要对询问进行整体排序以达到提速的目的） 特 阅读全文

摘要： 题干 这个是用来学莫队的例题，洛谷详解 需要注意的一点，一定要分块！不然会慢很多（直接TLE） 其中分块只在排序的时候要用，并且是给问题右端点分块 再就是注意add与del函数里的操作，增加数量不提，ans的加减可以用完全平方公式推出 上代码： #include<iostream> #include 阅读全文