- 博客(101)
- 资源 (5)
- 问答 (2)
- 收藏
- 关注
RSS订阅
原创 从动态该规划角度理解kmp
kmp是一种高效的字符串匹配算法(模式匹配算法)；给你一个主串m,模式串p。kmp可以找出p在m中的位置；比如主串m：abadabaad和模式串p:abaa;那么p在m中的位置是5;如果是纯暴力(朴素的模式匹配算法)的话时间复杂度会达到O(n*m),是比较高的；但是用kmp的话，时间复杂度会达到O(n+m);kmp是在朴素的模式匹配算法上进行优化的算法，我们首先来用一张图看一下...
2018-08-24 04:49:56
1310
原创 网络流
网络流建模思路一个医院有 n名医生，现有 k个公共假期需要安排医生值班。每一个公共假期由若干天（假日）组成，第 j个假期包含的假日用 Dj表示，那么需要排班的总假日集合为… 。例如，“五一”假期由5月1日至5月7日一共7个假日组成。“元旦”假期由1月1日至1月3日一共3个假日组成。每名医生 可以值班的假日集合是 Si,Si属于D，。例如，李医生可以值班的假日集合包括“五一”假期中的5月3日、5月4日和“元旦”假期中的1月2日。设计一个排班的方案使得每个假日都有一个医生值班并且满足下面两个条件：1.
2020-06-28 15:20:17
920
2
原创 Java实现http协议
1.http协议 http协议是一种用于在网络设备两端传输超文本的协议 此协议分为客户端和服务端 在详细了解此协议之前，我们要清楚 1.客户端一般是指运行在网络设备上的浏览器 2.服务端是提供内容服务的服务器软件 我们来看一下当客户端向服务端发送的请求报文头 这个是由客户端(浏览器)自动构造发送给服务端的 接下来是服务端向客户端的发送的回应报文头...
2020-04-18 22:18:26
4292
2
原创 rxjava在jvm上运行的坑点
1.在RxJava中，默认的调度器运行在守护进程线程上,所以一旦java主线程退出，rxjava的一切活动也会被杀死。为了避免这种情况我们可以让主线程永不停止(可以用while(true)的方法)...
2020-04-01 11:23:09
140
原创 idea+gradle使用的一些技巧
一.导入本地第三方包1.首先在根目录下创建lib文件夹2.将第三包移入lib里面3.在dependencie里面添加 compile fileTree(dir:'lib',includes:['*jar'])如图
2020-01-18 16:26:02
1718
原创 算法期末作业
实验1q1.请实现如下描述的快速选择算法：函数原型 void select(int a[],int beg,int end，int k)//在数组a的beg...end范围内选择最小的k个的元素并将其存于数组a的 beg....beg+k-1位置。要求：（1）采用分治算法：（递归程序）区间beg...end内的选择k小问题定义为: 1.划分算法 2.根据划分位置p，决定三...
2019-12-07 18:27:01
341
原创 jpeg压缩算法
jpeg的压缩分为四个步骤首先明确jpeg一般是将bmp转为jpeg格式的，那么我们就需要清楚bmp和jpeg的文件架构以下是bmp的文件架构项目位图文件头位图信息头彩色表/调色板位图数据以下是jpeg的文件架构四个步骤1将RGB转化为yCbCRYCbCR中的y代表亮度，cb,cr代表绿色和红色的色差，用这种表示方法能够很好的将图的细节区...
2019-11-11 16:35:22
1220
1
原创 A*k最短路讲解
A*k最短路讲解在讲解之前你可能需要了解一下 dijstra的堆实现Dijstra求k短路在松弛的过程中如果把每个点都加进优先队列(堆)，那么如果有泛化的点p在第t次出队，那么此时就能得到源点到p点的第t短的路。但是这个方法用来求k短路过于慢，所以就有了A*来加速寻找k短路的过程。A*A*本质上就是使用了优先队列的bfs。但是优先队列的优先性由一个确定值与一个估值的和来确定。在这里我们...
2019-08-29 14:56:19
513
原创 字典树详解
字典树详解字典树是一种用于统计和排序大量的字符串的数据结构。它的原理是把具有相同前缀的字符建立一颗树。例如，我们有字符acdr,aced,bde,asd,ceed,asdr,frt进行建树的话应该是这样：...
2019-07-06 16:18:10
338
原创 主席树
主席树又叫可持久化线段树 为了实现可持久化这一目的，主席树在建树或者更新的时候会建立多个历史版本，以便于在之后的查询可以随时回到某个历史版本 建立历史版本的方法有多种，但是为了实现空间和时间上的最优，我们采用下面的方法建立历史版本 假定我们现在有一个问题，给你一个长度n为的序列data，和一个序列aux。每一时刻按从左往右的顺序从data数组中拿一个数加入aux数组。求任意一个时刻序列...
2019-06-11 21:18:53
238
原创 划分树讲解
划分树是专门用来求静态区间第k的一种数据结构它主要利用快排的思想来进行建树和查询比如给你一个长度为12序列{1，9，4，5，8，3，4，6，5，2，5，7}我们要按照划分树来建树该怎么建呢1.首先和快速排序一样，分而治之。 我们把平均分为两部分，左区间任何一个数都小于右区间的一个数 同时左右两个区间的序列顺序和原来区间一样 我们还需要统计一下对于原区间[l,r]的任意一个数b...
2019-06-04 19:02:14
370
原创 Hdu-1828~(扫描线 + 周长)
扫描线扫描周长 扫描线扫描周长比扫描面积要麻烦一些,需要解决的问题有两个 1.如何统计每条横线( 也就是平行于x轴的线段的长度 ) 2.如何统计每条竖线( 也就是平行于y轴的线段的长度 )如图 我们发现每次扫描线扫描后投影到根节点的总长度与上次扫描所投影的 总长度的绝对值之差就是本次扫描所多出的边长。 这样我们就解决了第一个问题解决第二个问题的方法有两种 1.与解...
2019-05-28 16:18:45
419
原创 扫描线
扫描线用于求多个不规则多边形相交的问题。例如给你如下图，让你求该图的总面积为了解决此类为题，我们引入了 扫描线 的概念. 扫描线是我们脑海中假象的一根线，它能够按照一个方向来扫描图形得到我们想要的信息； 例如具体到本次问题，那么扫描线的作用可以概述为:扫描线从按平行于x轴的方向，自下而上的扫描每一个图 形，并得到每个图形的面积信息；那么经过扫描线的扫描后，得到的图形如下：很...
2019-05-27 14:41:26
453
原创 README
2019.5.26Hdu_6288 此题整体思路就是二分，但是难点不是在二分上 难点是判断a的b次方是否溢出。我们可以先求出a的b次方，再利用快速幂得出 a的b次方模1e9 + 7的结果，然后该值与a的b次方模 1e9 + 7 比较，相同说明 没有溢出，不同说明溢出 需要注意的是如果直接用c++函数pow来求a的b次方是有误差的，所以我们应该 手写一个求a的b次方的函数。 该题需要...
2019-05-27 10:52:02
204
原创 第十届蓝桥杯 省赛A组 E RSA 解密
这个题应该是填空题中最难的一个了。思路很简单，但是你需要一点python的基础讲一下本题的思路。首先我们要对公钥中的n进行质因子分解，得到p,q。然后根据 d * e %((p - 1) * (q - 1) == 1和扩展欧几里得求出e。RSA是一种不可逆的加密方法，不可逆的原因是公钥特别大，对它分解质因子时间上会很长，普通计算机大概是10年左右，量子计算机一星期就可以...
2019-03-24 17:42:51
4216
19
原创 第十届蓝桥杯省赛 A组 C最大降雨量(思维)
注意读题，求的不是七周中位数的和，而是七周中位数的中位数的最大值如图a,b,c,x,e,f,g分别是每周的中位数。而x是a,b,c,x,e,f,g是这七周的每一周的中位数的中位数题目的要求是让我们最大化这个x;我们可以假定x已经是我们要求的值，那么为了让x符合题目信息，我们必须让第4周的后3天，第5，6，7周的后4天都大于这个值。那么很显然有15个数比x大，那...
2019-03-24 15:02:16
6345
27
原创 关于数据对拍
数据对拍是一种通过找到错误输出数据寻找bug的方法；首先，我们可以跟据题意通过bfs,暴力等方法写出一份正确的代码，然后写个随机生成数据和验证输入输出的代码我们可以拿一道题来熟悉这个流程：路径规划(route)题意很好理解，就是给出起点，和终点，求出起点到终点的所需的步数，其中上下左右，斜着走八个方向都算一步；大致思路就是，优先斜着走，因为斜着走即在水平方向有位移，在竖直方向也...
2019-03-10 18:54:26
581
原创 stl-vector
#include<vector>#include<algorithm>#include<iostream>#define iter vector<int>::iteratorusing namespace std;int main(){//一。初始化 vector <int> data1(10,1);//初始化data1...
2019-02-26 11:57:02
124
原创 stl-string
#include<string>#include<algorithm>#include<iostream>using namespace std;int main(){//一。初始化 string str1("123456",2,2); cout<<str1<<endl; //从小标2开始，长度为2的字符，输出34//...
2019-02-26 11:55:50
266
原创 算法回顾
1. 二分 二分简单理解poj32582. 快速排序 hdu_14253. 搜索 (1)广搜 (2)深搜 深搜(2019CampWinterDay3A,博客链接) 广搜（三个水杯）4. std (1)set (2)map (3)string (5)vector ...
2019-02-15 19:19:39
219
原创 关于写算法题的一些收获
1.在读题思考的过程中，如果有思路(绝对)正确，就把它记录下来。(不管暂时能不能用上)。2.碰到找不出来的bug，就造出一个比较大的数据，代入代码里面一步一步调试。3.训练准确读题的能力，从题中提取信息，把这些信息抽象成能用准确语言（如方程式，关系）表达出来4.用vim写代码...
2019-01-24 13:23:08
281
2
原创 CCPC-Wannafly Winter Camp Day1 F 爬爬爬山(最短路+思维)
题目链接大致思路：刚开始做的时候怎么也做不对。在寻找最短路的过程中会对如何降低山的高度有影响。一直在想如何找出两者之间的联系。所以就一直错。后来经过一位学长提醒，我们只需要关注比1号山高k的山。因为我们有可能降低这些山的高度。比1号山低的山我们其实是不需要关注的，因为虽然下山增加体力，但是在上山的过程中有抵消了。所以是没有影响的。具体的做法是，我们可以把所有比h1 + k高...
2019-01-21 13:06:50
639
原创 关于结构体的构造函数
为了方便结构体的初始化我们需要在结构体内写构造函数；如下：#include<stdio.h>struct node{ int x,y; node(){}; node(int a,int b) : x(a), y(b) {};};int main(){ node data[100]; //注意如果没有无参的构造函数这行代码会出错的 node a =...
2019-01-12 20:21:20
923
原创 二分简单理解
在写题中经常遇到一些需要用到二分策略的题。这些题有些简单有些比较难。但是他们都遵循一些简单的原则。1.大部分题都是二分答案。2.将答案带入问题过程，由这个过程产生的信息与题目中给出的已知信息比较，确定下次的二分的区间。3.确保在这个过程中区间能不断缩小。例题讲解：POJ-3258POJ-3122...
2019-01-11 18:03:48
217
原创 POJ-3122~Pie(二分)
题目链接题目大意：有n个蛋糕，每个蛋糕有个半径。我们需要把这些蛋糕分给F + 1个人。F+1个人分得得蛋糕的大小必须是一样的(形状可以不一样)。分得的蛋糕可以由原来的蛋糕切割下来的，但不能是由几个蛋糕拼凑而成。求如何切才能使分得的蛋糕大小最大。只用输出最后分得的蛋糕的面积即可大致思路：我们可以二分这个最大对蛋糕面积。然后把它带入切蛋糕的过程。求出如果这个面积是正确答...
2019-01-11 18:03:01
271
原创 POJ - 3258~River Hopscotch（二分）
题目链接题目大意：在一条河的起点和终点之间有N块石头，起点和终点上也有石头。农夫可以移走M块石头（不包括起点和终点）使得移走的每两块石头(包括起点和终点)的最短距离最大。求这个值。大致思路：我们可以二分这个最短距离，然后求出如果这个是最短距离，我们需要在原来的基础上去掉几个石头。去掉石头的个数如果比M大，说明我们枚举的最短距离比真正的最短距离大了。去掉的石头个数...
2019-01-11 17:15:28
251
原创 Educational Codeforces Round 44-C. Liebig's Barrels(简单贪心+思维)
题目链接题目大意：给你n * k 个木板，让你组成有n个木桶，每个木桶有k个木板。每个木桶的体积是这个木桶的木板中最短的那个。并且任意两个木桶的体积的差必须<=l。求如何组装才能使n个木桶的体积和最大。输出体积和。解题思路：首先我们先将所有的木板从小到大分成n个块。如果我们想要实现体积最大化，我们需要选出每个块最短的那个木板作为由本块木板组成得木桶的体积。但是题目...
2019-01-10 18:17:15
194
原创 CodeForce Round #484 C - Cut 'em all!s(贪心 + dfs)
题目链接题目大意：给你一个树，你可以通过切割某多条边来制造多个连通块。问你最多到可以切几条边使得偶数大小的连通块最多且剩下的连通块的大小都为偶数；解题思路：用dfs遍历每一颗子树，如果这颗子树大小是偶数，说明可以切这棵子树和它父亲结点相连的那条边。如果是奇数则不切代码如下：#include<stdio.h>#include<string.h...
2019-01-04 00:23:02
170
原创 CodeForce Round #484 B - Bus of Characters(思维+栈)
题目链接 题目大意：公交车有n排座位，每排的座位有两个，且这两个座位的宽度一样。任何两排座位的宽度度都不一样。首先给你一个n，接下来给你n个数字代表第i排座位的宽度。然后给你一个01字符串代表乘客上车的顺序。0和1分别代表内向的人和外向的人。内向的人会从没有人坐的那几排选出一个宽度最小的那排座。外向的人会从有一个人坐的那几排选出宽度最大的那排座。题目要求你根据上车的...
2018-12-26 15:41:46
167
原创 CodeForce Round #483 C.Finite or not?(数论gcd)
题目链接题目大意是：给你三个整数，p,q,b。其中p/q是个分数。该题目要求你给出p/q在b进制下是否是个无限小数。解题思路：首先我们需要知道小数转化为二进制。假定有分数a/b(a<b),要将它转化为k进制。我们需要取a * k / b为第一位。然后让a = a * k % b.重复以上步骤，直到a* k % b == 0;a * k % b 一直不等于0那么就说...
2018-12-25 14:26:55
211
原创 2017CCPC秦皇岛A题~ZOJ - 3981~Balloon Robot
题目链接大意：有一个长度为m的圆形桌子，有n支队伍。然后有p次ac。每次ac给出ac的队伍编号和ac的时间。有一个专门发放气球的机器人，他按照顺时针的方向绕着圆形桌子，一秒移动一个座位。当他移动到第i个位置的时候，他会给下一个位置发放气球。发放气球的数量是该座位上次放气球的时间到这次发放气球的时间中ac的数量。当一个队伍ac后，如果不能立即得到气球，这支队伍就会产生怒气值。...
2018-11-14 19:54:25
298
原创 HDU- A Simple Math Problem(数论)
题目链接题意就是给你一个a,b。并且有x + y = a 且 lcm(x,y) = b, 让你求x,y;大致思路就是根据规律推出公式：设g = gcd(a,b)那么有g * K1 = x, g * K2 = y, 且 k1 和 k2 互质；由K1 和 K2 互质可得 K1 * K2 和 K1 + K2 也互质。又lcm(x,y) * gcd(x,y) = x * y 可...
2018-11-03 21:17:39
162
原创 HDU - 4081（次小生成树 + DFS）
题意要求a/b的最大值。 其中a是任意两点的点权和，b是除去这两点剩下的最小生成树的值。我们可以先求出最小生成树，然后不断删边，然后求出删去这条边后的剩下的点的最小生成树的值（联想到次小生成树）。删边的过程可以用dfs枚举。代码如下啊：#include<stdio.h>#include<math.h>#include<algorithm>...
2018-10-18 09:45:17
353
原创 次小生成树模板
整体思路就是将没有用过的边插入最小生成树中，会形成一个环，我们去掉这个环中最大的那个边，会得到一个新的生成树，次小生成树就是新的生成树中最小的那个。我们用一个数组maxx来记录最小生成树中两点之间最大的权值。用connect数组表示边是否加入最小生成树中，代码如下：#include<stdio.h>#include<algorithm>using name...
2018-10-18 08:23:07
115
原创 HDU - 2489（枚举+最小生成树）
通过dfs枚举所有点集合的情况，然后对这些点进行prim求的最小生成树。然后将边权和点权的比以及点集合存在到一个结构体数组里面，然后先对边权和点权的比进行排序，如果相等的话就按点集合的字典序排序即可；代码如下：#include<stdio.h>#include<string.h>#include<algorithm>#define mms...
2018-10-11 15:21:38
253
原创 字典树模板
#include<stdio.h>#include<string.h>const int INF = 40005;int tire[INF][26], sum[INF], tol = 1;void insert(char* data,int rt);void find(char* data);/*carbohydratecartcarburetorca...
2018-10-09 13:46:57
115
渗透神器明小子
2015-06-06
qt实现当单击树形控件是切换堆栈窗口
2017-10-30
关于多次为指针使用new和使用指针的问题
2017-10-24
TA创建的收藏夹 TA关注的收藏夹
TA关注的人