3 SherlckOuO

尚未进行身份认证

这个人真的很懒,什么都没写

等级
TA的排名 23w+

字符串哈希 模板

最近看了下字符串哈希的算法,学习了大佬的博客,这里小结一下。顺便附上大佬博客的链接,方便日后回顾。字符串哈希函数总结wikioi—字符串哈希如何解决哈希冲突—暴雪的哈希算法哈希:我的理解是将字符当作某一进制的数来看,这样相同的字符串就会有一样的值,不相同的字符串的值就不同。但值得注意的是这个进制必须大于128,而且为减少哈希冲突,需要构建不同的哈希函数。记录下我学的在竞赛中比...

2019-10-07 18:47:53

卡特兰数 大数求法 火车进站

时间限制:C/C++1秒,其他语言2秒空间限制:C/C++32768K,其他语言65536K64bitIOFormat:%lld火车进站题目链接题目描述一列火车n节车厢,依次编号为1,2,3,…,n。每节车厢有两种运动方式,进栈与出栈,问n节车厢出栈的可能排列方式有多少种。输入描述:一个数,n(n\leq60000)n(n≤60000)输出描述:一个数s表示n节...

2019-09-17 16:06:51

单调栈算法 Largest Rectangle in a Histogram

今天学了一下单调栈算法,给大伙分享下心得。定义:单调栈,顾名思义,是栈内元素保持一定单调性(单调递增或单调递减)的栈。这里的单调递增或递减是指的从栈顶到栈底单调递增或递减。既然是栈,就满足后进先出的特点。与之相对应的是单调队列。我的理解是将入栈元素按照某种单调顺序排列,在遇到逆序的时候将栈顶元素弹出,直到栈为空。然后看一看例题:LargestRectangleinaHistog...

2019-09-13 21:53:02

ACM 最小生成树 Kruskal Prim 算法模板

定义:求最小生成树,有两种算法。一种是Prim算法,另一种是Kruskal算法。你们可以先看下这个最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示看了都说好嘻嘻先讲一种比较简单的————Kruskal算法贪心+并查集#include<iostream>#include<algorithm>usingnamesp...

2019-09-05 21:40:37

洛谷 P1108 题解

题目描述“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者,你必须遵循以下的问题建议:“低价购买;再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下,求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(2^{16}216范围内的正整数),你可以选择在哪些天购买这支股票。每次购...

2019-09-03 23:21:05

P736 创意吃鱼法

题目描述回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中,然后开始思考:到底要以何种方法吃鱼呢(猫猫就是这么可爱,吃鱼也要想好吃法^_*)。她发现,把大池子视为01矩阵(0表示对应位置无鱼,1表示对应位置有鱼)有助于决定吃鱼策略。在代表池子的01矩阵中,有很多的正方形子矩阵,如果某个正方形子矩阵的某条对角线上都有鱼,且此正方形子矩阵的其他地方无鱼,猫猫就可以从这个正方形子矩阵“对角线的一...

2019-09-01 10:26:18

传纸条

