已注销

数据结构

ACM模版篇(139) C++(4) CONTESTS(31) dfs && bfs(59) GitHub(1) Linux(4) OpenGL(2) PHP(5) Python(7) QT(3) Script(4) STL(24) 位运算(3) 其他(37) 动态规划(148) 区间(22) 图形打印(6) 图论(96) 字符串(39) 打表(13) 排序(31) 数学相关(153) 数论(101) 暴力解题(31) 机器学习(10) 栈(14) 树(51) 每周都有那么几天不想学习(2) 汇编(6) 知识点总结(17) 笔试试题(15) 网络流(7) 职场老油条(1) 计算几何(17) 贪心(62) 逐梦者(97) 郑州-大连(2) 问题残余(4) 骑行也是追梦(1)

/ 注册

全部文章 / 数据结构（共73篇）

51Nod-1215-数组的宽度

ACM模版描述题解在讨论区中，夹克老师讲得十分透彻了，我也不再做那么详细赘述了，大致的分析一下，根据夹克老师的说法，用单调栈分别求出来一个数作为最大值和最小值的贡献区间，也就是说求出这个数作为最大或者最小的值时能往前往后延伸的长度，最后根据乘法原则就能求出来每个数贡献的区间数目。 ...

2021-05-21

0 0

51Nod-1257-背包问题 V3

ACM模版描述题解典型的0-1分数规划，二分单位体积价值即可。 0-1分数规划属于较简单易学的算法，本以为背包问题 V3一定是一个更难的动态规划，谁知道只是一个二分。不懂0-1分数规划的可以看看参考一栏的 blog，其实很简单的，只要知道0-1分数规划，这个题可以算是5级题比较简单...

2021-05-21

0 389

EOJ-大学生程序设计邀请赛（华东师范大学）-G-铁路修复计划

ACM模版描述题解二分查找+最小生成树，简单题，就是需要注意两点，M 是 long long，RIGHT_MAX 需要设置为 100W，当设置为 1000 时 WA 了五组，设置成 10W 时 WA 了一组，设置成 100W 时成功 AC 了…… 代码 #include <...

2021-05-21

0 377

EOJ-大学生程序设计邀请赛（华东师范大学）-B-分词

ACM模版描述题解一看这个题，我第一感觉就是 dp，想着可能是 map + 区间 dp，但是发现数据太大，开不来二维 dp，有些手足无措，真情太少，套路太深，后来搞懂原来这个是字典树 + dp，但是不是简单的区间 dp，具体我也不知道这叫啥 dp，反正挺有趣的一个 dp，具体代码...

2021-05-21

0 719

EOJ-大学生程序设计邀请赛（华东师范大学）-D-实验室传染病

ACM模版描述题解单调栈搞搞，不断更新左右区间，直到无法更新为止，在 51Nod 上见过一道类似的问题，不过那道题只需要一遍（update() + update_()）即可解决，而这个问题涉及到两个更新函数可能会互相影响彼此，所以需要多次更新，直到无法更新为止。具体是哪道题我就记不大...

2021-05-21

0 462

HDU-5877-Weak Pair

ACM模版描述题解线段树或者树状数组都能搞，这里使用的是树状数组。首先我们将 ai 和 ⌊k/ai⌋ 统一保存然后排序去重，对应结点建立映射（结点权值在序列中的位置），接着，一遍 dfs() 不断加点删点，搜索过程中，进行求和计数。描述起来并不是特别容易理解，还是细细品味...

2021-05-21

0 363

51Nod-1574-排列转换

ACM模版描述题解这个题是 CF 的一个题，但不是原题，题目弱化了，数据强化了，一开始想着一个经典算法——使序列有序的最少交换次数，可是意志不坚定的我还是点开了评论区，发现这个要用贪心写，可是发现写来写去就是过不去，一直 TLE，后来用栈写（代码 One），需要右移的入栈，遇见左移的...

2021-05-21

0 360

图灵杯-第四届“图灵杯”NEUQ-ACM 程序设计竞赛-E-简单的RMQ

ACM模版描述题解经典的 RMQ 问题，也可以用线段树解，这个题在刘汝佳的白书上边讲有，原题~~~ 这里需要用到游程编码（RLE），然后将询问划分为三个部分就好了，过多的就不说了，可以翻翻白书，P198，讲得十分详细。代码 #include <iostream> ...

2021-05-21

0 386

51Nod-1394-差和问题

ACM模版描述题解快排 + 离散化 + 两个树状数组搞搞，分别用于表示数的个数与数的和，这里的核心是添加和删除过程中绝对值之和的变化，假如当前加入的数为 x，比 x 小的数有 cnt 个，总和为 sum，那么添加 x 的过程这一部分对绝对值之和的影响为 x∗cnt−sum ，对于比...

2021-05-21

0 317

51Nod-1461-稳定桌

ACM模版描述题解这个是 CF 上的原题改的，将 di 的数据放大了，所以不能普通的枚举代价了，而需要用数据结构优化处理，这里可以使用线段树搞搞事情，很意外。首先，我们对每种代价进行建树，然后从大到小对长度进行排序，接着遍历一遍，枚举桌腿高度，不断添加删除的边，因为所有高于当...

2021-05-21

0 315