Xorex

写在前面 Dijkstra的堆优化真的是不好写，首先图里面一直犯的错误又来了，访问其他点直接上邻接表的下标i，求如何提高智商？在线等，急！ 以后所有的题目都无脑Dijkstra了，SPFA会被不良出题老师卡掉，Dijkstra需要记住一个东西，在堆里面的比较方式是相反的！greater是小根堆，“ < ”是大根堆比较，“ > ”是小根堆比较。被坑了，不过还好长了长记性…… Dijkstra的堆优化首先需要开一个结构体，然后定义比较方式，然后将初始点加入堆中，然后使用while循环，结束循环的条件就是当堆里面为空的时候。读堆顶，出堆，判断这个堆顶元素是否以前出过堆，如果出过就continue把，没出过就标记为出过。然后利用这个堆顶去更新和他相连的所有点，将没有出过堆的元素的加入堆中。不断的重复上面的过程直到退出。 大致过程就是这样，主要要使用邻接表，不然就是负优化的说，而且一个元素是会多次进堆的（因为大小被修改了QAQ），所以如果能直接修改堆中元素的值相比速度会提高很多，以后敲代码，如果是稠密图并且时间够，就直接上Dijkstra+堆优化，如果是稀疏图，时间不是太多，直接S ...

前言： 由于开始做一道DP题需要树形DP的知识点，于是就去学树形DP，但是学树形DP的时候需要用到树的知识点，然后就去学树，学树的重建的时候发现自己不会三种遍历，然后就去学三种遍历QAQ，然后花了一个上午看懂了……（果然没人讲效率低啊QAQ） 二叉树遍历前序遍历：1234567void First_traversal(int p){ if(p==0) return; cout<<a[i].now; First_traversal(a[i].leftchild); First_traversal(a[i].rightchild);} 中序遍历：1234567void Second_traversal(int p){ if(p==0) return; First_traversal(a[i].leftchild); cout<<a[i].now; First_traversal(a[i].rightchild);} 后序遍历：1234567void Third_traver ...

轻院ACM这个轻院的ACM啊，真的是一颗赛艇啊，算是长了不少经验的说，包括和其他队友一起配合，一起解题，都是很不错的经历。 然后最后感觉在这场比赛中，最重要的就是几个人在配合方面，因为三个人一台电脑，所以说比较麻烦，有时候自己的程序不能占着电脑Debug，这就是考验代码能力的时候到了，我觉得ACM这种赛制还是非常人情化的，没有OI那么残酷，OI是一点失误就GG了，但是ACM却可以多次提交，不过是题量多一点，时间长一点，而且可以几个人一起讨论，结合其他人的长处一起配合，效率很高。 这次A掉了3道题，算是中游吧，尽快提高自己的能力吧，明年组团去的时候，希望能拿到一（wu）等（bai）奖（kuai）吧。（突然感觉有些不现实，毕竟自己一直这么弱啊……） 现在最重要的还是OI，提高自己的能力，加油！

说在前面 今天写的这道题怕是我目前见过最神奇的东西，比当初见到Floyd还要神奇的东西，这个斜率优化啊，和DP里面一些普通的斜率优化简直强到了离谱好吧，我来总结一下。 P1660最佳牛栏题目描述： 农场主 John (简称 FJ) 的农场有一长排的 N (1 <= N <= 100,000)块地组成. 每块地有一定数量 (ncows) 的牛, 1 <= ncows <=2000. FJ 想修建环绕邻接的一组地块的栅栏, 以最大化这组地块中平均每块地中牛的个数. 这组地块必须包含至少 F (1 <= F <= N) 块地, F 作为输入给出. 给定约束, 计算出栅栏的布置情况以最大化平均数. 输入： 行 1: 空格分隔的两个整数, N 和 F. 行 2..N+1: 每行包含一个整数, 一块地中的牛数. 行 2 给出地块 1 中的牛数, 行 3 给出地块 2 中的牛数. 输出： 行 1: 一个整数, 它是最大平均数的 1000 倍. 不要用舍入求整, 仅仅输出整数 1000*ncows/nfields. 题解：这道题不是一道DP，没有状态转移方程 ...

