- 博客(39)
- 资源 (1)
- 收藏
- 关注
RSS订阅原创 线性基入门
线性基参考资料参考资料2模板来源概述线性基是一种擅长处理异或问题的数据结构.设值域为[1,NNN]，就可以用一个长度为⌈log2N⌉\lceil \log_2N \rceil⌈log2N⌉的数组来描述一个线性基。特别地，线性基第iii位上的数二进制下最高位也为第iii位。性质原序列里面的任意一个数都可以由线性基里面的一些数异或得到(也能异或得到一些不存在于集合的数)线性基...
2019-09-16 21:20:56
235
原创 SPFA
SPFA简介SPFA算法是一种求单源最短路的算法，其BFS写法是基于Ford的队列优化。但是尤其其经常被卡，所以一般不用于正权图，而是用于负权图来求最短路或者判断负环。算法思想主要思路是动态逼近法，也就是不断优化，直到无法优化路径。我们设置一个队列，用于存储待优化的节点。每次将队首节点出队，然后用其松弛邻接的结点，如果能松弛，则将可松弛的节点的距离更新，然后将可松弛节点加入队列。循...
2019-08-07 01:53:35
746
原创 日期计算
日期计算介绍日期计算问题就是给出一个合法日期，计算此日期是星期几。这个涉及到一些历法和数学的知识，但是有很好用的公式可以使用。蔡勒公式1582年10月4日之后：w=y1+(y1/4)+(c/4)-2*c+(26*(m+1)/10)+d-1;1582年10月4日以及之前：w=y1+y/4+c/4-2*c+13*(m+1)/5+d+2;输出：(w%7+7)%7 （为了确保结果为正数...
2019-08-06 21:07:43
399
原创 N数码问题
N数码问题简介我们先引入一个简单的问题.首先，这里的拼图游戏是滑块拼图，类似于华容道，游戏者通过移动拼图块将拼图还原为初始形状。关于拼图，常见的有3x3，4x4，多的以至于有16x16不等。一般块数越多拼图越复杂。如图所示,我们可以用空格与其上下左右相邻的位置的方块进行交换.给你两个局面,问这两个局面能不能互相转化.分析这个就是著名的N数码问题,我们为了严谨,在之后的讨论中都是N...
2019-07-31 22:40:39
1795
原创 Trie 树
Trie 树参考资料介绍Trie树是一种高级数据结构,用于解决多模式串匹配问题(KMP算法是用以解决单模式串匹配),其主要思想是利用树形结构,(树上除根节点外,每一个节点都对应着一个字符),使得前缀相同的单词共用前缀部分的节点.加快匹配速度.模板// 个人倾向于使用数组形式的字典树,动态节点类型不好debug//对于字符串比较多的要统计个数的，map被卡的情况下，直接用字典树//很...
2019-07-31 20:28:18
115
原创 ST表&LCA&RMQ
SparseTableRMQ问题RMQ (Range Minimum/Maximum Query)问题是指：对于长度为n的数列A，回答若干询问RMQ(A,i,j)(i,j<=n)，返回数列A中下标在i,j里的最小(大）值，也就是说，RMQ问题是指求区间最值的问题。算法朴素（即搜索），O(n)-O(qn)online。线段树，O(n)-O(qlogn)online。(这个稍后补...
2019-07-30 21:48:35
708
原创 单调栈&单调队列
单调栈&单调队列介绍单调栈和单调队列是两种很简单,但是很强大的数据结构.一般不会直接出裸题,常常作为优化手段使用.(多见于dp)单调队列实际上是升级版的单调栈.单调栈单调栈可以在O(n)时间复杂度下完成以下操作对于给定的a[ ]数组,在O(n)时间内生成数组 L[ ],其中L[i]表示a[i] 左边/右边 第一个 小于/大于 a[i]的元素的下标(常记录下标,可以使得操作更灵...
2019-07-30 21:46:54
317
原创 树状数组
树状数组十年岐路，空负曲江花介绍参考资料树状数组就是以数组的形式来模拟树,在代码很简洁的情况下,能起到部分代替线段树的效果.而且此算法常数较小,空间开销也很小,是一个非常轻量级的数据结构.思想图中黑色的是原数组,红色的是树状数组.我们发现树状数组的空间开销是O(n)的.我们以八个元素(从1开始记数会比较方便)求和为例.假设原数组是a[],树状数组是c[].我们不难发现C[1...
2019-07-30 21:45:43
172
原创 链式前向星
链式前向星介绍链式前向星是一种用于存图的数据结构,比较适用于存稀疏图.其综合了邻接表,邻接矩阵的优缺点,然后在前向星的基础上进行改进.时间复杂度,空间复杂度,查询复杂度都是O(m)初始化void CFSInit() { // 链式前向星初始化 cnt = 1; // 其实这里是0也无所谓 memset(head, 0, sizeof(head));}插入void ...
2019-07-30 21:44:39
189
原创 分层最短路
分层最短路介绍分层图最短路在最短路的基础上,增加了一个条件:可将 k 条边的权值变为 0.分析这种问题我们可以想到一种做法:如图,我们构建一个多层的图,其中每一层都是和题目中给的图相同.(图中假设k==1)上面的层表示不将任何边的权值变为0,而下面的这一层表示使用了这个机会后的状态.也就是0号节点可以不使用机会,转移到2号节点,也可以使用机会转移到7号(其实就是二号的镜像节点)....
2019-07-30 21:43:26
381
原创 斯特林公式
斯特林公式简介斯特林公式的常见表示形式显而易见,这个公式主要是用来求近似的阶乘的值的,在竞赛中往往只采用第一个形式,其精确度已经足够用来求阶乘位数了.lg(n!)=lg(2πn)/2+n∗(lg(n)−lg(e)) 这个公式就是图中第一个式子左右同时求对数得到的.不难发现,[10x,10(x+1) )之间囊括了所有长度为x+1的数,而lg(m*10^x)=x+lg(m) ,而lg(m...
2019-07-30 21:42:26
10134
原创 树的直径
树的直径概念给定一棵树,树中每个边都有权值,树中两点之间的距离定义为连接两点的路径边权和.树中最远的两点之间的距离称之为树的直径,也就是树的最长链(偶尔也指代为一条路径).树的直径有两种求法,都是O(n)的.一种是基于树形dp(之后再补上).一种是基于搜索.搜索我们随便找一个节点作为根(之前如果有根就不用换).进行一次搜索,找到距离根最远的节点p,然后再将p作为起点,寻找一个距离p最远的...
2019-07-30 21:41:37
160
原创 MR素性探测
MR素性探测简介MR算法全称是Miller-Rabin测试,是一个非确定的算法,用于判断一个数是否是质数.虽然是一个非确定的算法,但是只要巧妙地选取参数,在一定范围内就是一个确定性的算法.前置条件:费马小定理 1 ≡ a^(p-1) (mod p)Miller和Rabin两个人的工作让Fermat素性测试迈出了革命性的一步，建立了传说中的Miller-Rabin素性测试算法。 新的测试基...
2019-07-30 21:40:43
1172
原创 HDU2546饭卡(01dp+sort)
HDU2546文章目录HDU2546题意输入输出思路关键结论AC代码题意电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上...
2019-04-10 23:37:01
179
原创 HDU3466 Proud Merchants (01dp + 排序)
HDU3466文章目录HDU3466中文题意思路AC代码启示中文题意给出n个商品,以及自己的钱数m,然后以下n行,每一行给出p,q,v三个数,表示第i个商品的价格,以及最少需要多少钱才能进行购买,和收益求最大价值思路根据HDU2546(饭卡)的经验,我们也不难发现这个题的产品应该也是需要排序的,但是每个商品有两个变量,这个就带来了排序的困难.如果仅凭直觉,到底是以哪个参数排序为主...
2019-04-10 23:35:56
149
原创 马拉车算法
马拉车算法参考资料文章目录马拉车算法简介思路变量预处理算法代码简介马拉车算法是一种在O(n)时间内求一个字符串的最长回文子串的算法思路对于最长回文子串,我们可以有很多朴素算法比如穷举所有子串,然后验证这些子串是否是回文的,这样的复杂度是O(n^3),比如我们遍历数组,对于每一个元素,我们都认为其是某个回文子串的中心,我们同时向两边伸展,然后取其中的最大值,这样的算法的复杂度是...
2019-04-07 16:27:36
1057
原创 CF455A Boredom(简单dp)
CF455A题目链接文章目录CF455A题意输入输出解析代码启示大神代码题意给你长为 N 的整数序列a,你可以选择其中一个数ak,你会得到与这个数相同的分数,然后数列中和 ak+1 ak-1相同的数都会被删掉,求最多的分数输入第一行给出一个n接下来在一行中给出 n个数,第i个数表示ai输出输出可得到的最多的分数解析这个题肯定是用哈希来表示每个数出现了多少次,然后自小到大遍...
2019-03-21 21:09:10
654
原创 CF1034A Enlarge GCD(数论+贪心)
CF1034A文章目录CF1034A题意输入输出解析代码题意给你n个数,求最少去掉几个数能让这些数的最大公因数变大输入第一行给出一个n(2<=n<=3e5)第二行给出n个数,表示a1,a2…an,其中ai表示第i个数输出输出最少删掉的数解析关于一堆数的最大公约数,思路还是唯一分解定理.然后我们发现对于每个质因数,似乎只要把为0的去掉就可以了,但是!!!如果a...
2019-03-21 17:55:52
396
原创 CF1027D Mouse Hunt(dfs+图论)
CF1027D文章目录CF1027D题意输入输出解析代码启示题意n间宿舍里有老鼠,老鼠(只有一只)可能出现在任何一间寝室,然后它在第i个寝室里待一秒后一定会跑向第c[i]个寝室,给出在每个寝室布置陷阱的成本,求无论老鼠初始出现在那个寝室,一定会被抓住的最低成本.输入第一行给出n(1<=n<=2e5)第二行给出n个数字,每个大小都是[1,1e4],第i个表示c[i],即在...
2019-03-20 15:23:00
268
原创 CF1029C Maximal Intersection(枚举)
CF1029C文章目录CF1029C题意输入输出解析代码启示题意给你n个线段,给出其左右端点,求去掉其中一个边,剩下的线段的最大交集输入第一行给出一个n(2<=n<=3e5)接下来N行,每一行给出l,r(0<=l<=r<=1e9)输出输出n-1条边的最大交集.解析看到这个题我想起了之前做过的一个题(CF1132C),博客链接当时那个题是枚举去...
2019-03-20 15:07:40
263
原创 CF1020C Elections(枚举+贪心)
CF1020C题目链接文章目录CF1020C题意输入输出解析代码启示题意这个题的背景是贿赂选民,从而让自己的组织能够上台.自己组织的编号是1.然后列出选民想要选的组织,以及收买他们的代价.求最小代价.输入第一行给出n,m,表示选民数量和组织数量,组织按照[1,2,3…m]编号,范围都是[1,3000]然后之后n行选民,每一行给出p,c,表示此位选民想投的组织和收买的代价 ,...
2019-03-20 14:49:04
263
原创 CF1138B Circus(数学+方程暴力求解)
CF1138B题目链接文章目录CF1138B中文题意输入输出解析AC代码总结中文题意给出N(保证是偶数)个人的资料,其中c[i]为1表示此人可以扮演小丑,a[i]为1表示此人可以扮演艺术家,然后让你把这群人分成两组.有三点要求两组人数必须相等.第一组的小丑数量必须等于第二组的艺术家数量一个人只能被分在一个组里面输入第一行给出N(2<=n<=5000)随后一...
2019-03-20 13:55:33
263
原创 数论初探
数论初探文章目录数论初探质数埃氏筛欧拉筛每个数的质因数分解快速乘&快速幂lowbit()求某数二进制1的个数lowbit法__builtin_popcountn&(n-1)平方和扩展欧几里得算法ax+by=c得到最小整数 ```X = (c/gcd(a,b)*x0%r+r)%r```逆元定义计算暴力费马小定理+快速幂欧拉定理+快速幂扩展欧几里得算法递推求逆元```inv[i]=(...
2019-03-15 18:22:06
244
原创 浮点误差
浮点误差参考博客-韬光养晦综述由于计算机存储格式限制,浮点数是存在误差的,这一点在计算几何中尤为突出,以下来探讨这个问题.浮点数的精度占字节数数值范围十进制精度位数float4-3.4e-38～3.4e386~7double8-1.7e-308～1.7e30814~15对于同一个数,可能经由不同的计算方法得到,所以在低几位上可能不同,这个对...
2019-03-15 18:20:29
669
原创 数位DP入门
数位dp数位dp是一种模板性很强的,但又比较灵活的动态规划类型其主要由两种实现方式,一种是预处理,一种是记忆化搜索.前者比较复杂,而且不直观,故我们在此仅讨论第二种情况一般来说,此算法主要由两部分组成,一个solve()函数,一个dfs()函数.solve(n)主要是用于给出从[1,n]之间符合题目要求的数的个数/和/费用等,故求[m,n]之间符合的个数一般是由solve(n)-solve(...
2019-03-15 18:18:57
275
原创 差分与前缀和
差分与前缀和绪论差分与前缀是两个相反的过程,其中差分旨在以递推的形式记录数组元素,前缀和是以求和的方式灵活地面对区间询问区间加常数给定一个序列
2019-03-15 18:17:51
1200
原创 manjaro折腾小记
manjaro折腾小记使用manjaro半年了,中途遇见很多很多问题,在此记录,以备以后查询之用参考资料GAWEGORimorta源设置设置官方镜像源(core,extra,community,multilib)sudo pacman-mirrors -i -c China -m rank //更新镜像排名,图形化界面,选中前几个即可sudo pacman -Syy //更新数据源...
2019-03-15 18:16:18
1912
原创 王爽dos编译环境搭建
Dos环境搭建最近在自学王爽的《汇编语言》,文中提到了可以充分利用Dos的debug.exe工具来进行调试,所以开发选在dos环境下非常方便而且原汁原味Linux下有一个开源的模拟器dosemu,可以实现大部分功能,还可以实现文件夹共享,也就是在Linux环境下编写完汇编代码之后可以直接切换到dosemu中进行编译链接运行,非常的方便.但是我发现有些命令不兼容!这就非常的不方便,因此决定采用虚...
2019-03-06 22:51:23
591
原创 并查集进阶
并查集进阶文章目录并查集进阶绪论普通并查集初始化搜索合并带权并查集初始化搜索合并种类并查集例题HDU3047(种类并查集)HDU3635(带权并查集)POJ1988(带权并查集)POJ2912(种类并查集)POJ1456(普通并查集)绪论我本来以为并查集是一种很简单的数据结构,但是实在是被kuangbin的专题虐的死去活来,故在此总结一下并查集目前有三部分: 普通并查集,带权并查集,种类并...
2019-01-23 21:30:24
587
6
原创 [数据结构复习]排序
排序基本概念排序：给定一组记录的集合{r1, r2, ……, rn}，其相应的关键码分别为{k1, k2, ……, kn}，排序是将这些记录排列成顺序为{rs1, rs2, ……, rsn}的一个序列，使得相应的关键码满足ks1≤ks2≤……≤ksn（称为升序）或ks1≥ks2≥……≥ksn（称为降序）。正序：待排序序列中的记录已按关键码排好序。逆序（反序）：待排序序列中记录的...
2019-01-08 00:23:17
389
原创 [数据结构复习]查找
查找文章目录查找概述线性表查找顺序查找改进后的顺序查找优点缺点折半查找条件基本思想实现折半查找判定树定义构造性能分析索引顺序查找查找过程要求树表查找动态查找表的特点二叉排序树性质查找路径插入构造删除三种情况删除叶子节点删除有一棵子树的节点删除有两棵子树的节点性能分析平衡二叉树定义基本思想调整性能B-树定义&&查找散列表基本思想散列函数数字分析法折叠法除留余数法随机数法总结冲突处理...
2018-12-20 14:52:00
464
原创 [数据结构复习]图论
图文章目录图绪论一笔画问题巧渡河问题逻辑结构定义结构对比概念图的存储邻接矩阵基本思想特点邻接表基本思想十字链表邻接多重表DFS&&BFS连通性生成树最小生成树MSTPrim算法Kruskal 算法拓扑排序AOV网拓扑排序基本思想实现AOE网定义性质事件最早发生时间ve[k]事件的最迟发生时间vl[k]活动的最早开始时间e[i]活动的最晚开始时间l[i]最短路径单源最短路——Dij...
2018-12-19 00:25:55
692
原创 树和二叉树
树和二叉树文章目录树和二叉树@[toc]树的基本术语二叉树定义特点特殊二叉树斜树满二叉树介绍特点完全二叉树定义特点基本性质二叉树的顺序存储结构二叉树的链式存储表示二叉链表基本思想结构特点三叉链表基本思想结构双亲链表结构线索链表二叉树遍历遍历实现由遍历序列求二叉树二叉树递归应用线索二叉树概念线索链表树的存储结构双亲表示法孩子链表表示法孩子兄弟表示法森林和二叉树的转化森林化二叉树转化思路具体操作二...
2018-12-17 20:54:53
338
原创 二叉树递归应用
二叉树递归应用此文档主要是用来记录二叉树的一些递归操作.文章目录二叉树递归应用结构建树求叶子节点个数求二叉树深度删除指定元素及其子树求先序序列中第k个位置的节点的值根据前缀表达式建树中缀表达式建树结构typedef struct node { // 二叉树节点结构 char data; struct node *lchild; struct node *rchild...
2018-12-16 19:24:09
320
原创 [组合数学]卡特兰数
[组合数学]卡特兰数文章目录[组合数学]卡特兰数问题描述递归写法递推写法适用范围卡特兰数是在复习数据结构时遇到的一个问题。问题描述最初的问题是这样：有n个元素按a1,a2,a3…an的次序依次进栈(容量无穷)，且每个元素只允许进一次栈，则可能的出栈序列有多少种？这个问题在数量少的情况下可以进行模拟，但是仔细思索这是一个组合数学的问题。递归写法首先，我们设f（n）=序列个数为...
2018-12-08 17:22:47
253
原创 大毛数蚂蚁(法里数列、二分搜索)
大毛数蚂蚁题干大毛家的后花园有两个蚂蚁王国：A国和B国。现在两个王国即将开战，大毛前去观战。大毛以非人的动态视力分别数出了两个王国的蚂蚁士兵数量，记为a和b。定义双方的实力对比为a:b。大毛虽然得到了双方蚂蚁士兵的精确数量，但由于a和b数值太大，难以一眼看出它们的关系。大毛正想着怎么把蚂蚁塞进饲养员的被窝里，并没有心思去理解这么复杂的比例。因此大毛希望你能用两个不超过L的数字a’和b’代替a和...
2018-12-02 15:04:51
489
原创 ACM常用算法模板
常用模板/算法总结文章目录常用模板/算法总结@[toc]卢卡斯求组合数欧拉筛快速阶乘取模欧拉函数（欧拉筛版）卢卡斯求组合数/*(C n,m) % p*/#include<cstdio>#include<iostream>using namespace std;#define ll long longll n, m, p;ll pow_m(ll a...
2018-12-01 14:19:23
416
原创 C语言版二叉树构造&&遍历
二叉树构造&amp;&amp;遍历基于二分搜索的启发，将查找的复杂度由朴素的O(n) 降低至 O(log n),故产生此数据结构 : 二叉树。二叉树有两种构造方式，一种是顺序存储格式，也就是用数组来存储；另一种是链表。他们的优缺点和线性表中几乎一样：数组支持随机存取，实现简单，结构直观，缺点是添加删除不便，而且空间固定，不易修改，要么不足，要么浪费。链式的结构复杂，遍历需要算法，...
2018-10-07 19:23:37
3063
1
原创 动态规划初步—— 背包问题
动态规划初步动态规划初步动态规划认知01 背包问题算法优化空间优化恰好装满常数优化完全背包问题算法思维陷阱动态规划认知 在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。01 背包问题有n件物品和一个容量为m的背包，放入第ｉ件物品所需要的空间为ｗi，第ｉ...
2018-07-20 23:58:35
238
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人