Anonytt-CSDN博客

原创【图论】最短路算法小总结

SPFA算法链接：模板：https://blog.csdn.net/Rainfoo/article/details/104459643判环(是否成环/负环)：https://blog.csdn.net/Rainfoo/article/details/104481164Floyd算法链接:模板：https://blog.csdn.net/Rainfoo/article/details/10...

2020-02-24 17:27:33 191

原创 Markdown latex语法合集

极限：lim⁡x→∞1n(n+1)\lim\limits_{x\rightarrow\infty}\frac{1}{n(n+1)}x→∞limn(n+1)1积分：∫01x2 dx\int_0^1 {x^2} \,{\rm d}x∫01x2dx

2021-12-29 15:09:07 453

前置知识点(1) pi = acos(-1);(2) 余弦定理 c^2 = a^2 + b^2 - 2abcos(t)浮点数的比较const double eps = 1e-8;int sign(double x) // 符号函数{if (fabs(x) < eps) return 0;if (x < 0) return -1;return 1;}int cmp(double x, double y) // 比较函数{if (fabs(x - y) <..

2021-02-10 20:28:44 280

原创【主席树】区间查询第k大

洛谷P3834：#include<bits/stdc++.h>#pragma GCC optimize(2)#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define eps 0.000000001#define pb push_back#define mem(a,b) mems

2021-02-09 14:33:25 228

原创 01字典树模板