题目描述小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排做成一个mm行nn列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈了。幸运的是,他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里,小渊坐在矩阵的左上角,坐标(1,1(1,1),小轩坐在矩阵的右下角,坐标(m,n)(m,n)。从小渊传到小轩的纸条只可以向下或者向右...

2019-08-30 16:44:43

后缀表达式 题解

题目描述所谓后缀表达式是指这样的一个表达式:式中不再引用括号,运算符号放在两个运算对象之后,所有计算按运算符号出现的顺序,严格地由左而右新进行(不用考虑运算符的优先级)。如:3*(5–2)+7对应的后缀表达式为:3.5.2.-*7.+@。’@’为表达式的结束符号。‘.’为操作数的结束符号。输入格式输入:后缀表达式输出格式输出:表达式的值输入输出样例输入#1复制3.5.2.-*...

2019-08-28 17:10:13

二分答案 二分查找

二分答案大佬是这样解释的☟原博客 以下添加了一些个人理解 1.使用场景二分答案一般使用在求解符合条件的最小值或者最大值上面,当我们遇到这两个问题的时候,一般都可以使用二分答案来解决问题。(我觉得这段讲的不是很好)条件:所求的答案具有单调性,可以枚举答案,能判断答案的可行性特征:①求xxx最大值最小②求xxx最小值最大.③使最近的距离最大etc2.什么是二分...

2019-08-26 17:45:02

洛谷 P1325 雷达安装 贪心

**-将问题转化为区间覆盖问题此题求的是需要多少个头尾不相交的区间贪心策略:按区间的左端点排序,若i的左端点与i-1的右端点不相交(在精度范围内)就增加一个区间**#include<iostream>#include<cmath>#include<algorithm>usingnamespacestd;intn,r;typ...

2019-08-24 11:21:39

并查集与最小生成树 模板

"在计算机科学中,并查集是一种树型的数据结构,用于处理一些不交集(DisjointSets)的合并及查询问题。有一个联合-查找算法(union-findalgorithm)定义了两个用于此数据结构的操作:Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。Union:将两个子集合并成同一个集合。由于支持这两种操作,一个不相交集也常被称为联合-查找数据结构(unio...

2019-08-18 11:43:41

算法竞赛指南———打卡 0x03 前缀和与差分

先说下基本知识前缀和一维前缀和如果我给你一串长度为n的数列a1,a2,a3…an,再给出m个询问,每次询问给出L,R两个数,要求给出区间[L,R]里的数的和,你会怎么做,若是没有了解过前缀和的人看到这道题的想法可能是对于m次询问,我每次都遍历一遍它给的区间,计算出答案,这样子的方法固然没错,但是其时间复杂度达到了O(n*m),如果数据量稍微大一点就有可能超时,而我们如果使用前缀和的方法来...

2019-08-07 18:13:10

二进制状态压缩

二进制状态压缩,即将一个长度为m的bool数组用一个m位的二进制数来表示和储存操作运算取出整数n在二进制表示下的第k位(n>>k)&1取出整数n在二进制表示下的第0~k-1位(后k位)n&((1<<k)-1)取出整数n在二进制表示下的第k位取反nxor(1<<k)取出整数n在二进制表示下的第k...

2019-08-06 10:49:05

位运算+快速幂

位运算求快速幂1.一般求幂intpow1(inta,intb){intr=1;while(b--)r*=a;returnr;}2.快速求幂intpow2(inta,intb){intr=1,base=a;while(b!=0){if(b%2)r*=base;base*=base;b/=2...

2019-08-06 10:41:30

由数据范围反推算法复杂度以及算法内容

由数据范围反推算法复杂度以及算法内容一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下,C++代码中的操作次数控制在10e7以内为最佳。下面给出在不同数据范围下,代码的时间复杂度和算法该如何选择:n≤30n≤30,指数级别,dfs+剪枝,状态压缩dpn≤100n≤100=>O(n3)O(n3),floyd,dpn≤1000n≤1000=>O(n2)O(...

2019-08-06 10:40:01

BFS----浅尝

BFS:适用于图形结构的搜索,与数据结构中的队列紧密相连。对于这种算法主要步骤如下:找到当前可拓展的点,将他放入候选队列中每次选取候选队列的队头作为当前状态性质:对于广搜而言,他是一种逐层遍历的算法,所有状态按照入队的先后顺序具有层次的单调性,也就是所需的步数的单调性。如果每次拓展恰好对应一步,那么当第一个状态第一次被访问(入队)就会得到从起始状态到达该状态的最少步数。//模板#i...

2019-07-26 09:12:36

acm从入门到放弃——day11

1.KMP算法是用来处理一对一的匹配的。朴素的匹配算法,或者说暴力匹配法,就是将两个字符串从头比到尾,若是有一个不同,那么从下一位再开始比。这样太慢了。所以KMP算法的思想是,对匹配串本身先做一个处理,得到一个next数组。这个数组是做什么用的呢?next[j]=k,代表j之前的字符串中有最大长度为k的相同前缀后缀。记录这个有什么用呢?对于ABCDABC这个串,如果我们匹配ABCDAB...

2019-07-11 18:53:26

acm从入门到放弃——day6

dp(DynamicProgramming)前人的总结,个人感觉是不错的,点一点试试看了感觉云里雾里的,就想着去做个题试试,所以↓做了一下下面这个题题目背景uim神犇拿到了uoi的ra(镭牌)后,立刻拉着基友小A到了一家……餐馆,很低端的那种。uim指着墙上的价目表(太低级了没有菜单),说:“随便点”。题目描述不过uim由于买了一些辅(e)辅(ro)书,口袋里只剩MM元(M...

2019-07-07 09:12:38

acm从入门到放弃——day4

工作九九六,生病ICU 马爸爸云:”但是年轻人要明白,幸福是奋斗出来的!不为996辩护,但向奋斗者致敬!好的话不多说,来看看今天学到了什么东西。dfs(深度优先搜索:DepthFirstSearch)对于像我这样的蒻...

2019-07-05 09:35:43

acm从入门到放弃——day3

第一次打表还有些小紧张个人理解:打表主要用于答案相对固定和原本代码时间复杂度较为高,容易运行超时的题,比如素数,回文数这些是不会变的可以用打表法。对于规定范围内有固定比例的数字的选择也可用打表法。**此法属于变态暴力法,非万不得已,还是少用为好**dfs算法dfs算法,即深度优先算法(DepthFirstSearch)。理解深搜的重要关键点是在于解决“现在该怎么做”。...

2019-07-04 08:34:06

查看更多

勋章 我的勋章
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv2
    勤写标兵Lv2
    授予每个自然周发布4篇到6篇原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。