写在前面： 在做斜率优化的题目的时候，一定要记得，在编译之前看一遍整个代码，看看公式推得正确不正确，验证一下函数返回的值是否正确，然后顺一遍思路。不然你会Debug很惨很惨…… 总结一下在写斜率优化的时候犯下的错误： head++写成了head– 在进行计算斜率的时候应该是写Queue[head]/Queue[tail]结果写成了head/tail tail–写成了tail++ 更新队尾的时候应该让tail和tail-1比而不是tail和tail+1比 用前缀和后缀和进行运算的时候要-而不是+（可恶啊！！！） 斜率优化在我看来是比较玄学的一种优化，和单调性优化相似，都是需要将方程进行变形，变形之后寻找一种斜率关系，然后通过斜率的大小来比较最优值（有可能方程变形的时候是由正着的然后优化的时候必须变成倒着推才能将方程变形成一种斜率关系，大概是找方程中元素越少越好QAQ 其实需要将方程变形成一种关系,也就是只有以下是含有变量j的 因为比较抽象，所以说还是结合着题目进行学习吧 优化决策然后大力总结一发，我们首先将状态转移方程化为能写成与变量有关和与变量无关的两部分，然后对于决策x ...

写在前面 其实是动态规划深入讨论的一部分，但是由于内容比较多，所以拆开了。虽然动态规划的复杂度相对于搜索算法来说，已经很优秀了，是搜索算法的一种很强大的优化，但是DP在原来的基础上还是可以继续进行优化的，这其中一种方法就是利用单调性进行优化，适用范围还是挺广的。 单调性的优化其实就是利用你所列出来的状态转移方程中，进行变形，留下来真正的变量，剩下的已经确定的东西我们就可以不用去管了，只需要在真正的变量里面用低上一个维度或者低上更多的时间来得到这个变量的最优值，这种优化就是一种利用数学方面的DP优化。 其次就是DP类型的离散化类型的优化，我们只利用自己需要的值，对于一个维度特别大，达到远大于其他因素的时候，一般都是可以进行离散化优化的……学校的OJ里面大概有两三道题是比较好的，拉出来吧…… DP单调性优化P1326超级教主题目描述： LHX教主很能跳，因为Orz他的人太多了。教主跳需要消耗能量，每跳1米就会消耗1点能量，如果教主有很多能量就能跳很高。教主为了收集能量，来到了一个神秘的地方，这个地方凡人是进不来的。在这里，教主的正上方每100米处就有一个能量球（也就是这些能量球位于海拔1 ...

写在前面：一天前： 两天啃完吧，重要的是真正学会这个知识点，特意放慢脚步……前两天一天一个小专题真是搞得太紧张，好多都没有弄太懂QAQ 一天后： QAQ说好的两天的，结果一天都搞完了，mmp，可能是题目比较水的原因吧，大多都是自己认真想出来的，有时候对于题目的理解不太对，导致自己一直想不对，比如P1295创意吃鱼，我这语文理解能力啊QAQ太弱了…… P1295创意吃鱼题目描述： 可爱猫猫家里长方形大池子中有很多鱼，她开始思考：到底要以何种方法吃鱼呢（猫猫就是这么可爱，吃鱼也要想好吃法 。她发现，把大池子视为01矩阵（0表示对应位置无鱼，1表示对应位置有鱼）有助于决定吃鱼策略。 在代表池子的01矩阵中，有很多的正方形子矩阵，如果某个正方形子矩阵的某条对角线上都有鱼，且此正方形子矩阵的其他地方无鱼，猫猫就可以从这个正方形子矩阵“对角线的一端”下口，只一吸，就能把对角线上的那一队鲜鱼吸入口中。 猫猫是个贪婪的家伙，所以她想一口吃掉尽量多的鱼。请你帮猫猫计算一下，她一口下去，最多可以吃掉多少条鱼？ 输入： 第一行有两个整数n和m（n,m≥1），描述池塘规模。接下来的n行，每行有m个数 ...

