- 博客(28)
- 收藏
- 关注
RSS订阅
原创 费马小定理与欧拉定理
费马小定理和欧拉定理1.费马小定理1）定义我们现在设正整数a,ma,ma,m且(a,m)=1(a,m)=1(a,m)=1 我们就会有式子 am−1≡1(mod m)am−1≡1(mod m)a^{m-1}\equiv1(mod\ m)2）证明我们设一个完全剩余系A={1,2,3,...,m−1}A={1,2,3,...,m−1}A=\{1,2,3,......
2018-09-11 13:42:43
504
原创 FFT快速傅里叶变换
FFT太玄幻了，不过我要先膜拜HQM，实在太强了1.多项式1）多项式的定义在数学中，由若干个单项式相加组成的代数式叫做多项式。多项式中的每个单项式叫做多项式的项，这些单项式中的最高项次数，就是这个多项式的次数。其中多项式中不含字母的项叫做常数项。2）多项式的表达我们可以用一些不同的表达方式来表示一个多项式 f(x)=∑i=0i=nai⋅xif(x)=∑i=0i=n...
2018-08-17 08:31:58
335
原创 可持久化AC自动机
其实就是可持久化线段树的模板题 线段树不会看这里#include<bits/stdc++.h>const int N=1000005;using namespace std;int a[N],n,m,q,rt[N*20];int lc[N*20],rc[N*20],val[N*20],cnt;int rd(){ register int f=1,x=0;regi...
2018-08-17 08:30:33
716
2
原创 Luogu P1226 取余运算||快速幂_快速幂
超短代码#include<iostream>#include<cstdio>using namespace std;long long b,p,k;long long Pow(long long n,long long m,long long k){//快速幂啊 if(m==1)return n%k; else {long long r=Po...
2018-08-17 08:28:57
225
原创 Luogu P3740 [HAOI2014] 贴海报 线段树
线段树版的海报实际上这个与普通的线段树相差不大，只是貌似数据太水，暴力都可以过啊本来以为要离散的，结果没打就A了 #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int Max=4000000...
2018-08-16 08:41:49
2631
原创 Luogu P1257 平面上的最接近点对 暴力
这道题数据不大两点距离用勾股定理求#include<iostream>#include<cmath>using namespace std;struct node{ int x,y;}p[100001];int n;double dis(node a,node b){//勾股定理函数 double x=abs(a.x-b.x),y=a...
2018-08-16 08:39:54
2718
原创 键盘自动机
自己研究的自动的打字机效率大概在700字/min吧源码cpp： #include&lt;iostream&gt; #include&lt;cstdio&gt; #include&lt;windows.h&gt; using namespace std; void PutKeyState(char ch){ if(ch==' ...
2018-08-16 08:39:27
2531
原创 BZOJ3991 寻宝游戏 LCA 虚树 SET
5.26 T1:寻宝游戏Description小B最近正在玩一个寻宝游戏，这个游戏的地图中有N个村庄和N-1条道路，并且任何两个村庄之间有且仅有一条路径可达。游戏开始时，玩家可以任意选择一个村庄，瞬间转移到这个村庄，然后可以任意在地图的道路上行走，若走到某个村庄中有宝物，则视为找到该村庄内的宝物，直到找到所有宝物并返回到最初转移到的村庄为止。小B希望评测一下这个游戏的难度，因此他需要知...
2018-08-16 08:38:53
2565
原创 HDU5266 LCA 树链剖分LCA 线段树
HDU5266 LCADescription给一棵 n 个点的树，Q 个询问 [L,R] : 求点 L , 点 L+1 , 点 L+2 …… 点 R 的 LCA.Input多组数据.The following line contains an integers,n(2≤n≤300000).AT The following n−1 line, two integers...
2018-08-16 08:31:50
2673
原创 BZOJ2521 最小生成树 最小割
5.26 T2:最小生成树DescriptionSecsa最近对最小生成树问题特别感兴趣。他已经知道如果要去求出一个n个点、m条边的无向图的最小生成树有一个Krustal算法和另一个Prim的算法。另外，他还知道，某一个图可能有多种不同的最小生成树。例如，下面图 3中所示的都是图 2中的无向图的最小生成树：当然啦，这些都不是今天需要你解决的问题。Secsa想知道对于某一条无向图中的...
2018-08-16 08:26:13
2619
原创 树形结构
树形结构———其实这是很简单又很难得一些东西1 定义树状图是一种数据结构，它是由n(n>=1)n(n>=1)n (n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。 树（tree）是包含n(n>0)n(n>0) n(n>0)个结点的有穷集，其中：1）每个元素称为结点（node）...
2018-08-16 08:24:22
3614
原创 dinic网络最大流
网络流是什么？不急我们慢慢来讲。首先我们先看看最大流1.背景管道网络中每条边的最大通过能力（容量）是有限的，实际流量不超过容量。最大流问题(maximum flow problem)，一种组合最优化问题，就是要讨论如何充分利用装置的能力，使得运输的流量最大，以取得最好的效果。求最大流的标号算法最早由福特和福克逊与与1956年提出，20世纪50年代福特(Ford)、(Fulk...
2018-08-16 08:23:49
2647
原创 莫比乌斯反演
莫比乌斯反演是一个十分玄幻的东西，它可以把o(n2)o(n2)o(n^2)的时间复杂度降到o(nn−−√)o(nn)o(n\sqrt{n})甚至更低1.公式这是莫比乌斯反演最基本的东西，两个定义在正整数集上的函数F(n)F(n)F(n)和f(n)f(n)f(n) 若满足这个式子 F(n)=∑d|nf(d)F(n)=∑d|nf(d)F(n)=\sum_{d|n}f(d) 则会有 ...
2018-08-16 08:22:40
2694
原创 Lucas定
1.lucas定理的作用lucas定理听起来很高级，实际上它只是用来求cmnmodpcnmmodpc_n^m \mod p，其中ppp是一个素数2.lucas定理的表达式Cmnmodp=Cm/pn/p∗CmmodpnmodpmodpCnmmodp=Cn/pm/p∗CnmodpmmodpmodpC_n^m \mod p=C_{n/p}^{m/p}*C_{n\mod p}^{m\mo...
2018-08-16 08:21:36
2579
原创 CF558E A simple task 线段树
这道题好猥琐啊啊啊啊啊啊写了一个上午啊啊啊啊 没有在update里写pushup啊啊啊啊题目大意：给你一个字符串s，有q个操作 l r 1 :把sl..rsl..r按升序排序 l r 0 :把sl..rsl..r按降序排序Solution：我们考虑建26棵线段树，第i棵线段树的[x,y]表示在[x,y]中一共有多少个字母’a’+i-1 至于修改时我们可以以升序...
2018-08-15 19:26:53
2685
原创 树形dp
我也很久没写树d了今天切了4题，也就来写下博客1.树形dp这是一种在树上的dp，它与线性dp不同，与线性dp的顺序是不同的所以其实树形dp就是树上dp是一种在树状结构上进行dp的一种，各个阶段呈现树状关系的时候也可以采用树形dp。2.分类其实这里也有很多类了，树上背包，删点或者删边类树形DP等等3.实现树d的实现其实大多数就是dfs了，对于树的操作也...
2018-08-15 19:26:11
2826
原创 bzoj4518征途 斜率优化
征途这是一道十分经典的斜率优化我们可以从题目中的方差来想,也就很容易的到这个式子 ans=m2∗∑mi=1(xi−x¯¯¯)2mans=m2∗∑i=1m(xi−x¯)2mans=m^2*\frac{\sum_{i=1}^{m}{(x_i-{\overline{x}})^2}}{m}化简就会得到 ans=m∗∑i=1m(xi−x¯¯¯)2ans=m∗∑i=1m(xi−x¯)2ans=m*...
2018-08-15 19:25:38
2882
原创 复习1背包dp
背包问题是对于一个有限制的容器，一般计算可以装的物品的价值最值或数量。通常每个物品都有两个属性空间和价值，有时还有数量或别的限制条件，这个因体而异。背包大概分成3部分，下面会细述这最经典的3种题型1.01背包这是背包中最经典的问题，也是下面两个问题的基础，01背包顾名思义，每种物品要么取，要么不取，也就是1或0。看下例题Luogu P1164 小A点菜题目背景uim...
2018-08-15 19:24:59
3010
原创 复习2二分图匹配
我们现在讲下二分图匹配1.什么是二分图二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)G=(V,E)G=(V,E)是一个无向图，如果顶点VVV可分割为两个互不相交的子集(A,B)(A,B)(A,B)，并且图中的每条边（i，j）（i，j）（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i∈A,j∈B)(i∈A,j∈B)(i\in A,j\in B)，则称图GGG...
2018-08-15 19:24:11
2760
原创 线段树标记永久化
线段树的标记永久化其实线段树的标记永久化是一个非常容易理解的东西，往往我们都会在区间操作时打lazytag，但是在标记下放时会耗费大量的时间，所以我们可以尝试标记永久化，这样我们的就不用下放标记，同时代码也更加简洁，因为我们少了一个pushdown函数，同时出错率也会大大降低。 对于标记永久化，其实和普通线段树比起来，其实差不多#include<iostream>#in...
2018-08-15 19:23:15
3242
原创 高斯消元
高斯消元其实就是一个极其靠意识的东西 我们都学过加减消元，在二元时这里其实是极其容易的，但是拓展到多元，我们就需要一种通解 这个东西我在数学课上都听过，我们在考试时也经常用，现在我们用计算机来做其实就更加简单了 以前我们往往是对于一个元两个不同的系数的两个式子，我们往往讲这个元的系数变为原来两个数的系数的最小公倍数，举个例子 {5a1−2a2=b12a1+3a2=b2{5a1−2a2=b1...
2018-08-15 19:22:32
2771
原创 bzoj1834 网络扩容 网络流
好久没写题解了啊···题目大意：给你一幅n个点的网络，先求出其1到n的最大流，每条弧还会有个属性costicosticost_i，表示没扩容一个单位的费用，现在我们要求的就是扩容K个单位的最小费用思路：这是一道比较裸的网络流，第一问直接dinic就是了，重点就在于第二问。我们把第一问的残量网络继续利用，其中的每条弧的费用都是0，此时我们再在第iii条弧的两端之间在建一条弧，...
2018-08-15 19:21:52
2854
原创 复习3图的全家桶
图论还是来个全家桶吧，其实图论这种东西还是蛮好理解的-1.什么是图图（Graph）是表示物件与物件之间的关系的数学对象，是图论的基本研究对象。一个不带权图中若两点不相邻，邻接矩阵相应位置为0，对带权图(网)，相应位置为∞。有向图与无向图如果给图的每条边规定一个方向，那么得到的图称为有向图。在有向图中，与一个节点相关联的边有出边和入边之分。相反，边没有方向的图称为无向图。...
2018-08-15 19:20:57
2770
原创 bzoj3545 Peaks 线段树合并
离线乱搞。。。 也就是一个线段树合并没什么#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>using namespace std;int n,m,q,tot,cnt,num,h[100001],a[100001],ans[500001]...
2018-08-15 19:19:59
2839
原创 深度优先搜索DFS
深度优先搜索也就是DFS，使我们oi竞赛中使用的最多的算法之一我们今天就来看下这个神奇的算法1.什么是DFS事实上，深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次2.DFS有什么用其实这个DFS往往用来遍历一幅图，在树剖、网络流等算法中会用到。它还...
2018-04-26 13:50:25
2636
原创 斯特林数_数学
斯特林数有两类第一类是：[nk][nk]\left[\begin{array}{c}n\\k\end{array}\right]表示nn不同元素分为kk个非空环排列的方案数。第二类是：{nk}{nk}\left\{\begin{array}{c}n\\k\end{array}\right\}表示nn不同元素分为kk个非空集合的方案数。...
2018-04-21 09:08:11
2687
原创 Luogu P1919 【模板】A*B Problem升级版（FFT快速傅里叶）
这其实就是一道裸的FFT核心思想：把两个数拆成两个多项式用FFT相乘，再反序输出py解法如下：input()print(int(input())*int(input()))皮一下hihifft解法：#include<bits/stdc++.h>using namespace std;const double pi=acos(-1);int n,l,r...
2018-04-20 21:13:58
2826
原创 线段树_数据结构
没错则就是一个（过去的）线段树黑洞的线段树博客线段树：忠诚改实际上这个线段树是十分的简（fu）单（za）的分别有以下几个函数：build:构建整棵线段树pushup:对于我们所要求的答案进行往上更新pushdown:lazy标记下传update:区间修改（可以当做单点修改用）query:区间查询（和，最值等）所以这里每个节点可以维护一个值（如区间最值、和等...
2018-02-21 23:25:57
2917
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人