已注销

数据结构

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-1467-旋转绳

ACM模版描述题解这个题倒是不难，主要就是二分，并不像平时做的那种海量查询的问题那样，需要预处理优化、线段树优化之类的。一开始看到数据这么大，访问次数这么多，就感觉是需要预处理的，可是想半天也没有想到怎么处理，后来发现是二分，感觉很出乎意料，二分竟然能过，写好后提交了两次超时...

2021-05-21

0 361

51Nod-1711-平均数

ACM模版描述题解二分答案，数据结构用树状数组比较好，期间需要离散化一下下。这里给了 4s 时限，有些多了，应该是需要注意一下输入优化的。这里我们先求一下前缀和 sum[] 和最大值 mx ，然后二分，核心是 check() ，需要用到树状数组 + 离散化。至于树...

2021-05-21

0 396

51Nod-1525-重组公司

ACM模版描述题解典型的并查集问题，由于需要区间更新，所以这里要维护一个 pre[] 数组，表示当前记录点与在它前边且最靠近它的不同部门的点。代码十分容易理解，就不再赘述了。代码 #include <iostream> #include <cstdio...

2021-05-21

0 265

51Nod-1681-公共祖先

ACM模版描述题解第一次接触主席树，感觉好叼好叼，无法驾驭它啊~~~ 贴一下官方题解吧：貌似，这里用树状数组维护也是可以的啊……当然，我并不会。水平太臭了！代码 #include <cstdio> #include <algorithm> #i...

2021-05-21

0 269

SHU-“盛大游戏杯”第15届上海大学程序设计联赛夏季赛暨上海高校金马五校赛-K-购买装备

ACM模版描述题解比较基础的二分+贪心，如果这里要保证的不是最多件装备而是装备价值（不是属性）最大的话，就是二分+背包，因为这里实际上默认的是装备的价值为单位一罢了，大大降低了难度。比较水~~~ 代码 #include <cstdio> #include <cs...

2021-05-21

0 435

51Nod-1589-移数博弈

ACM模版描述题解这个题的解法真是奇思妙想，一开始只是知道单调栈搞不定，至于为什么，因为话题这里写得不是单调栈啊……当然也不是特别理解为什么要用链表，看了题解后恍然大悟。对于这种题，尽管用的数据结构变了，但是不变的是逐个求贡献，那么这个题我们需要根据什么求贡献呢？我们可以求出对于...

2021-05-21

0 0

51Nod-1485-字母排序

ACM模版描述题解一开始看到讨论区有人说，将排序部分改成 O(n) 就行了，然后我就傻傻的以为，计数排序搞一下就行了，然后，果然，无情 TLE 了四五组数据，后来知道了这个可以用线段树写，建 26 棵线段树，分别维护每种字母在不同区间的出现次数（计数部分），试了试，依然挂...

2021-05-21

0 355

51Nod-1533-一堆的堆

ACM模版描述题解离线处理，先将数据离散化，也就是根据 a 排序即可。因为要维护 k 叉最小堆，所以我们需要从小到大进行处理，加入树状数组中，先一遍循环访问这些结点的孩子所在区间有多少不合法，然后再将这些结点插入，以此而往，这里需要强调的是，这些指的不是所...

2021-05-21

0 311

HDU-2017 多校训练赛3-1003-Kanade’s sum

ACM模版描述题解我的意中人是个盖世英雄，有一天他会踩着七色的云彩来娶我，我猜中了开头，可是我猜不着这结局…… 这个题我也是猜中了开头，却没有猜中结尾…… 首先，很明显的一个条件是，人家要求所有子区间的第 k 大的值的和，那么，很明显我们不能求所有子区间，我们必须求每个值的贡...

2021-05-21

0 333

HDU-2017 多校训练赛3-1004-Kanade's trio

ACM模版描述题解这个题思路十分巧妙，没想到竟然可以用字母树解。题解不难理解，就是有些出人意料了。看了题解后，我拿着官方题解，参考着写了一份，习惯性的将一些东西改成了自己的习惯……比如说，初始化能用 memset() 的都用 memset() ，然后我就超时了……，很纳...

2021-05-21

0 316