Xorex

DFS和BFS定义DFS关于DFS，他叫做深度优先搜索，简称DFS，就是一条道走到黑，只要这里能够搜索，那么就不停地往下搜，往下搜，一直搜到不能搜为止，然后不能搜了直接返回上一层，然后继续搜，一直搜到不能搜为止。但是书上一直说DFS如果地图类型数据量很大的话会系统堆栈溢出…… BFS关于BFS，他叫做广度优先搜索，简称BFS，就是一走走一圈，走完一圈走下一圈，是一层一层的走，如果DFS是一个知识点刨根问底型学习的话，BFS就是分区规划型学习，两种算法在不同的题目虽然都可以用到，但是效率却相差甚远,所以要去学习怎么搞算法…… 题目题目描述： 一矩形阵列由数字0到9组成,数字1到9代表细胞,细胞的定义为沿细胞数字上下左右还是细胞数字则为同一细胞,求给定矩形阵列的细胞个数 输入： 整数0<=m,n<=100(m行，n列)M行n列0到9的数字（中间没有空格） 输出： 细胞的个数 题解：这道题就需要搜索了，首先枚举点，找到一个细胞的一部分就开始染色，用BFS或者DFS染成0，这样就不会干扰到寻找其他细胞了！然后一旦找到细胞的一部分就把这个细胞染成0色，这样找到一个一部分就找到了 ...

综述 这几天做了几道特别神奇的题目，让我感受到了算法的真正高效！这几道题的思路就是使劲压，从三维压到二维，从二维到一维，一维再优化，然后就可以将算法的复杂度下降很多很多。具体看下面的题： 一维累加和题目描述： 给定N个数，求这N(1 <=N <= 100,000) 个数的某个连续子序列的累加和，保证这个连续子序列的累加和最大。 输入： 第一行：一个整数N。(1 <=N <= 100,000) 接下来N行，每行一个整数P_i(-1,000 <= P_i <= 1,000)。表示第i个数。 输出： 一个整数，表示子序列的最大连续累加和。 题解：这道题首先来说…… 单纯的进行一个个枚举然后加到一起最后排序是绝对不行的，因为复杂度是O(N*N*N)，所以说，我们需要进行优化。 因为一个序列是要不停地加下去的，如果前面的序列是正的，那么加到后面肯定变大，而如果是负数，那么还不如不加。于是我们就可以计算累加和，如果前面的累加和是整数，继续加下去，并和maxx（用来记录最大值）比较。如果累加和是负数，清零，然后重新加。最后比较出来的maxx一定就是最大值！ ...

寒假安排： 1.写完第二页的所有题目（约40题）2.学完搜索……3.写出来素数方阵。4.写出来虫食算。5.补一补以前留下来的坑（比如高精度） 每日过程：Jan/13今天下午去机房晚了一点，写了寒假安排（可能会调整），然后写了P1162是一道比较水的搜索题，枚举过了。表示对寒假很期待。 Jan/14今天上午写了等差数列，听老师和学姐讲了一些东西，下午有些难受，就先走了。 Jan/15上午开了USACO的铜组，A掉了三道题，但是第三题题意很难理解，可能是翻译的问题吧，get两个银组小号，晚上没有来机房，数学老师自习课占用了。 Jan/16感受到了银组的难度但是，我还是写出了第一题，然后发现，第一题最后一组超时……下午翘课来机房，然后写了第二题，写了搜索的两道题，学到了状态压缩P1173和P1174，算法效率很高，但是P1174不是太懂，因为要改USACO银组，就丢给明天了。于是我把枚举换成二分，AC. Jan/17早上三节课来机房，写了USACO银组第二题，略简单，需要空间换时间，入门篇里面的。下午到机房写了补了P1174的题，自己完全弄懂之后才A掉，真是不能相信书上的代码。然后一下午都 ...

