yizimi远欣

题解

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

/ 注册

全部文章 / 题解（共39篇）

题解 CF475B 【Strongly Connected City】

这道题思路有三种： 1. 我们看到 2 <= n, m <= 20 数据范围不是很大，交点大约400，可以试着每个点dfs一次，然后找是否有一次都能到达其他点 2. 有些大佬会说：这不就是强联通分量水题吗？所以可以用Tarjan来求 3...

模拟强连通分量

2018-12-02

0 348

题解 P2073 【送花】

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

线段树

2018-12-02

0 481

题解 P3372 【【模板】线段树 1】

线段树模板题所以，我偏不用线段树奇了怪了主要思路：平衡树——Splay Splay是可以很好的维护区间的。我这里主要讲如何用Splay维护区间。我们知道Splay是严格按照中序遍历的顺序的，用rotate操作并不会改变这种性质，所以我们我们可以考虑一下一...

平衡树 Splay

2018-12-02

0 336

<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

题解 P2296 【寻找道路】

主要思路：DFS + Dijkstra + 堆优化 + 反向思维要不是写代码的时间问题我就用线段树优化了首先，题目要求是路径上的所有点的出边所指向的点都直接或间接与终点连通。我们可以先不考虑如何通过某点到达终点，我们想象如果通过一个点可以再到达终点，说明把边反过来后，终点可以...

Dijkstra 最短路

2018-12-02

0 445

题解 P1736 【创意吃鱼法】

主要思路：二维DP + 二维前缀和我就讲讲我当时做这道题的想法就好了。如果你只拿了部分分，可以看看修改和优化方法。一开始我没看清题，一看，，，这不就是求最长的对角线吗（当时我还只以为是左上右下方向的对角线），，，好求啊，，，简单的dp就好啦当这个点有鱼时（a[i][j] ==...

DP

2018-12-02

0 493

题解 P2574 【XOR的艺术】

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

线段树

2018-12-02

0 522

题解 P2486 【[SDOI2011]染色】

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

树链剖分线段树

2018-12-02

0 451

题解 P1047 【校门外的树】

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

模拟线段树

2018-12-02

0 467

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

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

Dijkstra 最短路线段树

2018-12-02

0 380