已注销

区间

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) 图形打印(6) 图论(96) 字符串(39) 打表(13) 排序(31) 数学相关(153) 数据结构(73) 数论(101) 暴力解题(31) 机器学习(10) 栈(14) 树(51) 每周都有那么几天不想学习(2) 汇编(6) 知识点总结(17) 笔试试题(15) 网络流(7) 职场老油条(1) 计算几何(17) 贪心(62) 逐梦者(97) 郑州-大连(2) 问题残余(4) 骑行也是追梦(1)

/ 注册

全部文章 / 区间（共22篇）

51Nod－1285－山峰和分段

ACM模版描述题解这里需要强调的是，峰如果被分割，依然算峰，所以，首先需要对点数据进行峰数据检索，然后处理得到一个pre数组用来存储前i个点数据中有几个峰。当然，我们最多分的段数受峰个数控制。代码 #include <iostream> #include <c...

2021-05-21

0 305

51Nod－1402－最大值

ACM模版描述题解一开始看到这道题，感觉挺简单的，但是，我只关注了明沟，却忽略了暗坑！！！首先，这里我们将这些特殊点成为卡点，但是不是所有的卡点都能卡住数据的，其中，最容易想到的是t < x - 1的点是无法卡住数据的，所以我们可以直接忽略掉，那么剩下的卡点一定是可以卡住数...

2021-05-21

0 352

51Nod-1686-第K大区间

ACM模版描述题解十分有意思的二分，二分第k大的数是多少，设为mid，然后cala(mid)，只要计算出有多少个区间的众数的次数是>= mid的即可。使用尺取法+二分可以实现O(nlogn)复杂度的算法。这里有一个暗藏的坑，k <= n * (n - 1) / 2，说明区...

2021-05-21

0 524

51Nod-1521-一维战舰

ACM模版描述题解好长时间没有见过51更新4级以下的题了，今天多了一道从CF上抓来的题，很有趣，区间问题，对于我这种做题少的人来说是一种区间新题型。比较简单的是直接上STL的set，用二分搞搞（代码One）。但是这个耗时贼高，于是发现这道题不用set和二分也是完全可以的（代码Tw...

2021-05-21

0 233

51Nod-1712-区间求和

ACM模版描述题解做这道题明显感觉智商不够用，只能说略懂略懂……套路太深，数论有些差了/(ㄒoㄒ)/~~不是看了大牛们的详解我断然无法弄懂这道题。以下是官方题解：对于一段区间l~r，其中一个数x对答案的贡献为(2x-l-r)次。因此我们只要求出所有数对答案的贡献并累加起来...

2021-05-21

0 367

51Nod-1674-区间的价值 V2

ACM模版描述题解虽然是四级题，但是真不会，找了题解，甚是不错。以下题解来自abclzr的博客：对区间分治，统计[l, r]中经过mid的区间的答案。我的做法是从mid向右扫到r，统计出所有[mid, i], mid ≤ i ≤ r的and和or值。然后发现这些and...

2021-05-21

0 386

ZOJ-The 14th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple-D

ACM模版描述题解离散化找公共区间，然后对区间进行一定规则的累加就行了。具体规则就看翻译了，能翻译对，就 AC，翻译不对，就可以洗洗碎了……还好猜样例猜到了规则！哎，英语渣渣打比赛真是累~~~全靠猜！对了，这个题的数据有些迷，题目说好了 1≤x,y≤100 ，我开了 ...

2021-05-21

0 371

51Nod-1572-宝岛地图

ACM模版描述题解这个问题一开始我选择暴力，结果 TLE 了，然后各种优化，考虑到很多位置是重复判断的，所以我选择将所有可能会路过的相对坐标存在 set 中，结果依然是 TLE 了两组，虽然时间上快了很多，但是依然无法避免的超时了（代码 One）。然后，发现自己虽然在不断地优...

2021-05-21

0 532

蓝桥-ALGO-29-校门外的树

ACM模版描述题解区间合并问题。水题…… 代码 #include <iostream> #include <algorithm> #include <cstdio> using namespace std; const int MAXN =...

2021-05-21

0 357

51Nod-1564-区间的价值

ACM模版描述题解这个题很有意思，输入专门强调是随机生成的，所以不存在比较卡的数据，酱紫的话，也就是可以使用分治搞搞，当然这个方法不是最好的，但是是最简单的，在此基础上，还可以进行数据结构上的优化，使区间查询最值的过程更优，酱紫就会想起来线段树、树状数组、RMQ 之类的东西，可能用单...

2021-05-21

0 427