堆/优先队列 我觉得堆和优先队列是我现在学习到的最神奇的东西了，比sort还要神奇！ 堆和优先队列是比较高级的数据结构，效率很高，O(logn)啊！堪比sort，但是实际上并没有sort快，但是也是很方便的。 然后就是使用的时候麻烦一点，需要输入一些不好记住的东西： 堆的定义priority_queue<int,vector<int>,greater(less)<int(double)> > ans(name); 然后就是头文件：#include<queue> 堆的使用然后就可以随心所欲的ans.push(a[i])进队，返回队列是否为空ans.empty()，删除第一个元素ans.pop()，返回元素个数ans.size()，返回优先值最高的东西ans.top()。 这就是堆的一些应用，用堆的排序效率并不是太高，仅仅只是一些特别的题目会用到，然后就是完全二叉树了！ 完全二叉树 上面的就是二叉树，分别是好用的满二叉树，一边倒的完全二叉树和体型奇异的非完全二叉树。 二叉树直接存储的时候，按照左儿子是自己坐标乘2，右儿子是乘2+1 。 就这 ...

声明关于栈和队列我已经在上两篇日志里面讲过了，但是在实际应用中，往往都是混用的，而且OJ上P1148这道题还超级麻烦，所以…… 看题： 题目描述： 对于一个由(,),[,]括号组成的字符串，求出其中最长的括号匹配字串。 具体来说，满足如下条件的字符串成为括号匹配的字符串： （1） (),[] 是括号匹配的字符串。 （2） 若A是括号匹配的串，则(A)或[A] 是括号匹配的字符串。 （3） 若A和B都是括号匹配的字符串，则A+B也是括号匹配的字符串。（这里的+是字符串的加法运算）。 例如：(),[],([]),()() 都是括号匹配的字符串，而][，[( ])，(]则不是。 字符串A的子串是指由A中连续若干个字符组成的字符串。例如：A,B,C,ABC,CAB,ABCCABC都是ABCABC的子串。空串是任何字符串的子串。 输入： 输入一行，为一个仅由()[]组成的非空字符串。(括号都是英文输入法的括号) 输出： 输出也仅有一行，为最长的括号匹配子串。若有相同长度的子串，输出位置靠前的子串。 题解：拿到这道题，然后我们的思路就是建立一个类似于栈的队列，输入一个后和队 ...

单调队列描述于队列，就是一个数组，不过需要用head（我习惯用top）和tail（我习惯用end）来维护的一个先进后出的队列（有时候出入不规则）。单调队列就是在整个队列中，所有元素都是单调递增或者单调递减的，因为需要维护整个队列为单调的，所以有时候需要在队头或者队尾都删除数。 单调队列和单调栈是相似的，但是最优解的范围不同，队列在乎全局P1157，栈在乎局部P1153. 题目P1157window题目描述： 给你一个长度为 N 的数组，一个长为 K 的滑动的窗体从最左移至最右端， 你只能见到窗口的K个数，每次窗体向右移动一位，如下表: 你的任务是找出窗口在各位置时的 max value,min value. 输入： -第 1 行 n,k,-第 2 行为长度为 n 的数组； 输出： 2 行 第 1 行每个位置的 min value, 第 2 行每个位置的 max value ； 题解：拿到这道题，最简单的方法，n-k个sort，也就是说(n-k)*nlogn 次计算，如果n大一点，绝对超时，那么为了有更快的办法，我们可以直接使用单调队列来解决这个问题。因为题目中有mi ...

栈的定义 栈（stack）又名堆栈，它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。 栈的应用 栈作为一种数据结构，是一种只能在一端进行插入和删除操作的特殊线性表。它按照先进后出的原则存储数据，先进入的数据被压入栈底，最后的数据在栈顶，需要读数据的时候从栈顶开始弹出数据（最后一个数据被第一个读出来）。栈具有记忆作用，对栈的插入与删除操作中，不需要改变栈底指针。 P1153乱头发节题目描述 李智宇的某 N 头奶牛 (1 <= N <= 80,000) 正在过乱头发节！由于每头牛都 意识到自己凌乱不堪的发型， 宁智贤希望统计出能够看到其他牛的头发的牛的数量。 每一头牛 i有一个高度 h[i] (1 <= h[i] <= 1,000,000,000)而且面向东方排成 一排(在我们的图中是向右)。因此，第i头牛可以看到她 ...

静态链表定义关于静态链表就是一个结构体，加上一个数组： 123456struct Card{ int sit; int next; int prev;};Card a[1000]; 静态链表原理之所以会用到静态链表是因为纯粹的一位数组太慢了，每次处理差不多都是On(n),一个二重循环大多数数据都会超时的，包括移动一个元素，删除，插入一个元素能能，动一个就要动全身，所以要使用静态链表； sit的具体含义是要分题目的，因为有些题中，要固定不变的量是不变的，有可能sit是一样需要移动的东西的编号，也有可能是一样东西的权值。next指的是这个东西下一个元素是哪一个，prev指的是上一个元素是哪一个，这样进行操作的时候就可以将为On(1)了。eg:删除编号为15的元素 1a[a[15].prev].next=a[15].next 这样我们只要让他的上一个元素所指向的下一个元素，为自己指向的下一个元素即可，然后就永远不会出现有个编号为15的元素了，因为其他没有任何一个元素的next是他，也就不可能访问到他了。 P1145作弊的发牌者题目描述 ...

分治算法分治总结不知不觉得竟让A完了第二页的二分，然后来写写总结。 关于二分，其实老师很久很久以前就已经讲过了，当时很不理解，但是现在是好多了，分治算法就是分而治之，将一个很大的问题逐步分解为一个一个小的问题，然后最总得到答案。 分治过程通过一个while循环，判断是否找到了答案，一般都是：while(left+1<right)**，也就是说，一般退出循环之后，答案就已经出来了，因为一般二分查找留下来的答案都是在left和right之间，如果left紧挨着right，那么我们是不就可以仅仅通过一个判断就得到正确答案了呢。然后就是while循环里面的内容，首先建立一个mid=(left+right)/2，作为需要查找的中间值，然后计算出mid的结果，如果结果偏大，就在left和mid之间从新再找，也就是right=mid，反之是left=mid，然后进入新一轮的查找，每次查找都会缩小一半**的范围，因此二分效率要比一个一个枚举快很多。 答案判断至于判断什么的，就因题目而论了。 题目题解P1137 小车问题题目描述 甲、乙两人同时从A地出发要尽快同时赶到B地。出发时A地有一辆小车，可 ...

NOIP2016!总的来说，这次NOIP已经结束了，成绩也不尽人意原因又很多，但是最主要还是自身的原因。 比赛概况这次联赛普遍比较难，自己之所以考的很烂最主要的原因就是该拿到的分数没有拿到，两个T1都写挂了。 Day1-T1第一题TOY是因为判断错误，一个 “ = ” 的问题，结果一个简单的模拟题只拿到了10分，修改了判断之后就能AC了（NOIP的水数据），但是在OJ上还需要对读入进行处理一下，因为到后面4组数据用string来读入人名是会超时的，需要用到字符数组。 Day2-T1重点是第二题，第二题需要的递推公式我是已经想出来的，而且实现的也很好，失败就失败在了后面的优化上，也就是空间换时间上面。为了不超时，我使用了一个一维数组来存入每一排前面所有的答案，但是忽略的题意，没有注意到枚举的范围，所以导致后面一片WA，我删除了优化之后，OJ上拿到了80分，是很有可能AC掉NOIP的水数据的，但是自己画蛇添足，自作自受。 Day1-T2&&Day2-T2然后就是两个第二题，分别都拿到了一些步骤分，30分和20分（好像），按照这样，不算Day2 T1自己真的有可能想不出来的优 ...