const int maxn=1e5+5;struct Trie{ int val[maxn*31],tree[maxn*31][2],L,root; int newnode(){ mem(tree[L],-1); return L++; } void init(){ L=0; root=newnode(); } void update(int x,int key){ int now=root; for(int i=31;i>=0;i--){ int p=(

2021-02-02 12:21:01 115

原创矩阵快速幂模板

const ll mod = 1e9 + 7;const int N = _____;//输入矩阵大小Nstruct Mat{ ll m[N+1][N+1];};Mat a,e;Mat Mul(Mat x,Mat y){ Mat ans; for(int i=1;i<=N;++i){ for(int j=1;j<=N;++j){ ans.m[i][j]=0; for(int k=1;k<=N;

2021-01-30 21:50:19 78

原创【动态规划】LIS O(nlogn)

#include<bits/stdc++.h>#pragma GCC optimize(2)#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define eps 0.000000001#define pb push_back#define mem(a,b) memset(a,b,si

2020-10-13 12:58:20 207

原创【数据结构】单调栈/单调队列

单调栈#include<bits/stdc++.h>#pragma GCC optimize(2)#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define eps 0.000000001#define pb push_back#define mem(a,b) memset(a,

2020-10-04 14:38:09 101

原创【图论】A*搜索(第k短路)

POJ2449#include<bits/stdc++.h>#pragma GCC optimize(2)#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define eps 0.000000001#define pb push_back#define mem(a,b) memse

2020-09-17 20:42:54 125

原创【图论】网络流一些模板

AcWing.2188 无源汇上下界可行流#include<bits/stdc++.h>#pragma GCC optimize(2)#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define eps 0.000000001#define pb push_back#define

2020-08-29 16:22:12 206 2

原创【字符串】AC自动机

模板洛谷P3808：#include<bits/stdc++.h>#pragma GCC optimize(2)#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define eps 0.000000001#define pb push_back#define mem(a,b) me

2020-08-02 22:07:06 165

原创【字符串】关于循环字符串字典序最大最小位置表示法

hdu3374题意：给出一个字符串，依次左移一个单位形成一堆字符串，求其字典序最小和最大的字符串需要左移多少位，以及一共有几个这样的字符串。题目分析：首先可以确定两个字符串出现的次数应该相同。由于假设最小的左移m位得到最大的话，那么所有相同的最小字符串左移m位都会得到最大串。对于求解最小最大串的位置可以用最小最大表示法。最大最小表示法：总的来说就是这道题的模板，求一个循环串字典序的最小和最大的位置。算法整体思想很简单，以最小为例如题，指针i，j分别代表比较的两个串的串首位置，这两个位置是互相更新的。当

2020-07-30 17:39:22 510

原创【数据结构】带权并查集

hdu3038模板#include<bits/stdc++.h>#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define eps 0.000000001#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))#defi

2020-07-30 10:20:01 143

原创【字符串】扩展KMP

板子：HDU2594#include<iostream>#include<cstring>#include<algorithm>#include<vector>#include<cmath>#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n

2020-07-28 21:48:52 92

原创【图论】最短路中(最短距离计数+最短距离最大顶点费用)

问题一：最短距离计数例题:(洛谷P1608) https://www.luogu.com.cn/problem/P1608坑点：去重边#include<bits/stdc++.h>#define ll long long#define white 0#define black 1#define grey 2#define endl '\n'#define INF 0x3f3f3f3f3f#define IO ios::sync_with_stdio(false);ci

2020-07-19 10:43:02 154

原创【图论】差分约束

洛谷P5960:https://www.luogu.com.cn/problem/P5960#include<bits/stdc++.h>#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define eps 0.000000001#define pb push_back#define

2020-07-16 09:57:31 222

原创【图论】边/点双联通分量

边双连通分量:hihocoder1184#include<bits/stdc++.h>#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define eps 0.000000001#define pb push_back#define mem(a,b) memset(a,b,sizeo

2020-07-14 15:51:49 370

原创【图论】2-SAT

模板：洛谷P4782#include<bits/stdc++.h>#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define eps 0.000000001#define pb push_back#define mem(a,b) memset(a,b,sizeof(a))#def

2020-07-13 10:21:05 174 1

原创【图论】树上启发式合并

树上启发式合并(DSU on Tree)，是一个在O(nlogn) 时间内解决许多树上问题的有力算法。cf600E板子#include<bits/stdc++.h>#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define mem(a,b) memset(a,b,sizeof(a))

2020-06-07 19:23:35 273

原创【数论】线性求逆元

ine[1]=1; for(int i=2;i<mod;i++){ int a=mod/i,b=mod%i; ine[i]=(ine[b]*(-a)%mod+mod)%mod; }

2020-06-06 20:23:52 137

原创【图论】点分治

洛谷P3806#include<bits/stdc++.h>#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define mem(a,b) memset(a,b,sizeof(a))#define IO ios::sync_with_stdio(false);cin.tie(0);u

2020-06-04 20:05:45 167

原创【图论|数据结构】树链剖分(重链)

时间复杂度：重链剖分O(logn)线段树O(logn)m次询问总：O(m*log(n)*log(n))板子：#include<bits/stdc++.h>#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define mem(a,b) memset(a,b,sizeof(a)).

2020-05-30 17:10:41 316

原创【图论】Floyd求最小环

CF1205B:#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<cmath>#include<vector>#define ll long long#define inf 1e8+10using na...

2020-05-06 12:37:26 284 1

原创图论中的记忆化搜索问题

今天做了一道题，codeforces283B，感觉收获蛮多的，第一次接触了记忆化搜索，对于dfs的认知更进了一层吧抛砖引玉:给你一个n，表示从1~n个数，输入x(x<=n)，问x+(x+1)…+n的和，即后缀和，傻子都知道怎么做，最简单的莫过于高斯公式了，但是我们需要从简单问题抽象出更深层次的东西—记忆化搜索#include<bits/stdc++.h>#define m...

2020-04-29 16:54:39 206

原创【语法小技巧】重载运算符

以cf1063B为例#include<bits/stdc++.h>#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define mem(a) memset(a,0,sizeof...

2020-04-25 15:37:41 185

原创 codeforces698B 【合并树+拆环】

https://codeforces.com/contest/698/problem/B题解：好题！感觉这是cf 1700里面graph中比较有价值的一道题。题意差不多就是把图转成树需要最少几步。第一次接触拆环这个东西还是挺有感触的吧。大体思路就是：不断通过当前点访问其父亲结点，看其父亲结点是不是顶点或者已经被访问。如果父亲节点x已经被访问说明该链是x的一条子链，这在树里面是允许的。判断...

2020-04-20 17:04:54 226

原创【数据结构】dfs序建简单线段树

例题：https://ac.nowcoder.com/acm/contest/5158/I解答：这个题很棒！该题求和是把该点所有孩子以及本身加起来求和，所以我们可以动用dfs序，确定L[x]和R[x]的位置。L就是dfs遍历当前时候的时间戳，R是回溯回当前位置的时间戳。而一开始只给你各个节点序号及其对应的值，怎么确定你dfs时间戳呢？他给了你一个起点k，通过跑dfs遍历就能得到。id[df...

2020-04-19 21:55:42 394

原创【图论】最大流算法(FF,EK,dinic)

模板题：洛谷P3376算法二：FF算法(dfs为主)#include<bits/stdc++.h>#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define mem(a) ...

2020-04-14 22:40:28 477

原创【图论】二分图多重匹配の探讨

这几个题是我觉得比较好的入门二分多重匹配的题。什么是二分多重匹配？简单的来说，就是一个对于左边(或者右边)的点集，每个点都要有单独输出的完备匹配，但是其对应的另一侧点集，每个点可以有多个输入(有些点甚至可能没有输入也有可能)，简单的来说就是：目标方可以有多个输入吧，输出方每个只能单个输出，保障每个输出方点均有输出。既然是要多重，那么我们就会有一定的约束条件。比如POJ2289：意思就是每个...

2020-04-10 19:56:58 612

原创【图论】二分图判断&一些常识

(1)二分图的最大匹配匈牙利算法(2)二分图的最小点覆盖二分图的最小点覆盖=二分图的最大匹配求最小点覆盖：从右边所有没有匹配过的点出发，按照增广路的“交替出现”的要求DFS。最终右边没有访问过的点和左边访问过的点组成最小点覆盖。(3)二分图的最少边覆盖二分图的最少边覆盖=点数-二分图的最大匹配证明：先贪心选一组最大匹配的边放进集合，对于剩下的没有匹配的点，随便选一条与之关联的边放进...

2020-04-08 14:51:31 399

原创【图论】二分图匹配(Hungary算法&KM算法&hopcroft-karp算法)

O(n^3)的板子：#include<bits/stdc++.h>#define ll long long#define endl '\n'#define mem(a) memset(a,0,sizeof(a))#define IO ios::sync_with_stdio(false);cin.tie(0);using namespace std;const int I...

2020-04-06 20:38:37 534

原创【图论】求树的直径(最长链)

方法有很多，我这里用2种dfs的做法来做方法：先从任意一点P出发，找离它最远的点Q，再从点Q出发，找离它最远的点W，W到Q的距离就是是的直径#include<iostream>#include<cmath>#include<algorithm>#include<cstring>#include<stack>using nam...

2020-04-03 13:03:52 464

原创【图论】"欧拉回路"の训练报告+总结

首先先给各位看官分享一下题单，接下来的博客将围绕题单顺序展开：这里就不具体介绍什么是"欧拉回路”了吧：在我看来，欧拉回路首先分2大类：有向的或者无向的；具体问题具体分析。板块一：欧拉图的判断：无向欧拉图：1.先用并查集合并所有组，如果并查集组数位1，那么ok2.再看每个点的度数，因为是无向图，就不细分Indeg和outdeg了，统一用degree表示，那么会存在2种情况：即所有的点...

2020-03-25 16:54:26 323

原创【2020春数据结构】线性表

#include<bits/stdc++.h>#define ll long long#define endl '\n'#define IO ios::sync_with_stdio(false);cin.tie(0);using namespace std;const int maxn=1e3+5;int a[maxn];typedef struct{ int dat...

2020-03-15 21:00:24 141

原创【字符串】序列自动机

#include<bits/stdc++.h>#define ll long long#define rep(i,a,n) for(int i=a;i<=n;i++)#define per(i,n,a) for(int i=n;i>=a;i--)#define endl '\n'#define mem(a) memset(a,0,sizeof(a))#defin...

2020-03-14 17:08:24 146

原创【图论】欧拉回路

先上一个板子吧，单向的#include<bits/stdc++.h>#define ll long long#define endl '\n'using namespace std;const int INF=0x3f3f3f3f;const int mod=1e9+7;const int maxn=1e3+10;int tot,n,m,cnt;int head[ma...

2020-03-06 16:16:51 227

原创【图论】朱刘算法路径输出

codeforces240E：感谢博主https://www.cnblogs.com/zsben991126/p/9809730.html#include<iostream>#include<cstring>#include<cstdio>#include<algorithm>#include<vector>#define ...

2020-03-05 13:09:05 475

原创【图论】次小生成树

#include<bits/stdc++.h>#define ll int#define endl '\n'#define mem(a) memset(a,0,sizeof(a))#define IO ios::sync_with_stdio(false);cin.tie(0);using namespace std;const int INF=0x3f3f3f3f;co...

2020-03-01 22:15:26 116

原创【图论】朱刘算法求最小树形图

以洛谷P4716为例#include<bits/stdc++.h>#define ll long long#define IO ios::sync_with_stdio(false);cin.tie(0);using namespace std;const int M=1e6+5;const int N=1e6+5;const int inf=2e9;struct Ed...

2020-02-28 20:59:32 233

空空如也

空空如也