- 博客(24)
- 收藏
- 关注
RSS订阅原创 Opencv 环境配置 5分钟搞定
大概分为这几步走下载opencv添加环境变量创建一个空项目 配置项目文件测试下面看详细步骤:1.下载opencv点击release选择适合自己平台的安装包下载，安装2.添加环境变量...
2019-11-18 16:45:40
277
原创 字符串哈希 模板
最近看了下字符串哈希的算法，学习了大佬的博客，这里小结一下。顺便附上大佬博客的链接，方便日后回顾。字符串哈希函数总结wiki oi—字符串哈希如何解决哈希冲突—暴雪的哈希算法哈希：我的理解是将字符当作某一进制的数来看，这样相同的字符串就会有一样的值，不相同的字符串的值就不同。但值得注意的是这个进制必须大于128，而且为减少哈希冲突，需要构建不同的哈希函数。记录下我学的在竞赛中比...
2019-10-07 19:19:10
235
原创 卡特兰数 大数求法 火车进站
时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32768K，其他语言65536K64bit IO Format: %lld火车进站题目链接题目描述一列火车n节车厢，依次编号为1,2,3,…,n。每节车厢有两种运动方式，进栈与出栈，问n节车厢出栈的可能排列方式有多少种。输入描述:一个数，n (n \leq 60000)n(n≤60000)输出描述:一个数s表示n节...
2019-09-17 16:51:27
307
原创 单调栈算法 Largest Rectangle in a Histogram
今天学了一下单调栈算法，给大伙分享下心得。定义：单调栈，顾名思义，是栈内元素保持一定单调性（单调递增或单调递减）的栈。这里的单调递增或递减是指的从栈顶到栈底单调递增或递减。既然是栈，就满足后进先出的特点。与之相对应的是单调队列。我的理解是将入栈元素按照某种单调顺序排列，在遇到逆序的时候将栈顶元素弹出，直到栈为空。然后看一看例题：Largest Rectangle in a Histog...
2019-09-13 22:03:24
193
原创 ACM 最小生成树 Kruskal Prim 算法模板
定义：求最小生成树，有两种算法。一种是 Prim算法 ，另一种是Kruskal算法。你们可以先看下这个最小生成树(Kruskal(克鲁斯卡尔)和Prim(普里姆))算法动画演示 看了都说好 嘻嘻先讲一种比较简单的————Kruskal算法贪心+并查集#include <iostream>#include <algorithm>using namesp...
2019-09-08 23:01:04
244
3
原创 洛谷 P1108 题解
题目描述“低价购买”这条建议是在奶牛股票市场取得成功的一半规则。要想被认为是伟大的投资者，你必须遵循以下的问题建议:“低价购买；再低价购买”。每次你购买一支股票,你必须用低于你上次购买它的价格购买它。买的次数越多越好!你的目标是在遵循以上建议的前提下，求你最多能购买股票的次数。你将被给出一段时间内一支股票每天的出售价(2^{16}216范围内的正整数)，你可以选择在哪些天购买这支股票。每次购...
2019-09-05 22:08:56
191
原创 P736 创意吃鱼法
题目描述回到家中的猫猫把三桶鱼全部转移到了她那长方形大池子中，然后开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 ^_*）。她发现，把大池子视为01矩阵（0表示对应位置无鱼，1表示对应位置有鱼）有助于决定吃鱼策略。在代表池子的01矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“对角线的一...
2019-09-01 10:26:18
83
原创 传纸条
题目描述小渊和小轩是好朋友也是同班同学，他们在一起总有谈不完的话题。一次素质拓展活动中，班上同学安排做成一个mm行nn列的矩阵，而小渊和小轩被安排在矩阵对角线的两端，因此，他们就无法直接交谈了。幸运的是，他们可以通过传纸条来进行交流。纸条要经由许多同学传到对方手里，小渊坐在矩阵的左上角，坐标(1,1(1,1)，小轩坐在矩阵的右下角，坐标(m,n)(m,n)。从小渊传到小轩的纸条只可以向下或者向右...
2019-08-30 16:44:43
209
原创 后缀表达式 题解
题目描述所谓后缀表达式是指这样的一个表达式：式中不再引用括号，运算符号放在两个运算对象之后，所有计算按运算符号出现的顺序，严格地由左而右新进行（不用考虑运算符的优先级）。如：3*(5–2)+7对应的后缀表达式为：3．5．2．-*7．+@。’@’为表达式的结束符号。‘.’为操作数的结束符号。输入格式输入：后缀表达式输出格式输出：表达式的值输入输出样例输入 #1 复制3.5.2.-*...
2019-08-28 17:10:13
1254
原创 二分答案 二分查找
二分答案大佬是这样解释的☟原博客 以下添加了一些个人理解 1.使用场景二分答案一般使用在求解符合条件的最小值或者最大值上面，当我们遇到这两个问题的时候，一般都可以使用二分答案来解决问题。（我觉得这段讲的不是很好）条件：所求的答案具有单调性，可以枚举答案，能判断答案的可行性特征：①求xxx最大值最小 ② 求xxx最小值最大.③ 使最近的距离最大 etc2.什么是二分...
2019-08-26 17:45:02
270
原创 洛谷 P1325 雷达安装 贪心
**- 将问题转化为区间覆盖问题此题求的是需要多少个头尾不相交的区间贪心策略：按区间的左端点排序，若i的左端点与i-1的右端点不相交（在精度范围内）就增加一个区间**#include <iostream>#include <cmath>#include <algorithm>using namespace std;int n, r;typ...
2019-08-24 11:21:39
236
原创 并查集与最小生成树 模板
"在计算机科学中，并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。有一个联合-查找算法（union-find algorithm）定义了两个用于此数据结构的操作：Find：确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。Union：将两个子集合并成同一个集合。由于支持这两种操作，一个不相交集也常被称为联合-查找数据结构（unio...
2019-08-18 11:43:41
95
原创 算法竞赛指南———打卡 0x03 前缀和与差分
先说下基本知识前缀和一维前缀和如果我给你一串长度为n的数列a1,a2,a3…an,再给出m个询问，每次询问给出L，R两个数，要求给出区间[L,R]里的数的和，你会怎么做，若是没有了解过前缀和的人看到这道题的想法可能是对于m次询问，我每次都遍历一遍它给的区间，计算出答案，这样子的方法固然没错，但是其时间复杂度达到了O(n*m)，如果数据量稍微大一点就有可能超时，而我们如果使用前缀和的方法来...
2019-08-07 18:13:10
151
原创 二进制状态压缩
二进制状态压缩，即将一个长度为m的bool数组用一个m位的二进制数来表示和储存操作运算取出整数n在二进制表示下的第k位(n>>k)&1取出整数n在二进制表示下的第0~k-1位（后 k 位）n&((1<<k)-1)取出整数n在二进制表示下的第k位取反n xor (1<<k)取出整数n在二进制表示下的第k...
2019-08-06 10:49:05
207
原创 位运算+快速幂
位运算求快速幂1.一般求幂int pow1(int a,int b){ int r=1; while(b--) r*=a; return r;} 2.快速求幂int pow2(int a,int b){ int r=1,base=a; while(b!=0){ if(b%2) r*=base; base*=base; b/=2...
2019-08-06 10:41:30
516
转载 由数据范围反推算法复杂度以及算法内容
由数据范围反推算法复杂度以及算法内容一般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
150
原创 BFS----浅尝
BFS:适用于图形结构的搜索，与数据结构中的队列紧密相连。对于这种算法主要步骤如下：找到当前可拓展的点 ，将他放入候选队列中每次选取候选队列的队头作为当前状态性质：对于广搜而言，他是一种逐层遍历的算法，所有状态按照入队的先后顺序具有层次的单调性，也就是所需的步数的单调性。如果每次拓展恰好对应一步，那么当第一个状态第一次被访问（入队）就会得到从起始状态到达该状态的最少步数。//模板#i...
2019-07-26 09:12:36
127
原创 acm从入门到放弃——day11
1.KMP算法 是用来处理一对一的匹配的。朴素的匹配算法，或者说暴力匹配法，就是将两个字符串从头比到尾，若是有一个不同，那么从下一位再开始比。这样太慢了。所以KMP算法的思想是，对匹配串本身先做一个处理，得到一个next数组。这个数组是做什么用的呢？next [j] = k，代表j之前的字符串中有最大长度为k 的相同前缀后缀。记录这个有什么用呢？对于ABCDABC这个串，如果我们匹配ABCDAB...
2019-07-11 18:53:26
96
原创 acm从入门到放弃——day6
dp（Dynamic Programming）前人的总结，个人感觉是不错的，点一点试试看了感觉云里雾里的，就想着去做个题试试，所以 ↓ 做了一下下面这个题题目背景uim神犇拿到了uoi的ra（镭牌）后，立刻拉着基友小A到了一家……餐馆，很低端的那种。uim指着墙上的价目表（太低级了没有菜单），说：“随便点”。题目描述不过uim由于买了一些辅（e）辅（ro）书，口袋里只剩MM元(M...
2019-07-07 09:12:38
210
原创 acm从入门到放弃——day4
工作九九六，生病ICU 马爸爸云：”但是年轻人要明白，幸福是奋斗出来的！不为996辩护，但向奋斗者致敬！好的话不多说，来看看今天学到了什么东西。dfs(深度优先搜索：Depth First Search)对于像我这样的蒻...
2019-07-05 09:35:43
166
原创 acm从入门到放弃——day3
第一次打表还有些小紧张个人理解：打表主要用于答案相对固定和原本代码时间复杂度较为高，容易运行超时的题，比如素数，回文数这些是不会变的可以用打表法。对于规定范围内有固定比例的数字的选择也可用打表法。**此法属于变态暴力法，非万不得已，还是少用为好**dfs算法dfs算法，即深度优先算法(Depth First Search)。理解深搜的重要关键点是在于解决“现在该怎么做”。...
2019-07-04 08:34:06
126
原创 String类的简单重载
**用c++简单对String类重载**完成功能：创建简单的String类获取字符串的长度将小写变为大写大写变为小写踩才过的坑刚开始未对赋值运算符重载，造成堆栈错误#include <iostream>using namespace std;class String{ char* content; int len;publi...
2019-06-16 22:35:11
306
原创 二维数组排序
先来理一下思路，对二维数组的排序和对一维数组排序有什么区别，【坏笑】当然是多了一维呀。哈哈哈哈哈思路很简单：将二维的转为一维的来做；先看一个简单的一维数组例如：一维数组一个for循环搞定。#include<iostream>#include<cstdlib>using namespace std;const int N = 4;int main(){...
2018-12-03 21:32:48
449
原创 hello world
HELLO WORLDMy first blog [haha]now is 2018 12.2 night,I just wanna set post a blog to show I have been here,and I'm gonna do more on this website.So far I'm just a "game-boy" playing games every w...
2018-12-02 21:06:35
94
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人