csdn_Coder_T-CSDN博客

原创 2017/10/15训练心得

这两天一直在尽可能的作杭电的线段树和树状数组专题，但是到现在为止还有6、7道没有做，怪自己国庆没有做太多的题目，也怪自己的代码实现能力太差，有些有思路的题完全做出来也需要很多的时间，一些复杂的题目更是需要看着题解写，按照之前队里的约定，我得离队了，回想起前天和队友一起到网吧刷野想要尽可能的做完题目，有些小遗憾，但我不会放弃，以后有机会我会再回来的。

2017-10-15 22:33:26 226

原创 POJ4638

题意：给定n个数的序列，进行m次查询，求查询区间里的连续数段的个数例：（1,3,5,4,2）查询区间[2,4]的连续序列个数为1 题解：利用树状数组来维护区间，其sum()函数求的值为从1位置到pos[v[i]]位置的连续序列的段数，每一个数组元素的值是表示v[i]这个数插入进树后对总的连续序列的个数的影响。在将位置为pos[v[i]]的数插入到树中时，和前面插入的数进行判断，如果前面

2017-10-15 22:31:49 199

原创 POJ1990

题意：FJ有n头牛，排在一条直线上（保证坐标不出现重复），另外每头牛还有一个自己的声音，如果i和j牛之间进行沟通，则需要两头牛的声音最低为max(vi,vj)，消耗的体力为max(vi,vj)*(两头牛之间的距离)，求所有牛进行沟通现消耗的体力思路：建立两个树状数组维护坐标值小于等于x的牛有几条和坐标值小于等于x的牛的坐标和。先对v进行排序，按照顺序从小到大将声音为v的牛的信息插入到两个树状数

2017-10-15 22:31:13 337

又到了写心得的时候，这个周空余时间看了很多大牛对于线段树和树状数组的讲解视频，知识点还是那些知识点，没有太多过于新鲜的东西，尽管讲起来没有太多可以学习的东西，有些大牛说话甚至都听不清楚，但让让我比较吃惊的是大牛们的敲代码的速度是真的快啊，代码的生成速度和我的思维的速度差不多，又一次意识到了差距。接触一段时间的ACM，意识到刷题对于我们来说还是很重要的，ACM需要保持状态，毕竟是思维方面的东西，几天

2017-10-12 21:34:25 231

原创线段树扫描线总结

通过扫描线求一个由多个图形构成的图形的面积，就是用一条拟定出的线不断的划分每一个小矩形的面积，这一点并不难理解，之前困扰我的是如何用代码实现：因为同一个高度上的小矩形可能是不连续的多个，而且小矩形的低可能是double类型的数据，这两个地方比较困扰我。最开始的用扫描线的方法来求面积，又要用上线段树的知识，我觉得二维线段树能够处理，但是二维线段树处理起来更加复杂，后来在网上看到了一维

2017-10-08 17:55:14 565

原创线段树

二维线段树模板#include #include #include #includeusing namespace std;const int N=;int tree[N][N//建立y轴方向上的线段树，作为一维线段树的一个节点void Build_2(int node,int left,intright,int deep){ tree[dee

2017-10-08 17:49:38 271

原创 17年国庆小长假训练心得

国庆小长假结束，总结一下假期的学的东西，重点还是线段树和树状数组的内容，对线段树的二维转一维有更深的理解，主要看了扫描线这一类问题，因为之前一直没有看懂，虽然原理并不难，但真是代码实现起来之前也搞不太清楚。由于回老家的原因耽误几天时间，坐了很长时间的火车，在车上也看了随机算法和一些博弈论的内容（如巴什博奕、斐波那契博弈等），算是简单的了解了一下，以后有时间再进一步学习。期间做了一次CodeFo

2017-10-08 17:46:35 297

原创 HDU2795 Billboard题解

问题不难，简单的线段树模板题，但是有两个地方值得学习一个是有height和n中小的那个值进行建树，在不影响题意的前提下节省了空间内存二是在写函数的时候不能指望一个函数解决太多事情，就Update()来说，开始我是把不能存放的情况也加进去，后来出现WA，将函数简化后，把不能放的情况拿出来，简化了代码的复杂程度，也成功AC程序源代码：#include#include#i

2017-09-28 21:25:28 261

原创线段树基础

