yizimi远欣

分类

其他(14) 算法及模板(3) 课内(2) 题解(39)

/ 注册

全部文章（共14篇）

题解 P1886 【滑动窗口】

线段树优化做法牛客网上应该会MLE，洛谷上可以过如果仔细读过题的话，就会发现这是一个静态的区间查询最大值与最小值。很多人（如果你学过线段树的话）就会想到，我当年学线段树的例题不就是区间加，然后求区间最大值吗？何况还没有区间加这一操作，岂不嗨皮哉？？？好的，看看数据范围...

线段树

2018-12-02

0 385

题解 P1339 【[USACO09OCT]热浪Heat Wave】——线段树做法

Dijkstra + 线段树解法最近集训一位大佬给我讲了一个奇妙的Dijkstra优化方法，他告诉我线段树可以代替优先队列来优化Dijkstra。我第一个感觉是眼睛一亮于是我认真的听完了他讲的方法。 Dijkstra算法周围的大佬已经讲的十分的漂亮了，我觉得我再插一嘴就...

Dijkstra 最短路线段树

2018-12-02

0 380

题解 P1047 【校门外的树】

此题解分两部分，请选手对号入座 1.普及组初学者我们可以通过for循环来实现操作，用一个数组来记录是否有树。当修改时，嵌套一个for循环可以把这一部分标记下。代码如下： #include <iostream> using namespace std; int ma...

模拟线段树

2018-12-02

0 467

题解 P2486 【[SDOI2011]染色】

主要思路：树链剖分 + 线段树一看就知道是棵树，可以通过树链剖分后维护。颜色就相当于点权，强烈暗示树链剖分。所以重点就落在了如何维护区间颜色块数？ 1 1 2 2 3 3 3 2 我们可以这样考虑：我们考虑小区间与小区间是不是可以合并。如： 1 1 2...

树链剖分线段树

2018-12-02

0 451

题解 P2574 【XOR的艺术】

主要思路：线段树线段树大法好我觉得这道题就是把区间修改，区间查询的普通线段树改了改懒标记就完了不会线段树？不着急啊，我们有入门宝典—— 具体线段树入门：入门1：单点修改，区间查询入门2：懒标记及区间修改 Blog发完就跑记得，这里的xor如...

线段树

2018-12-02

0 522

<span>题解 P3374 【【模板】树状数组 1】</span>

主要思路：zkw线段树最简单的zkw线段树就十分适合这道题，为什么用zkw线段树，可以看一下以下精简代码：我们只需要用到单点修改，区间查询就好了。 #include<cstdio> #define go(i,j,n,k) for(int i=j;i<=n;i+=k...

zkw线段树线段树

2018-12-02

0 527

题解 P2073 【送花】

毒瘤题目主要思路：线段树（权值线段树）可能很多同学做题之前会看一下题目标签。这题的题目标签就是线段树与平衡树，然而写不出来以后，一看题解里全是STL，一脸茫然，，，我这里是一篇正了八经的线段树解法。首先我们要看清题： 1.操作的编号一定不能看倒，不能理所当然...

线段树

2018-12-02

0 481

题解 T50424 【lqyz10.11选拔赛 T3 婆罗门的城市斗鸡】

题目描述在一个城市的一条窄到只有长度没有宽度的道路上有 N只婆罗门的斗鸡在不同斗鸡点的上，对一个城市定义该城市的斗鸡爱好度为：这n × (n − 1)个距离的总和。每只婆罗门的斗鸡都计算到其它各只婆罗门的斗鸡的距离。但是婆罗门数学太差，所以他要让你帮他求城市斗鸡爱好度。 ...

线段树

2018-12-02

0 357

题解 P1966 【火柴排队】

题目描述涵涵有两盒火柴，每盒装有 n 根火柴，每根火柴都有一个高度。现在将每盒中的火柴各自排成一列，同一列火柴的高度互不相同，两列火柴之间的距离定义为： Σ(\(a_i\) - \(b_i\))² 其中a_i表示第一列火柴中第 i 个火柴的高度，b_i表示第二列火柴中第 i 个火...

线段树权值线段树

2018-12-02

0 708

题解 POJ1151【Atlantis】

题目大意给你n个矩形，让你求所有矩形覆盖的总面积，重叠的地方只算一次输入格式输入的第一行包含一个整数n，表示可得到的地图数目。以下n行，每行描述一张地图。每行包含4个整数x1,y1,x2和y2（0≤x1＜x2≤30000,0≤y1＜y2≤30000）。数值（x1,y1...

线段树扫描线

2018-12-02

0 510