区间动态规划 今天谜一样的把区间动态规划给敲完了QAQ，好累……特地来总结一下！ 区间动态规划就是针对一个区间，进行从小区间推到大区间，而大区间的值来自于小区间，一般是有三重循环，最外面枚举区间长度，从2开始，另一个循环开始枚举出发点，然后结尾就可以计算出来，最后枚举在i到j中选择分割点来分割成两个小区间来更新i到j这个大区间。区间DP在乎的是区间成体的最优值。 然后区间DP的题并不水，要比昨天的题目要难一些的，所以还需要多多复习一下！PS：（省选之前复习一下所有学过的模板，感觉已经忘光了QAQ）。 P1290关灯题目描述： 宁智贤得到了一份有趣而高薪的工作。每天早晨她必须关掉她所在村庄的街灯。所有的街灯都被设置在一条直路的同一侧。 宁智贤每晚到早晨5点钟都在晚会上，然后她开始关灯。开始时，她站在某一盏路灯的旁边。 每盏灯都有一个给定功率的电灯泡，因为宁智贤有着自觉的节能意识，她希望在耗能总数最少的情况下将所有的灯关掉。 宁智贤因为太累了，所以只能以1m/s的速度行走。关灯不需要花费额外的时间，因为当她通过时就能将灯关掉。 编写程序，计算在给定路灯设置，灯泡功率以及宁智贤的起始位置的 ...

综述： 完全是受到了尧神的启发，决定开一个刷题柱，记录下来每天刷的题，给自己增添一些动力QAQ，加油！ 刷题榜：Apr/5 五道题：P1282，P1283，P1284，P1285，P1296；Apr/6 五道题：P1286，P1287，P1290，P1291，P1292；Apr/7 五道题：P1293，P1294，P1295，P1298，P1331；Apr/8 四道题：P1507，P1326，P1327，P1309；Apr/9 今天没有刷题 复习+总结；Apr/10 一道题：P1328；Apr/11 放假；Apr/12 放假；Apr/13 五道题：P1966，P1661，P1330，P1329，P1924；Apr/14 五道题：P1907，P1935，P1662，P1660，P1093；Apr/15 四道题：P1096，P1098，P1900，P1901；Apr/16 去轻院ACM浪了一波QAQ ；Apr/17 考前复习；Apr/18 期中考试；Apr/19 期中考试；Apr/20 放假 两道题：P1315，P1236；Apr/2 ...

直接题目P1283 HAOI2010 最长公共子序列题目描述： 字符序列的子序列是指从给定字符序列中随意地（不一定连续）去掉若干个字符（可能一个也不去掉）后所形成的字符序列。令给定的字符序列X=“x0，x1，…，xm-1”，序列Y=“y0，y1，…，yk-1”是X的子序列，存在X的一个严格递增下标序列<i0，i1，…，ik-1>，使得对所有的j=0，1，…，k-1，有xij = yj。例如，X=“ABCBDAB”，Y=“BCDB”是X的一个子序列。 对给定的两个字符序列，求出他们最长的公共子序列。 输入： 两行序列，以”.”为结尾。 输出： 两行，最长公共子序列的长度和最长公共子序列的数量； 题解：这道题的第一问是比较好求的，只需要列出状态转移方程： 123f[i][j]=max(f[i][j],f[i-1][j-1]+1);if(ch1[i]==ch2[j])f[i][j]=max(f[i][j],f[i-1][j-1]+1); 但是关键在于第二问，第二问需要求出序列的数量，也就是所有的方案数，我们就可以建立一个数组 g[i][j] 表示在第一行字符i之前和第二 ...