平衡二叉树是完全二叉树，算法复杂度为O(logn)级别，建树用二分法找到左右两个子节点，直到不能继续划分节点，线段树主要用于处理一段连续区间的插入、查找、统计、查询等操作，线段树的运行时间主要是1、对于任意两个节点的区间，要么完全包含，要么互不相交2、任意线段[a,b]在线段树的查询或查找过程中把线段最多分成log(b-a)份线段树模板void Build(int node,int

2017-09-28 19:19:50 132

原创 2017/9/24

6场网络赛打完了，每次只能出一道或两道题目，看到了现在和其他队伍的差距，还需要更多的学习和练题，希望以后能达到自己想达到的目标

2017-09-24 20:18:17 194

原创 2017/9/21

看了一个星期的题目，只是做题比以前多一些思路，像是二维转一维、离线等方法，但是对线段树却没有新的心得

2017-09-22 00:19:22 166

原创 2017/9/14

课余时间看了看《挑战程序设计》这本书，对于线段树和树状数组的地方做出一定总结，其实现在看题目对于知识点的理解帮助更大，但我想再把知识点确定一下，之后总结题目，望老师理解线段树是擅长处理区间的，树上的每个节点都维护一个区域，根维护的是整个区域，每个节点维护的是父亲的区间二等分后的其中一个子区间。常用于维护的数据有最大值、最小值、区间元素个数等，线段树最底层的元素一定是划分到不能再分的元素

2017-09-14 21:57:27 238

原创 2017/9/10

通过今天和昨天的网络赛发现题目还是有一定的思路的，但是用代码实现起来就会速度会比较慢，而且这一点在日常的java的编程中也有体现，想了原因，我个人认为是由于接触计算机的时间较晚，对于敲键盘的手速还不够快，编程序的时候还需要看着键盘敲，以及对于思路需要反复思考其正确性导致变成编程速度缓慢，这一点还是需要在日常的训练学习中不断强化，至于手速的问题估计也只有通过不断地敲代码的提速了。在比赛中主要的问题还

2017-09-10 22:08:32 187

原创 2017/9/7

首先感慨一下时间过得很快，转眼已经是开学的第三篇博客了，在这一个半星期的时间里基本是只有在看线段树的相关内容，线段树以及树状数组在实际应用中的难处在于不容易想到用线段树或树状数组解决问题，经过近期的看题总结了一些线段树的常用用法，struct定义节点类型，其中一般包括区间值和维护的值，维护的值通常可以是该区间的区间长度、该区间的一些数值，常用操作包括Build()、Query()、Update()

2017-09-07 21:52:12 204

原创 2017/9/3

个星期的训练让我对线段树的运用有了更深一些的理解，用来维护区间值，其实对线段树有一定了解后会发现用线段树解决问题也并不算难，因为解题的步骤和程序都有一定的相似之处，包括Build()函数建立区间，用Updat()函数不断的对叶子结点的值进行更新，而叶子节点的类型常常被定义为struct类型，所以对于线段树问题的解决重点是寻找区间维护值，由于近期班级工作比较多，没有拿出很多时间来好好学习ACM，所以

2017-09-04 01:06:09 181

原创 2017/8/31

开学虽然还没有几天时间，但是能够明显感受到课程的难度有了提升，空闲时间总是先写完作业就将时间投入到acm的训练中，不能像暑假里系统地训练是肯定的，但是对于acm的学习也不可能用零碎的时间来做，毕竟零零碎碎的时间可能很难想明白一道题目甚至是一个知识点，所以在需要在acm的学习时间需要固定的一段时间里，也有助于思维的不断深入。就这半个星期的学习结果来看还是挺不错的，对于一些逻辑结构的理解更加的清晰

2017-08-31 21:34:09 178

原创 2017/8/25

一个月的集训就要结束了，只是觉得时间过得太快，仿佛不久之前才开始第一趟ACM课。在这一个月是时间里，非常感谢老师和同学的帮助，因为当时的ACM选修课我没有选，后来去蹭课又是在选修课已经开了两周的情况下才去听，所以那时候感觉自己好像一直比其他人差不少，其实现在看看，那个时候学的东西也并没有在后来的解题过程中占据举足轻重的地位，但是自信心的打击留下的后遗症还是多少存在的。来到集训可以说

2017-08-25 19:35:54 229

原创 2017/8/24

Bad Hair Day题意：给出从左到右的牛的高度，每头牛可以在不被挡住视线的情况下看到右边的牛，求所有牛能够看到的右边的牛的数量和。解题思路：构建一个递减的单调栈，每次插入一头牛的数据时，将前面小于它的高度的数据删除，每清除之前小的数据之后插入新的数据之前用sum求一次累加和，其表达的含义是在准备插入的牛之前有多少比自己高的牛，这些牛能够看到要插入的牛所以将其数量加上。当再出现一头更高

2017-08-24 21:31:27 187

原创 2017/8/23

树状数组和线段树的题目解起来没有想象中来的简单，一个题目往往在知道了题意以后不能很快有思路，需要在纸上进一步件问题转化后才能有所思路。总结这几天对树状数组和线段树的学习我发现，树这种数据结构在使用起来需要很强的逻辑性，这一点和在学习动态规划时有相同的感受，因为大部分情况都是用数组（或者一维或者二维）来表示树的结构，其意义都是人赋予的逻辑含义，单单就数组本身并没有特定的含义，我们在自己赋予的含义

2017-08-23 20:15:46 199

原创线段树和树状数组的认识与总结

线段树（Segment Tree）和树状数组（Binary Indexed Tree）具有相似是结构特点，都是以二叉树作为基础进行数据运算，都是擅长处理区间上的数，不同的是线段树的每个节点维护的是对应区间的最小值，所以善于处理区间上的最小值，而树状数组的节点维护的是对应区间的数的和，所以更善于处理区间和。线段树的主要操作为2种：1、给定s和t，求其区间上的最小值；2、给定i和x，把ai的值改成

2017-08-21 20:50:41 1209

原创运用BIT处理冒泡排序的交换次数问题

题意：给定一个1~n的排列a0,a1,a2,.....,a(n-1)，求对这个数列进行冒泡排序所需要的交换次数。在数据较大时，用常规的双重for循环来求解交换次数就会因为复杂度太高而存在TLE的情况，所以可以利用树状数组善于查询两个数之间的数字和的优势进行解题。首相树状数组的基本操作就是BIT的求和以及BIT的值的更新，那么如何要在没有if语句比较的情况下进行前后数值大小的比较进而求

2017-08-21 20:13:11 1609 1

原创基于POJ2991Crane问题对线段树的理解

题意：有一台起重机。我们把起重机看成由N条线段依次首尾相接而成。第i条线段的长度是Li。最开始，所有的线段都笔直连接，指向上方。有C条操纵起重机的指令。指令i给出两个整数Si和Ai，效果是使线段Si和S(i+1)之间的角度变成Ai度。其中角度指的是线段Si开始逆时针旋转到S(i+1)所经过的角度，最开始时所有的角度都是180度。按顺序执行这C条指令，在每条指令执行后，输出起重机的前端(第N

2017-08-18 22:03:04 291

原创最短路问题及路径回归

最短路问题：给定两个顶点，在以这两个点为起点和终点的路径中求最小路径或最小步数问题。单源最短路问题就是固定一个起点，求它到其他所有点的虽短路的问题。重点也固定的点叫做两点之间最短路问题。但是解决单源最短路问题的复杂度也是一样的，因此通常作为单源最短路问题来解决。单源最短路径1(Bellman-Ford算法)：d[i]=min{d[j]+(从j到i的边的权值)|e =(j,i) E}

2017-08-17 21:53:26 395

原创邻接矩阵邻接表

邻接矩阵：使用|V|*|V|的二维数组来表示图，g[i][j]表示顶点i和顶点j的关系。在无向图中可以用1和0表示两顶点之间的边是否存在。在有向图中用同样的方法表示连接，需要注意的是因为有向图中表示方向，所以中不满足g[i][j]==g[j][i]。在带权图中，g[i][j]表示顶点i到顶点j的边的权值，边不存在是常将其设为较大的常数INF来表示两点之间没有连接，这样定义的目的是为了和

2017-08-17 21:50:20 505

原创穷竭搜索

递归函数：在一个函数中再次调用该函数自身的行为叫做递归。其必须存在函数的停止条件。栈(stack)：支持push和pop两种操作的数据结构。push是在栈顶端放入一组数据的操作。pop是从其顶端取出一组数据的操作。后进先出(LIFO)结构队列(queue)：同样支持push、pop两个操作，但pop是取出最低端元素的操作。先进先出(FIFO)结构穷竭搜索：深度优先搜索(DFS)：从

2017-08-16 17:36:42 266

原创算法复杂度总结

算法复杂度总结：复杂度：一般分为时间复杂度和空间复杂度。算法花费时间与算法中语句的执行次数成正比，一个算法的执行次数称为时间频度(T(n))时间复杂度：T(n)(时间频度)/f(n)(辅助函数)在n->无穷时的值为一个不等于0的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，称O(f(n))为算法是(渐进)时间复杂度。即为最高阶的n 的函数，T(n)=n^

2017-08-15 21:16:44 453

原创 2017/7/31

这一周的训练题目主要围绕搜索，通过一天的复习和题目训练，对两种搜索方式有如下总结：广度优先搜索依靠队列实现，在队列尾部放置元素，在队首取出元素，在函数体中通过循环列举下一步中可能的元素并加入队列深度优先搜索依靠栈实现，在栈尾放置元素和取出元素，通过在函数中定义所有可能来实现算法，靠回溯、剪枝简化算法两种搜索方法根本上都可以分别通过队列和栈的原理

2017-07-31 22:16:49 211

原创递归函数理解

后来又在网上搜了写递归函数的资料，说的是当函数直接调用自己时就发生了递归。因为递归在生活中并不直观，不是很符合日常的思维模式，我们的日常思维模式是一步接一步的，所以我们更容易接受迭代这个概念。最初开始学习递归时，我总是被困在不停的回溯，不停按照迭代思路摸索递归过程，后来在网上看了一些博文，其实递归并不需要这样验证，递归的重点是找到递归关系与递归的终止条件，将大问题不断地转化成小的问题，在达到终

2017-04-15 13:10:21 205

CSDN_Coder_T的博客