so_hard.

未归档

Android(6) BFS(7) DFS(10) DP(15) ESP32(1) HDUOJ(7) KMP(2) Linux(2) MySchoolOJ(1) NowCoder(3) PAT(7) PAT甲级题(5) POJ(1) STL(7) 三维(1) 二分答案(1) 前端学习(1) 图论(4) 字符串处理(1) 嵌入式实时操作系统(μC/OS)(3) 并查集(1) 心路历程(2) 思维(6) 扩展kmp(1) 技巧(3) 数学(4) 数论(7) 整理笔记(1) 新姿势(3) 暴力(1) 最小/大表示法(3) 树状数组(1) 游戏(1) 游记(1) 离散化(1) 算法与数据结构(2) 线段树(2) 编程语言学习(1) 胡搞题(1) 蓝桥杯OJ(5) 蓝桥杯历届省赛题目(4) 贪心(3)

/ 注册

全部文章 / 未归档（共203篇）

利用栈的结构O(1)动态查询当前最小值（双栈）

题目描述定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。思路：利用两个栈来进行操作，一个存正常的栈数据，另一个辅助栈存放当前最小值。入栈时：如果当前没有最小值或者加入的数字小于等于当前的最小值则更新辅助栈，即push新数据，否则不...

2019-07-20

0 612

统计一个数字中二进制位1的个数

题目详情：给一个二进制数，其中负数用补码表示，问其中二进制‘1’的个数。思路1：在计算机中，其实为了运算的方便，负数都是用二进制的补码表示，也就是说，我们对其进行位运算其内部加法器的实现都是先转化成补码（详见组成原理）。对于这题有以下几个思路：按位统计，也就是每次从二进制最右边通过与1...

2019-07-18

0 663

有序矩阵查询某值是否在阵中（搜索）

题目描述：在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。思路：由于是有序的，我们找个起点开始搜索，注意这个起点一定要能确定一个方向是递减一个是递增的，...

2019-07-17

0 409

求两个等长升序序列的中位数（二分）

题目：给两个长度均为N的升序序列，求两个序列的所有元素的中位数。定义一个长度为L的升序序列S，其 L / 2 ...

2019-07-13

0 929

查询区间恰好有2个的数字种类数

思路：离线做法：首先离散化数字arr，并按右端点处理询问，原理和处理区间种类数一样然后把1~n的相同的数字预处理一下，让每个相同的数字可以索引到它后面那个位置，也称为这个节点的后继，实际上就是按类构造静态链表之后预处理每个链表首部有后继的节点在表头位置+1 然后根据树状数组...

2019-07-12

0 412

查询区间中出现次数超过长度的一半的数字

思路：思路有很多，大致有这几种：强行在线统计每个数字的出现次数，由于不知道数字的规模，用键值树（hash_map、Tree_map）记录次数，复杂度 O ( ...

2019-07-09

0 444

计蒜之道2019 复赛 D、B、E（贪心+思维）

link D 思路：开始的想法是用邻接表存住每个字母的下标，由于扫描顺序的缘故字母的下标表必然有序，然后二分。复杂度是\(O(nlogn)\)。然后T一发...冥想了一会胡搞了一下又T了。算了一下规模差不多有15e7这样...后来改用单调栈维护一发过。其中单调栈中是维护一个字典序单调不减的序列。 ...

思维

2019-06-17

0 589

C++ Output Limit Exceed错误笔记

如果你发现你的代码和标程几乎无差，思路一致，但一直有Output Limit Exceed错误，以下有我的解决方案，但对于这个错误我也无法说出所以然，故记下这篇笔记在做模运算的时候，如果定义了long long（__INT64）a，b变量，但用了一个int对两个的乘积做模操作，在FZU2297上...

2019-05-16

0 550

HDU2795（线段树+单点更新+思维）

题目链接题目大意：给一个h高，w宽的广告牌，以及n条广告的宽度，每条广告的高度默认为1，问n条广告能插上的话所在的最高行数，插入不了输入-1. 解题思路：比较容易到用mlen维护区间h能够装下的最长广告的长度（未插入），n在2e5内，所以线段树最多就开8e5就足够了！之后单点更新的时候顺带返回...

2019-05-14

0 392

HDU1698（线段树+区间覆盖+lazytag）

题目大意：给n个数，初始化为1，每次输入一个区间端点以及数字k，把这个区间的数全设为k。最后查询整个区间的数字和。解题思路：线段树的裸题，区间更新区间查询，在打标记的时候直接赋值就行。关于延迟标记更新的时候如果发现某个区间在我们的更新区间之内，那么我们就把它的父节点更新完毕后，打个标记，表...

2019-05-09

0 686