- 博客(101)
- 收藏
- 关注
RSS订阅原创 AcWing 859. Kruskal算法求最小生成树
#include<algorithm>#include<iostream>#include<cstring>using namespace std;const int N=2e5+10;int f[N];struct Edge{ int a,b,w; bool operator<(const Edge &W) cons...
2020-02-01 21:40:54
146
原创 AcWing 858. Prim算法求最小生成树
#include<algorithm>#include<iostream>#include<cstring>using namespace std;const int N=510,INF=0x3f3f3f3f;int g[N][N],dist[N];int n,m;bool st[N];int prime()//寻找点并把点加入{ in...
2020-02-01 21:39:03
125
原创 AcWing 854. Floyd求最短路
#include<iostream>#include<cstring>#include<algorithm>using namespace std;const int N=210,INF=1e9;int d[N][N];//i到j的距离int n,m,Q;void floyd()//多源最短路{ for(int k=1;k<=n;k...
2020-02-01 21:35:59
144
原创 AcWing 852. spfa判断负环
#include<algorithm>#include<iostream>#include<cstring>#include<queue>using namespace std;const int N=1e5+10;int h[N],e[N],ne[N],idx,w[N];int dist[N],cnt[N];bool st[N];...
2020-01-31 20:30:52
219
原创 AcWing 851. spfa求最短路
#include<algorithm>#include<iostream>#include<queue>#include<cstring>using namespace std;const int N=1e5+10;int h[N],e[N],ne[N],idx,w[N];int dist[N];bool st[N];int n,m...
2020-01-31 20:27:51
197
原创 AcWing 853. 有边数限制的最短路
Bellman-Ford#include<iostream>#include<algorithm>#include<cstring>#include<string>using namespace std;const int N=510,M=1e4+10;int n,m,k;int dist[N],backup[N];struct E...
2020-01-31 20:24:52
84
原创 AcWing 850. Dijkstra求最短路 II（堆优化）
#include<algorithm>#include<iostream>#include<cstring>#include<queue>using namespace std;const int N=1e5+10;int e[N],ne[N],w[N],h[N],idx;int dist[N];bool st[N];int n,m...
2020-01-31 20:05:22
162
原创 AcWing 849. Dijkstra求最短路I
#include<algorithm>#include<iostream>#include<cstring>using namespace std;const int N=510,INF=0x3f3f3f3f;int n,m;int g[N][N],dist[N];//dist[i]：点1到i的距离bool st[N];//点是否加入了集合int...
2020-01-31 19:59:20
130
原创 AcWing 848. 有向图的拓扑序列
#include<algorithm>#include<iostream>#include<cstring>using namespace std;const int N=1e5+10;int h[N],e[N],ne[N],idx;int q[N],d[N];int n,m;void add(int a,int b){ e[idx]=...
2020-01-30 21:14:01
112
原创 AcWing 847. 图中点的层次
#include<algorithm>#include<iostream>#include<queue>#include<cstring>using namespace std;const int N=1e5+10;int h[N],e[N],ne[N],idx;int n,m;int d[N];queue<int> q...
2020-01-30 21:10:39
103
原创 AcWing 846. 树的重心
#include<algorithm>#include<iostream>#include<cstring>using namespace std;const int N=1e5+10;int h[N],e[N*2],ne[N*2],idx;bool st[N];int n;int ans=N;void add(int a,int b){ ...
2020-01-30 21:08:47
133
原创 AcWing 845. 八数码
#include<algorithm>#include<iostream>#include<string>#include<unordered_map>#include<queue>using namespace std;int bfs(string start)//状态转移好麻烦{ string end="1234...
2020-01-30 20:59:04
110
原创 AcWing 844. 走迷宫
#include<cstring>#include<iostream>using namespace std;const int N=110;int g[N][N],d[N][N];pair<int,int> q[N*N];int n,m;int bfs(){ int hh=0,tt=0; q[0]={0,0};//从左上角开始...
2020-01-30 20:50:32
96
原创 AcWing 837. 连通块中点的数量
#include<algorithm>#include<iostream>using namespace std;const int N=1e5+10;int p[N];int n,m;int sizee[N];//记录数量int find(int x){ if(p[x]!=x) p[x]=find(p[x]); return p[x];}...
2020-01-18 12:22:26
73
原创 AcWing 836. 合并集合
#include<algorithm>#include<iostream>using namespace std;const int N=1e5+10;int p[N];//p[x]代表x的父节点int n,m;int find(int x)//寻找祖先节点{ if(p[x]!=x) p[x]=find(p[x]); return p[x];...
2020-01-18 12:18:54
65
原创 AcWing 143. 最大异或对
#include<iostream>#include<cmath>#include<algorithm>using namespace std;const int N=1e5+10;int son[N*31][2];int idx;void insert(int x){ int p=0; for(int i=30;i>=0;...
2020-01-18 11:42:20
86
原创 Acwing 835 Trie字符串统计
#include<algorithm>#include<iostream>#include<string>using namespace std;const int N=1e5+10;int son[N][26],cnt[N];int idx;char str[N];void insert(){ int p=0;//根节点 fo...
2020-01-18 11:39:31
119
原创 Acwing 831KMP字符串
#include<algorithm>#include<iostream>using namespace std;const int N=1e4+10,M=1e5+10;char p[N],s[M];int ne[N];int main(){ int n,m; cin>>n>>p+1>>m>>s+...
2020-01-18 11:32:18
154
原创 Acwing 831滑动窗口
#include<algorithm>#include<cstdio>using namespace std;const int N=1e5+10;int a[N],q[N];int main(){ int n,k; scanf("%d %d",&n,&k); int tt=-1,hh=0; for(int i=0...
2020-01-16 21:06:10
130
原创 Acwing 830 单调栈
在放入x之前，栈中所有比x大的数都不会存在于队列中。#include<algorithm>#include<iostream>using namespace std;const int N=1e5+10;int stk[N],tt=0;int main(){ int n; cin>>n; for(int i=0;i<...
2020-01-16 20:48:49
100
原创 Acwing 829 模拟队列
队列，先进先出。hh代表头，tt代表尾#include<iostream>using namespace std;const int N=1e5+10;int q[N],tt,hh;void init(){ tt=-1; hh=0;}void push(int x){ q[++tt]=x;}void pop(){ hh++;...
2020-01-16 19:23:21
101
原创 Acwing 828模拟栈
以tt作为指针先进后出#include<algorithm>#include<iostream>using namespace std;const int N=1e5+10;int stk[N],tt;void init(){ tt=0;}void push(int x){ stk[++tt]=x;}int pop(){ ...
2020-01-16 17:32:40
87
原创 Acwing 827 双链表
开始把0设为head，1设为tail，所以编号为k的节点为第k+1个插入的数；#include<algorithm>#include<iostream>#include<string>using namespace std;const int N=1e5+10;int l[N],r[N],idx,e[N];//l，r分别为左右指针void ini...
2020-01-16 17:14:52
171
原创 Acwing 826单链表
把head，en[N]看成指针感觉会舒服很多。#include<algorithm>#include<iostream>using namespace std;const int N=1e5+10;int head,idx,e[N],ne[N];void init()//初始化，head一开始指向-1{ idx=0; head=-1;}v...
2020-01-16 16:51:50
88
原创 AcWing 803. 区间合并
利用贪心的思想，对节目开始时间从大到小排序#include<iostream>#include<algorithm>#include<vector>using namespace std;typedef pair<int,int> PII;vector<PII> segs;void merge(vector<PII&g...
2020-01-15 11:06:34
99
原创 AcWing 802. 区间和
用离散化的思想来做#include<algorithm>#include<iostream>#include<vector>using namespace std;typedef pair<int,int> PII;const int N=3e5+10;int a[N],s[N];int n,m;vector<int> ...
2020-01-15 10:48:43
80
原创 AcWing 801. 二进制中1的个数
#include<algorithm>#include<iostream>using namespace std;int lowbit(int x){ return x&(-x);原码和反码 相与}int main(){ int n; cin>>n; for(int i=0;i<n;i++) {...
2020-01-15 10:41:33
136
原创 洛谷P1255数楼梯
走第一个台阶一种走法（走一步），走两个台阶两种走法（走一步，走两步），走上第三个台阶可以看成走上第一个台阶的方法+走上第二个台阶的方法。因为n太大，所以要用高精度来做。f[k][i],k表示走上第几个台阶，i表示高精度加法的位数。#include<algorithm>#include<iostream>using namespace std;const int ...
2020-01-12 20:33:43
301
原创 洛谷P1303高精度乘法
#include<algorithm>#include<iostream>#include<string>#include<cstring>#include<vector>using namespace std;const int N=5e5+10;int A[N],B[N],C[N];int mul(int sizeA,...
2020-01-12 20:26:43
163
原创 Acwing800数组元素的目标和
A，B数组为递增的，所以可将j从B的结尾开始，这样子不用每次把j放到开头再来一遍。#include<iostream>#include<algorithm>using namespace std;const int N=1e5+10;int A[N],B[N];int main(){ int n,m,x; cin>>n>&g...
2020-01-12 20:20:12
110
原创 Acwing799 最长连续不重复子序列
利用s[]来判断是否重复#include<cstdio>#include<algorithm>using namespace std;const int N=1e5+10;int a[N],s[N];int main(){ int n; scanf("%d",&n); for(int i=0;i<n;i++) s...
2020-01-12 20:18:19
139
原创 ACwing798差分矩阵
对（x1,y1）至（x2,y2）中数+c，也可用差分来做。类似于子矩阵的和的那种加减方法。#include<cstdio>using namespace std;const int N=1010;int a[N][N],b[N][N];void insert(int x1,int y1,int x2,int y2,int c){ b[x1][y1]+=c; ...
2020-01-12 20:15:39
108
原创 Acwing797差分
要对a[l,r]中的每个数进行加减c的操作，直接进行的话为al+c，al+1+c……ar+c,若进行差分的话，则只需要对bl+c，br+1-c即可。#include<cstdio>#include<algorithm>const int N=1e5+10;int b[N],a[N];void insert(int l,int r,int c){ b[l]...
2020-01-12 20:08:49
131
原创 Acwing 子矩阵的和
#include<cstdio>using namespace std;const int N=1010;int a[N][N],s[N][N];int main(){ int n,m,q; scanf("%d %d %d",&n,&m,&q); for(int i=1;i<=n;i++) for(int ...
2020-01-11 20:00:44
155
原创 Acwing 前缀和
#include<iostream>#include<cstdio>using namespace std;const int N=1e5+10;int a[N],s[N];int main(){ int n,m; scanf("%d %d",&n,&m); for(int i=1;i<=n;i++) sca...
2020-01-11 20:00:13
116
原创 Acwing 高精度除法
#include<iostream>#include<algorithm>#include<vector>#include<string>using namespace std;vector<int> div(vector<int> &A,int &b,int &r){ vector...
2020-01-11 19:59:43
223
原创 Acwing 高精度乘法
#include<algorithm>#include<iostream>#include<string>#include<vector>using namespace std;vector<int> mul(vector<int> &A,int b){ vector<int> C; ...
2020-01-11 19:58:02
104
原创 Acwing高精度减法
#include<algorithm>#include<iostream>#include<vector>#include<string>using namespace std;bool cmp(vector<int> &A,vector<int> &B)//判断A大还是B大{ if(A.s...
2020-01-11 19:55:33
110
原创 Acwing高精度加法
#include<algorithm>#include<iostream>#include<vector>#include<string>using namespace std;vector<int> add(vector<int> A,vector<int> B){vector<int>...
2020-01-11 19:53:28
256
原创 Acwing 790数的三次方根
二分#include<cstdio>#include<algorithm>#include<iostream>using namespace std;int main(){ double n; cin>>n; double l=-10000,r=10000; while(r-l>1e-8)//控制范围 { dou...
2020-01-10 22:38:43
118
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人