- 博客(122)
- 收藏
- 关注
RSS订阅原创 原型模式
设计模式（六）——原型模式一、原型模式简介1、原型模式简介原型模式使用原型实例指定创建对象的种类，并且通过拷贝原型对象创建新的对象。Prototype模式提供了一个通过已存在对象进行新对象创建的接口（clone）， clone()实现和具体的语言相关，在C++中通过拷贝构造函数实现。原型模式实际上就是从一个对象再创建另外一个可定制的对象，而且不需要知道任何创建的细节。在初始化的信息不发生变化的情况下，克隆是最好的办法，既隐藏了对象创建的细节，又大大提高了性能。因为如果不用clone，每次new都需
2021-04-27 20:51:31
127
原创 treap详解
Treap详解Treap=Tree+HeapTreap中每个节点有2个值，其中一个满足二叉查找树的性质，一个满足大根堆的性质。把满足二叉查找树性质的值称作data，把满足大根堆性质的值称作value。 对于Treap来说，当前节点的data值大于左儿子，小于右儿子。当前节点的value值小于儿子节点的值。每个节点的data我们无法改变，为了保证Treap的平衡性，我们需要让每个节点的value均为随机值，这样我们就可以保证这棵树“基本平衡”。统计up：计算儿子数void up(int x){
2020-12-03 09:23:01
1126
原创 树链剖分——重链剖分
1.树链剖分的用处对如下问题我们可以采用树链剖分的方法去做1.把某个节点的子树的每个节点都加上一个值z2.查询某个节点的子树的所有节点的值的和求出来3.把一个节点x到y之间最短路径（经过边的条数最少）上的每个节点都加上某个值z4.把一个节点x到y之间最短路径（经过边的条数最少）上的所有节点的和求出来由于我们需要解决这些问题，所以我们要使用树链剖分这种算法。2.实现原理：1.知识储备：重儿子：该节点的所有儿子中，子树中节点个数最多的儿子。举例：节点A有两个儿子，G所形成的树中有6个结点分
2020-11-30 22:17:00
295
原创 树上倍增法求最近公共祖先模板
学习博客#include <bits/stdc++.h>using namespace std;int n,m,s,x,y,tot=0;const int N=100005;//N存储节点总数,M存储边的总数int deep[N],fa[N][22],lg[N];//deep[i]是i号节点的深度//lg是log数组struct node{ int u,v,next;}edge[4*N];int cnt;int head[N];void add(int u,i
2020-11-25 22:55:26
131
原创 获取以2为底log值的两种方法
求log2xlog_2^xlog2x（向下取整)用处：ST表，求最近公共祖先代码;#include<bits/stdc++.h>using namespace std;#define N 100005int Log[N],lg[N];int main(){ int n=10000; //方法一： for(int i=1;i<=n;i++) { Log[i]=Log[i-1]+(1<<Log[i-1]==i)
2020-11-23 23:16:39
6617
原创 12周总结
线段树时间复杂度分析线段树高度：可以看出每次都将区间的长度一分为二,数列长度为n,所以线段树的高度是log(n),这是很多高效操作的基础。建树复杂度：因为每次将区间的长度一分为二,所有创造的节点个数，即底层有n个节点，那么倒数第二次约n/2个节点，倒数第三次约n/4个节点，依次类推：n + 1/2 * n + 1/4 * n + 1/8 * n + ...= (1 + 1/2 + 1/4 + 1/8 + ...) * n= 2n所以构造线段树的时间复杂度和空间复杂度都为O(n)，
2020-11-22 20:39:15
113
1
原创 差分：一维差分，二维差分，树上差分
一维差分差分概念对于一个数列 a_{i}，我们需要维护的数据是“相邻两个数之差”。这种策略是，令pi=ai−ai−1p_i =a_i-a_{i-1}pi=ai−ai−1，即相邻两数的差。我们称数列pip_ipi为数列 a 的差分数列。它可以维护多次对序列的一个区间加上一个数，并在最后询问某一位的数或是多次询问某一位的数。譬如使 [l, r] 每个数加上一个 k，就是 pl=pl+k,pr+1=pr+1−kp_{l}=p_{l}+k, p_{r+1}=p_{r+1}-kpl=pl+k,pr+
2020-11-19 10:41:18
321
原创 11月1日学习总结
一.生成树理解两个最小生成树算法, 都有一个共同的思想: 这棵树是一点一点长大的; 并且每次生长, 都是贪心的.我们可以把一棵树理解成一个有智能的生命, 可以感知它附近的点到它的距离. 每次生长枝条, 它都选择离它最近的那个点.点到树的距离, 是指树外一个点到树上的任意点的最小距离.所以,在代码实现的时候, 需要维护这样一个数组: 树外的点到树的距离. 所以, 还需要区分一下点究竟在树上还在树外.维护数组就是要做两件事: 更改数组和调用数组.何时更改: 树外的点到树的距离发生变化. 这种事只能在树生
2020-11-01 21:19:09
121
原创 2020 10月25日博客总结
一.算法学习本周学习的算法：以下的算法定义和实现代码就不放上了，都另写了博客。1.并查集—disjoin set应用： 1.判断两个元素是否属于同一个连通块。 2.判断图中是否存在一个环2无向图的连通分量 无向图G的最大连通子图称为G的连通分量( Connected Component)。 任何连通图的连通分量只有一个，即是其自身，非连通的无向图有多个连通分量。实现方法：DFS：找出一幅图的所有连通分量可以用深度优先搜索。在深度优先搜索的递归调用期间，只要是某个
2020-10-25 21:50:40
88
原创 拓扑排序模板
#include<iostream>#include<vector>#include<string.h>#include<queue>using namespace std;int n,m;int deg[100];//度 vector<int> G[100];void TPsort(){ queue<int> q; for(int i=1;i<=n;i++) if(!deg[i]) q.push(i);
2020-10-24 21:34:00
81
原创 Team them up! UVA - 1627（动态规划+好题）
题目题目大意：给你n个数字，让你将数字分成两组。是的两组的数字个数尽可能相近。规则如下：每个数字有各自认识的其他数字，每个数字只能和他认识的数字在一组。求分配方式。题目分析：从正面并不是很好下手，不过可以换过一个角度去思考。我们可以考虑如果1,2不认识的话，那么1,2,肯定在不同的组。我们可以把这种关系记录下来。如（1,2），（1,3）（3,4）不能在一组的话，那么只好2,3在一组，1,4在一组。我们可以把不能在一组的两个数字连上边，然后所以不能在一起的关系就会构成一个图。图中所有边都代表边上的两个
2020-10-22 16:36:48
103
原创 线段树区间修改，区间查询模板题
A Simple Problem with Integers线段树区间修改，区间查询模板题#include <cstdio>#include <vector>#include <queue>#include <cstring>#include <cmath>#include <map>#include <set>#include <string>#include <iostream>
2020-10-21 20:08:43
225
原创 求有向图的强连通分量-----tarjan算法
定义：有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通(strongly connected)。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量(strongly connected components)。如何求：伪代码...
2020-10-21 20:06:56
322
原创 求无向图的连通分量
方法一【邻接矩阵DFS】邻接矩阵，DFS解#include<iostream>#include<cstdio>using namespace std;bool f[105][105],a[105]; //f邻接矩阵，a给走过的顶点做标记int m,n,ans;void ooo(int s){ a[s]=1; //标记 for(int i=1;i<=n;i++) { if(!a[i]&&f[s][i]) //当两点连通并且此点没有被访问
2020-10-21 19:59:21
6415
2
原创 并查集及种类并查集
B站并查集int find_root(int x){ if(parent[x]==-1)return x; while(parent[x]!=-1) { x=parent[x]; } return x;}int hebing(int x,int y){ int a=find_root(x); int b=find_root(y); if(a==b)return 1; else {if(deep[a]&
2020-10-20 12:38:18
172
原创 Mayor‘s posters
Mayor’s posters离散化，不然做不了，因为数据太大了#include <cstdio>#include <vector>#include <queue>#include <cstring>#include <cmath>#include <map>#include <set>#include <string>#include <iostream>#include &l
2020-10-18 22:54:14
60
原创 Sliding Window
Sliding Window我一开始用ST表做的，超内存，这是ST表的一个弊端吧？太耗内存ST表#include <cstdio>#include <vector>#include <queue>#include <cstring>#include <cmath>#include <map>#include <set>#include <string>#include <iostrea
2020-10-18 22:53:25
66
原创 ST算法
ST算法应用：多次求区间最大值时间复杂度：询问m次暴力： 总mn线段树：预处理O(logn),查找O(mlogn),总O(logn+m*logn)ST: 预处理O(logn),查找O(m), 总O(logn+m)预处理:const int logN=20;int log[n],f[n][logN+5];//预处理出1~n的log值，因为c++的log函数效率太低;预处理f[n][0]的值;log[0]=-1;for(int i=1;i<=n;i++){
2020-10-18 22:48:53
219
原创 树状数组
树状数组应用：区间求和。时间复杂度：处理O(logn），查找O(logn)拓展：二维树状数组。应用—矩阵求和。注意事项：树状数组的下标是1.……n的数组，因为lowbit(0)=0,会陷入死循环。lowbit(int x){ return x&(-x);}//单点增加void modify(int pos，int data){ for(int i=pos;i<=n;i+=low(x)) { a[i]+=data; }}//区间求和int s
2020-10-18 22:48:05
67
原创 差分约束系统----最短路径算法的应用
差分约束系统是一种特殊的N元一次不等式组，它包含N个变量X1~Xn以及M个约束条件，每个约束条件都是由两个变量做差构成，形如Xi-Xj<=Ck,其中Ck是常数（可以是负数也可以是非负数），1<=i,j<=N,1<=k<=M.我们要解决的问题是求一组解，X1=a1，X2=a2，X3=a3，…，XN=aN，使得所有条件都得以满足。差分约束系统的每一个约束条件Xi-Xj<=Ck可以变形为Xi<=Xj+Ck。这与单源最短路问题中的三角不等式dist[y]<=dis[
2020-10-18 22:39:17
225
原创 SPFA算法的广度优先实现
广度优先搜索+queue实现的spfa算法#include<bits/stdc++.h>using namespace std;#define mod 1e9+7#define N 100#define inf 0x3f3f3f3fconst double PI = atan(1.0)*4.0;typedef long long ll;int visit[N],dis[N],head[N];int m,n;int x,y,z;struct edge{ int u,
2020-10-18 20:36:28
78
原创 迪杰斯特拉算法数组模拟邻接表实现
5 9 ------------------------5是节点数，9是边数1 2 11 3 31 4 51 5 82 3 12 5 53 4 13 5 24 5 41 ------------------------- 根节点1 2 3 4 5 --------------- 输出该点到根节点的最短路径结果0 1 2 3 4#include<bits/stdc++.h>using names
2020-10-18 12:15:37
185
原创 最小生成树
MST（Minimum Spanning Tree，最小生成树）问题有两种通用的解法，Prim算法就是其中之一，它是从点的方面考虑构建一颗MST，大致思想是：设图G顶点集合为U，首先任意选择图G中的一点作为起始点a，将该点加入集合V，再从集合U-V中找到另一点b使得点b到V中任意一点的权值最小，此时将b点也加入集合V；以此类推，现在的集合V={a，b}，再从集合U-V中找到另一点c使得点c到V中任意一点的权值最小，此时将c点加入集合V，直至所有顶点全部被加入V，此时就构建出了一颗MST。因为有N个顶点，所以
2020-10-17 00:30:33
110
原创 DFS序
树状数组应用：区间求和。时间复杂度：处理O(logn），查找O(logn)拓展：二维树状数组。应用—矩阵求和。注意事项：树状数组的下标是1.……n的数组，因为lowbit(0)=0,会陷入死循环。lowbit(int x){ return x&(-x);}//单点增加void modify(int pos，int data){ for(int i=pos;i<=n;i+=low(x)) { a[i]+=data; }}//区间求和int s
2020-10-04 22:34:29
96
原创 DFS剪枝
通过某种判断，避免一些不必要的遍历过程。在编写搜索程序的过程中都要考虑剪枝。剪枝优化的核心问题是设计剪枝的判断方法。5种深度优先搜索的优化技巧：1.优化搜索顺序搜索树中各个层次，各个分支之间的顺序不是固定的2.排除等效冗余在搜索的过程中，如果我们能判定某几条分支到达的子树是等效的，那么只需要对其中的一条分支进行搜索3.可行性剪枝在搜索的过程中对当前的状态进行检查，如发现无法到达递归边界，就执行回溯。4.最优性剪枝在最优化问题的搜素过程中，如果花费已经超过了当前的搜到的最优解，那么无论采
2020-09-27 18:21:50
229
原创 9.20几个贪心问题的总结
1.最优装载问题按区间最右端从小到大排序，如果能放下就直接放，不用考虑“暂时不放这个，从而使后面的能够放下”这种情况。2.区间选点问题还是按最右端从小到大排序，排好序后在每个区间选点时，尽可能的选最后的点，因为这样一个点就可以覆盖尽可能多的区间。如果一个区间要包含多个点，那就按位置从后往前选点。3.区间覆盖问题按照左端点从小到大排序，然后选择与已覆盖区域相接的，右边界最远的区间4.流水作业调度问题（johnson 算法）问题描述：有n个作业要在两台机器A和B上完成，每个作业必须先花时间ai在A
2020-09-20 08:53:05
160
原创 Educational Codeforces Round 93 (Rated for Div. 2)补题
比赛链接题意：问一串数字中有多少子串的长度等于串中所有数字之和思路：不会做，我只能想两重循环，一个数一个数的处理，时间复杂度1010，超时。其实可以不用一个数一个数的处理，只需要用一个map。#include <bits/stdc++.h> using namespace std; int t, n;string s; map<int, int> mp; int main(){ ios::sync_with_stdio(false);
2020-08-15 15:59:16
105
原创 二叉苹果数
思路：首先建树，用一个ma数组，储存输入的数据，用三个数组，l[N],r[N],a[N],完成数的建立，l[i]存储i的左子树顶点，r[i]存储右子树顶点，a[i]存储以i为终点的树枝上的苹果数。建树的过程是两个for循环加递归分别建立左子树右子树。DP函数：因为要保留q个树枝，即要保留q+1个顶点。所以q++。dp[i][j]代表顶点i保留j个顶点所能得到的最大苹果数。用for循环所有情况。三个递归出口：1.当在顶点i保存0个顶点的时候返回0(即砍掉包括i在内的子树）2.当已经循环到树端点的时.
2020-08-14 15:51:07
132
原创 8.13总结
今天把树状数组收了收尾，然后主要学习了数位动态规划，挺难理解的。书上的讲解有限，看不出个所以然。就直接去看实例。今天就看题读程序了。书上给的实例都有点难。因为程序标注很少，真的不好懂，尤其是各种各样的位运算夹在其中，使整个代码很简洁，同时也变得难以理解。只看代码看不明白，只能在纸上模拟过程，从而理解思路。当整个代码理解通顺了之后也就不觉的位运算，DFS什么的难了，只觉得很巧妙。我觉得DP看到现在，觉得要想独立作出这些类型的题目很难，想要吃透很难难。但是起码在脑子里有了这些知识储备，以后如果遇到这些类型的题目
2020-08-13 23:39:16
142
原创 8.6日Codeforces Round #661 (Div. 3)补题
C这个题我做出来了，不过是枚举的总重量的大小，因为数不大嘛，不超过一百，但是我看别人的做法跟我不一样，所以就粘过来了，算是扩展一下思路。题意：一共 t 组测试样例，每组输入一个 n 表示一共有n个人，然后第二行输入n 个数，代表第 i 个人的权重，我们需要对其进行两两配对，每个人只能属于一个队伍，队伍的权重等于两人权重之和，求最多可以组成多少对权重相同的队伍。解题思路：n = 50，排个序 从2 -> 2 * n 双指针即可，注意一下指针在变换的过程中判断一下当前权重和当前枚举的 s 之间的
2020-08-06 23:10:37
135
原创 8.4 算法学习---图论
图的储存结构1.二维数组邻接矩阵存储结构定义int G[N][N]G[i][j]的值，表示从i到j的边的权值注意：初始化数组大可不必使用两重循环1.int数组memset(G,0x7f,sizeof(G))初始化为一个很大的数，memset(G,0,sizeof(G))初始化为0。2.double数组memset(G,127,sizeof(G))初始化为一个很大的数，memset(G,0,sizeof(G))初始化为0。2.二维数组模拟邻接表储存结构#include<iostream&
2020-08-04 21:03:43
251
原创 暑假嗨11
https://vjudge.net/contest/386618#problem/AA题意：给定一串数，问每一个数最右边的小于这个数和这个数之间的距离是多少，如果没有输出-1.我的思路：我是用数状数组来解决的。struct skr{ ll v;int i;}a[N]；1.先按给定的顺序给每个数一个序号idfor(int i=1;i<=n;i++){cin>>a[i].v;a[i].i=i;}2.将这个数组按照v从小到大排序3.从左到右遍历排好序的数组(设当前遍
2020-07-31 22:57:23
80
原创 7月29日
上午的时间，练习线段树模板各种模板的键入。因为我区间修改，区间查询，相关问题还不熟悉，也不能完全脱离模板因此下午的时候，在洛谷上练习了一个线段树的此类模板题。链接：https://www.luogu.com.cn/problem/P2023题目类型：区间修改（区间乘法和加法的组合），区间查询代码反复出错了很多地方，写代码加修改用了一下午的时间，为了更好地记住，在代码中标出出错点，以便日后反思代码：#include<bits/stdc++.h>using namespace std
2020-07-29 23:58:26
114
原创 7月27日树状数组
1.基础知识博客链接2.B站视频讲解3.最形象的树状数组示意图4.树状数组求逆序对及离散化的两种方式树状数组与离散化和求逆序对应该是经常组合起来用吧，今天一共做了俩题，一开始由于不懂离散化和求逆序对，对着别人的题解看了很长时间，勉强看懂，后来去搜了求逆序对和离散化之后，再看题时就很明朗了。5.洛谷1.P1168中位数想了半天，没有思路，最后看的别人的题解。如果要用树状数组的话，首先要离散化处理，不改变原数组的情况下，重新排列。离散化目的：找到每一个数在当前子串下对应的实际相对位置，为后
2020-07-28 00:21:22
66
原创 Codeforces Round #659 (Div. 2)补题A，B1，B2，C，D
A题意：输出n+1个字符串，si和si+1的公共前缀长为ai思路：我们只要模拟过程即可，只要两个字母就可以输出任意多个满足题意的字符串。我们只要改，第一个不相同的就好，后面的都输出一样的，但是一定要确保长度能够达到和下一个字符串相等的长度思路好想，但是写的过程错了很多小细节，暴露代码能力AC代码：#include<bits/stdc++.h>using namespace std;#define mod 1e9+7#define N 100#define inf 0x3f
2020-07-26 20:23:30
169
原创 暑假嗨9
比赛地址A题意：剧院有n种剑，每种都有x把， y 个人来到剧院拿了相同的剑（每个人拿的剑的种类相同），只有1种剑没有被拿过，然后给出每种剑剩余的个数，求最少有多少个人，拿了多少把剑思维因为所有种类的剑初始数量相同，每个人拿且只拿一种剑，且每个人拿的数量相同，就可以想到将剩余的剑排序后，最大的数经过i个人拿之后可以到达其余的任何一个数.所以最大数依次与剩余的数相减得到的所有的数的公约数可以为每个人拿的剑数，为了使人最小，所以要是最大公约数。D题意：先给一张白纸的坐标，再给你两张黑纸的坐标，坐标
2020-07-23 21:34:41
98
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人