- 博客(28)
- 收藏
- 关注
RSS订阅原创 基本数据结构汇总
栈元素先进后出 栈顶进栈顶出一般用数组或链表来实现插入删除时间复杂度O(1) 空间复杂度O（n）单调栈 乱发节 从前向后扫，维护一个自底向上单调递减的单调栈。每扫到一个数，就把栈顶所有小于这个数的元素弹出栈，把这个元素加入栈。进出栈序列问题递归 O(2^n)枚举每一步进栈还是出栈递推 O(n*n)考虑1在出栈序列中的位置，如果1排在第k个，问题就被划分为"k-1...
2018-08-16 00:14:12
201
原创 位运算
基础知识1.与&两位全为1，结果才为1，否则为0特殊用法： （1）清零。如果想将一个单元清零，即使其全部二进制位为0，只要与一个各位都为零的数值相与，结果为零。 （2）取一个数中指定位 例：设X =10101110,取X的低4位，用X&00001111 = 0000 1110 即可得到2.或 |只要有一个为1，结果就为1特殊用法： ...
2018-07-23 22:00:09
162
原创 Noip2013 货车运输
思路 观察题目，经过思考，发现两个点之间最小值最大的路径一定在最大生成树上。 所以我们可以先用kruskal算法求出最大生成树。 之后问题转化为链上最小值。 首先我们可以以1为根建树，之后用倍增算法。dadi,j表示i的2j的父亲，maxi,j表示i到他的2j的父亲路径上所有边的最小权值。 这样我们在求lca的同时可以求出链上最小值。 时间复杂度O(mlogm)，空间复杂度O(...
2018-07-21 09:57:52
211
原创 贪心
贪心是一种在每次决策时采取当前意义下最优策略的算法，因此要求整体最优性可以由局部最优性导出。正确性证明的常见手段： 1.微扰（邻项互换） 证明在任意局面下，任何对局部最优策略的改变都会使结果变差 2.范围缩放 ...
2018-07-11 16:18:00
188
原创 分治
整数集合上的二分流程 1.确定左右半段哪个是可行区间，以及mid归属于哪一半段 2.根据分析结果选择两个配套形式之一（只适用于非负数） ①r=mid,l=mid+1,mid=(l+r)/2 ②l=mid,r=mid-1,mid=(l+r+1)/2当二分区间包含负数时，需要使用更加一般的计算方法“
2018-07-11 13:01:32
242
原创 最小生成树-Prim算法
Prim算法总是维护最小生成树的一部分。最初，Prim算法近仅确定1号节点属于最小生成树。在任意时刻，设已经确定属于最小生成树的节点集合为T，剩余节点集合为S。...
2018-07-09 19:46:00
210
原创 最小生成树-Kruskal算法
定理：任何一棵最小生成树一定包含无向图中权值最小的边（反证法）算法思路Kruskal算法基于上述定理，总是维护无向图的最小生成森林。最初，可认为生成森林由0条边构成，每个节点各自为树。在任意时刻，从剩余边中选出一条权值最小的，并且两个端点不连通（属于两棵不同的树），把该边加入生成森林。节点的连通情况用并查集维护。算法流程1.建立并查集，每个点各自为一个集合2.把所有边按权值升序排列，依次扫描每条边...
2018-07-06 19:26:13
149
原创 Floyed算法-求任意两点间最短路
本质是动态规划，O(n^3)算法思路设D[k,i,j]表示“经过若干个编号不超过k的节点”从i到j的最短路该问题可划分为两个子问题：1.经过编号不超过k-1的节点从i到j 2.从i先到k再到jD[k,i,j]=min(D[k-1,i,j],D[k-1,i,k]+D[k-1,k,j])初值为D[0,i,j]=A[i,j] //开头定义的邻接矩阵k这一维可以被忽略Tipsk是阶段，必须置于最外层循...
2018-07-04 15:22:20
1112
原创 Bellman-Ford和SPFA算法
定义 给定一张有向图，若对于某一条边（x,y,z），有dist[y]<=dist[x]+z成立，则称该边满足三角形不等式。若所有边均满足三角形不等式，则dist数组就是所求的最短路。基于迭代思想的Bellman-Ford算法1.扫描所有边（x,y,z），若有dist[y]>dist[x]+z，则更新dist[y]2.重复上述步骤直到没有更新操作发生SPFA算法（队列优化的Bell...
2018-07-04 12:06:18
270
原创 堆优化的dijkstra算法
基于贪心思想，只适用于边长为非负数的图算法流程1.初始化的dist[1]=0，其余节点的dist为正无穷2.找出一个未被标记、dist[x]最小的节点x并标记3.扫描x的所有出边（x,y,z），若dist[y]>dist[x]+z，则更新dist[y]4.重复2、3，直到所有节点被标记//by ziwan Catherine//堆优化dijkstra 边长为非负数 //d[n]从起点到n...
2018-07-04 11:21:25
2379
原创 基本深搜模板
一个基本的深搜模板int search(int t){ if(满足输出条件) { 输出解; } else { for(int i=1;i<=尝试方法数;i++) if(满足进一步搜索条件) { 为进一步搜索所需要的状态打上标记; ...
2018-06-20 11:25:44
1047
原创 拓展欧几里得算法
概述【背景：欧几里得算法即辗转相除法 求gcd（a,b）】对于不完全为 0 的非负整数 a，b，gcd（a，b）表示 a，b 的最大公约数，必然存在整数对 x，y ，使得 gcd（a，b）=ax+by。递归式推导递归终点在欧几里得算法求gcd时，递归终点是b=0此时ax=gcd(a,0) 所以x=1，即为递归终点代码实现通解与特解 若（x0，y0）是不定整数方程ax+by=c的一组解...
2018-05-30 01:31:09
141
原创 区间dp zrtT1涂色
#include <cstring>#include <iostream>#include <algorithm>using namespace std;char in[105],len;int dp[105][105];int main(){ cin>>in; len=strlen(in); for(int i...
2018-05-09 17:59:26
132
原创 5.3信心杯T1 Divisibility
题解(by 石二lyh orz) 一组数两两之差可以整除m，当且仅当它们在模m的剩余系意义下相等。对于每个数a[i]，将其加入a[i]%m的代表集合中，判断0~m-1是否有一个集合的个数大于等于k即可。输出字典序最小的方案时，只需要比较所有满足题意的集合中的最小值，最小值最小的集合即为答案，排序输出前k个即可。 时间复杂度o(n+klogk)代码 //by ziwan#inc...
2018-05-04 00:56:58
90
原创 深度优先搜索—luogu1040加分二叉树
#include<iostream>#include<cstdio>using namespace std;int n;int a[35],dp[35][35],rt[35][35];int dfs(int l,int r){ if(dp[l][r])return dp[l][r]; if(l>r)return 1; if(l==r)...
2018-05-03 00:41:44
109
原创 深度优先搜索-luogu1019单词接龙
#include<bits/stdc++.h>#define LL long long#define reg register int#define f(i,a,b) for(reg i=a;i<=b;i++)using namespace std;int n;int ans,mx;string s[25];char g;int vis[50];void df...
2018-05-02 22:53:21
166
原创 高斯消元法
double a[i][i];const double eps =1e-5;//1*10^-5void gauss(int n){ for(int i=1;i<=n;i++)//枚举方程 { int k=-1; for(int j=1;j<=n&&k==-1;j++) if(fabs(a[i][j])...
2018-05-02 22:42:36
121
原创 区间dp-luogu3205[HNOI2010]CHORUS 合唱队
区间dp介绍 区间dp属于线性dp的一种，它以区间长度作为dp的stage，使用区间左、右端点来描述每个维度。在区间dp中，一个状态由若干个比它更小切且包含于它的区间所代表的状态转移而来，因此区间dp的决策往往是划分区间的方法。实现 初态一般由长度为1的“元区间”构成，枚举时先枚举阶段长度，再枚举左端点下标，由此计算右端点下标。例题（luogu3205[HN...
2018-05-01 15:21:12
178
原创 树形dp-luogu1352 没有上司的舞会
树形dp实现 动态规划在树形结构上的实现：任选一个点作为根节点，从而定义出每个节点的深度和每个子树的根。设计算法时，一般以节点由深到浅（子树由小到大）的顺序作为dp阶段，通常采用递归实现。状态表示 第一维通常是节点编号（代表以该节点为根的子树）。对于每个节点x，先递归在它的每个子节点上进行dp，在回溯时，从子节点向x进行状态转移。例题（luogu1352）思路 ...
2018-04-30 23:50:36
226
原创 线段树模板
模板#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#define size using namespace std;struct tree{ int l,r; int mx,sum;}t[size*4];void bu...
2018-04-06 09:48:36
177
1
原创 完全背包
完全背包问题题目有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]，每件物品可以使用无限次。求解将哪些物品装入背包可使价值总和最大。基本思路这个问题非常类似于01背包，所不同的是每种物品有无限件，也就是从每种物品的角度考虑，与它相关的策略已并非取或不取两种，而是有取0件、取1件、取2件……取[V/c]件等很多种。如果仍然按照解01背包时的思路，令f[v]表示前i种物品恰放入...
2018-03-27 00:34:12
84
原创 01背包变式 luogu1064金明的预算方案
虽然还是01背包吧，但是这道题思路相对麻烦一些，所以单独用一篇博客来记录好了题面如下数据预处理用ad[i][j]数组来记录附件 表示第i个物品的第j个附件这样可以直接查找附件用bl[i]数组来标记第i个物品是附件还是主件 附件为1在dp的时候就可以把附件直接跳过思路框架因为情况复杂所以选用倒序循环一维的01背包模板接下来讨论每个主件中有哪些选择 分类列出状态转移方程截图来自题解【懒得打出来了emm...
2018-03-23 02:37:33
220
原创 01背包问题
今天是决定要好好学oi的第一天，虽然还是因为各种各样的原因耽搁了一会，但任务还是完成啦~01背包问题题目有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。用子问题定义状态：即f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方...
2018-03-21 01:40:00
215
原创 邻接表 链式前向星
//链式前向星 #include#includeusing namespace std;int cnt,last[10],a[10],n;struct edge{int to,next;//每个结点存一条边，next表示下一条边，to表示这条边的终点}edge[505];void add(int bg,int ed){cnt++; edge[cnt].t
2017-12-09 11:46:29
195
原创 快速幂算法
#include<iostream>using namespace std;int pw(int a,int b){ int res=1; while(b) { if(b%2==1) res*=a; a*=a; b/=2; } return res;}int main()...
2017-12-09 11:40:04
170
原创 堆排 luogu1090合并果子
此题为堆排的简单运用#include<cstdio>#include<iostream>using namespace std;int ans,s,hp[10005],n,siz,cnt;void pus(int x)//输（插）入 {cnt++;hp[cnt]=x;int now=cnt;int fa=cnt/2;while(now>1){if(hp[now]>...
2017-12-09 11:37:26
193
原创 小根堆的插入和排序
#include<cstdio>#include<iostream>using namespace std;int hp[105],n,siz;void push(int x)//输（插）入 { if(hp[x]>=hp[x/2]) return; else { int a=hp[x]; hp[x]=hp[x/2]; hp[x/2]=...
2017-12-09 11:33:47
1100
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人