wcxyky的博客

近来这段时间，大概的学习步骤是白天通过做数论的题目巩固已经会的数论知识，以及学习一些新的数论知识。都是靠题目带动学习，否则光看效率不太高，看不下去。但这几天做题很懈怠，总是看着别人过了什么题，自己才去跟着。导致给自己心理放松，别人没做的自己看一眼，啊，好难，就放过去啦。正好，今天，老师发了数论1-数论5的题目博客，可以催促自己把前面的题目没做的看一遍补上。晚上除了继续做数论的题目，有时...

今天看的，老师把整个寒假要做的数论练习题都放了出来，告诉我们不仅要做题，重要的是锻炼出做题的思维，总结出思考问题的方法规律。感觉老师总结的好正确啊。现在做的数论的题目，很多都是把题目经过转化，数学公式的推算最后转变到我们数论常用的知识点上面来。进而应用数论知识。而且数论真的很锻炼思维，很多题目自己想不到往哪一方面去化，但看到别人的做法就是那样。本来觉得数论涉及到的知识点太多啦，太杂啦，...

最近做的数论的老师给的第一套题目主要就是关于数论前面基本知识的。很多题目都是用打表找出题目规律的，像打表筛素数，打表找各种规律等。另外一点要注意的是：要注意时间复杂度。另外还要考虑到题目涉及到的特殊情况，不然又白WA上几遍。...

这周发了一套数论练习题，做了一些发现自己前段时间学的数论有所遗忘，所以在做题前先又复习了一遍，边做题边复习前面学过的知识，但自己掌握的还是不深入，就是看到有些题目想不到具体用学过的知识点怎么靠，所以有时一看别人的题解又豁然开朗，所以不愧是短时间内“速成数论”。没有那么强的自悟能力，还是多见题目，多做题目吧，否则真的学过的数论知识不知道如何灵活应用啊。...

最近几天看的主要看的佩尔方程，扩展欧几里得算法，中国剩余定理和欧拉函数应用的题目，以及一些数论在ACM中常用技巧。这两天看的实在比较急，感觉有点囫囵吞枣，不是十分细致。过错啊，因为实在感觉要看不完啦。我还有莫比乌斯反演没有看那，感觉我要凉凉啦。下周既要看四级，还得把莫比乌斯反演看完，加油，祝我幸福。...

这两天一直在看发的数论有关的知识点，的确在学的前期感觉定理很多，很杂，但后面还会反复提及到并应用，所以就又感觉没有想象中的那么多，那么难（可能我现在看到的都是一些对于定理的比较简单的基础应用，哈哈哈，所以才会有这样的感慨）。还有一个关于做必要的总结的事，不总结吧就感觉就过了一遍自己的脑子，但总归不是自己的。但如果见到自己不太会的就整理就有点浪费时间，所以，回来还是要注意一下整理的问题。加油看。...

最近几天在看老师发的关于数论的整理的资料，可能是我还没有看到那么深入的地方，大体就感觉，好多定理（当然是除去那些比较简单的）。还有证明，因为得懂其所以然，不能只会裸题。所以就得真正弄懂证明和扩展应用，但有时心会有浮躁，总想一下子就明白原理或是会应用，就导致无法沉下去。这一点回来要改正。刚才看了一眼老师发的消息，让两周内看完全部的知识，我的天，照这样，那得每天挤出更多时间去学数论，要不然真学不完...

昨天下午，老师给我们开了一场会：关于如果只是浑浑噩噩地想应付平常考试一样去对待ACM，那么他也会敷衍地对待你：你将不会有任何收获。随着现在参加ACM比赛的队伍越来越多，题目也是越来越难。如果继续按照我现在只是了解一下简单算法的基本原理，做一些很简单的题目，那么其实没有任何意义可言。说实话，昨天我真的感觉自己很垃圾，在考虑自己是否还要接着学下去。知道今天，我看了我们学校一个参加了今年区域赛的一个...

这两天主要复习了线段树和树状数组这两部分，这一部分是怎么用于题目中对于题目降低时间复杂度的那，它是对于单点和区间的各种操作。在看的以及做的题目中，关键是能够把题目中所看的问题一看普通做法复杂度高，需要线段树优化，立马能把实际问题对应于线段树的各种操作问题。另外，在处理问题中的过程，可能会有一些相对通用的技巧。例如：在线段树上加标记用来表示目前的状态，可以在每次查询时降低时间复杂度。还有lazy...

这两天做的题目不算很多，没有看一些新题目，就做的Vjudge上的关于二分三分法还有单调队列单调栈这的基本算法的题目。又顺着数据结构复习了并查集。但唯一的收获就是，做的题目多了，对二分三分法法还有单列队列，单调栈的算法更加熟练。尽管他们比较基本。以前没有准备过口语，星期六要开始啦，明后两天要空余时间把五大模块学习准备一遍。ps:数据结构这一部分还有线段树没有大做题巩固。剩下的感觉自己都复...

这两天一方面做的是Manacher算法的相关变形题，对这一算法有更加清楚的学习。另一方面是学习的基本算法是二分法，尺取法在做题目的一些应用。我看了一些大佬写的题解关于这两方面的，发现自己对于比较裸的可以做出来，但要是在运用其他算法但利用到这一算法优化的话我可能会想不到这样解决。但其实在很多算法题目的解决中，都会用到基本算法的优化的。另外还有做的RMQ的一些变形题目。这个还可以，了解倍增思想...

这两天做了几道关于KMP和字符串最小最大表示法结合起来的题目。最小最大表示法可以在O(n)的时间内确定一个字符串在循环过程中字典序最小或最大是第几个。所以就又看了一些博客和这一用法有关的。看了几道最小最大表示法和Hash用法以及二分的基本思想用法结合起来的题目。另外，又翻出了后缀数组的方面的知识，不得不说，好长时间不见它，我竟又记不清它啦，由此可见，得常复习，要不可能就会像那什么狗熊掰...

这两天做的KMP及其各种变形以及马拉车算法的题目，包括像KMP后缀前缀匹配；KMP中求字符串的前缀是否为周期串，若是，求循环节长度和循环次数；kmp补齐循环节使成为循环串至少应添加几个字符；统计模板串在待匹配串中出现的次数；KMP中对next数组原理的理解；KMP求最小循环节个数等题目。另外，又复习了AC自动机的相关知识以及看了以前大佬写的莫队算法的题目，复习完接下来可以把这个专题也做了。...

最近是跟着做的VJ上的几个专题，题目确实不错诶。感觉最受用的提高就是对尺取法有了更深刻的理解，学习了一种学习技巧：尺取法：尺取法通常是对数组保存一对下标，即所选取的区间的左右端点，然后根据题目情况不断地推进区间左右端点以得出答案。之所以说是个技巧，是因为尺取法比直接暴力枚举区间效率高很多，尤其是数据量大的时候，所以说尺取法是一种高效的枚举区间的方法，一般可以用于求取有一定限制的区间个数或最短的...

对于上个月的学习总结，主要就是前期看的别人写的数据结构的博客学习的知识点，后期是做的51nod上的题目。直到前段时间做不下去啦，对。昨天，老师给我们开了一个会，是关于未来需要做的事，注意的事项，近期的安排，长远的计划。大体规划是：接下来的一个月到11月底，把vj上的数据结构的专题刷一遍，把自己不熟的知识点认知的更清楚。然后一个月后要开数论专题，老师说数论题目讲的是一个变化，所以可以提高人的...

今天做了一套题，整个过程都在死磕D题，是求你操作完的矩阵的四个角的最小值的最大值，在经历一会后，我们发现，这是一道较明显的二分题目，但我一直卡在了如何判断你弄的mid是否合法，后来在很长时间后看了一下别人的思路，发现是一种转化的很巧妙的去判断两两在同一列并且大于mid。额，搞了那么长时间，还感觉从前似曾相识。由此而见，自己在思维的转化方面太弱啦，结束后看这是一道D级的二分题目。由于死磕这道题，导致...

自从上次做的数据结构的专题做不下去了，所以转战的下面的数据结构知识点的分专题，有字符串，线段树，单调栈，哈希，并查集，单调队列，树状数组等，做这些题目比较细微没有那么综合，所以难度较小。由此可见，自己做综合知识点的大题还是很有难度，还是自己基础没扎实，做的题不多。自我检讨：过去的这一周做的题目不多，因为一些其他的事情。接下来的时间到11月15号为止，要争取把数据结构所有专题，分专题的题目除...

这两天做题很自闭啊，挨着做题发现越来越做不动啦，索性跳过但往下迎接我的却依然那么难。按理说，这些题涉及到的知识点全都是数据结构中涉及到的知识点，但自己却想不到如何去做。感觉自己用了很长时间去想思路还是想不出来，所以，通过做题，感觉自己学知识还是掌握的皮毛，掌握的不熟练，不深入。所以接下来要调整一下自己策略：做题辅以学知识，因为自己对知识掌握程度的不熟，导致自己做题做不动。还是自己见得少，同时鞭策自...

最近两天是做的51nod 上面的题目，上面的题现在我做的还是一些复习基本算法的题目，像单调栈，主席树求区间第k大，第k小，以及二分，尺取等基本算法。在做题的过程中又从头复习了一遍数据结构的算法，发现自己有的知识点确实有所遗忘，可以督促自己再复习一遍总结一遍。大概就是这样，其余还是接着做题。做题发现补自己的漏洞。...

最近两天没有学很多新东西，因为主要看的是处理字符串的各种算法。因为它们的相对题型很固定，翻来覆去就那几种，顶多和二分以及哈希联系一下，所以变化较少较简单。做的51nod上的题目，前面很简单，按AC数量做的，后面的大概模块我看了一下，也就是哪几种，但题目还没有具体做。突然今天看到一个还有个可持久化线段树的专项，我还没有系统看，回来最近得把它学了。其实我感觉51nod上的题目只是一个辅助，关键还是...

这两天，一个是学习了主席树的两种，一种是静态的主席树的查询（对于每次查询，输出区间[l,r]中第k大的数 ），还有是一种动态的主席树的查询（可以随时进行单点或区间的修改并随时输出区间[l,r]中第k大的数）。因为前两天学习的树链剖分，所以这两天就紧接着学的LCA，像和线段树优化结合，以及树链剖分，以及离线tarjan算法（图论的），还有和深搜一遍整棵树在回溯的时候利用树形dp结合的（这个看的还不...

这两天学习了树链剖分和线段树结合起来的维护以及修改树上路径的问题。其实看明白了就是先树链剖分用两个dfs序将树上路径转化为线段树的区间，然后就还是线段树单点以及区间修改查询的那一套，这也算是一种类型的题木吧。树链剖分的作用就是将一棵树变成一个可处理的dfs序，对于树上操作一般都是由线段树和树状数组维护。另外，还学习了dfs序和欧拉序的不同以及应用。用dfs序求出每个节点的入时间戳以及出时间戳，...

这两天学了一些关于涉及到将树用dfs序和邻接数组(链式前向星)转化为线性的线段树以及好用的树状数组的所处理的单点修改，区间修改以及区间查询等问题，并带出来了LCA最近公共祖先都可以实现。另外今天又捎带着看了一点欧拉序以及欧拉序的用途Tarjan算法（离线算法）即：首先读入所有的询问（求一次LCA叫做一次询问），然后重新组织查询处理顺序以便得到更高效的处理方法。Tarjan算法是一个常见的用于解...

这两天主要看了线段树集中几种类型的题目。第一道是因为如果不离散化要开10的八次方的数组。而在，线段树中开这么大会超时。一般见的都是开到10的5次方的数量级。第二个是一道铁路的关于转化为线段树的题目。问题是转化成对n-1个数进行m次区间更新最值，对于每段铁路而言，min表示该最早被使用的时间，max表示最后一次被使用的时间，最小花费即区间查询就是每天都加上这段铁路的花费，更新用线段树upda...

近两天主要看的线段树方面的题目。然后发现用到线段树的题目虽然有各种类型，但追其根本都是为了降低时间复杂度，两种本质：一种是单点修改区间查询，另一种是区间修改区间查询操作。只要题目的本质涉及到这两种操作，都可以是用线段树来解决。其实难点主要是考虑线段树每个节点维护什么信息，还有如何通过线段树维护的节点信息来解决题目所要求的问题。从而修改写出build,pushup,update,query四个函数来...

前两天把RMQ算法的那几道题目收尾了以后，今天又开始看的后缀数组的算法，看了道给你一个字符串,要你求出这个串中的最长回文字串,如果存在多个,则输出第一次出现的那个的题目，这道题目其实用马拉车算法实现更简单，上一次打比赛时就涉及到求最长回文子串用马拉车算法的。所以又复习了一遍马拉车算法。然后又看了几道用后缀数组求公共子串和最长公共子串的题目，都是些标准的后缀数组的题目。明天还要接着看把后缀数组和...

最近主要看了RMQ算法的相关题目。这两天杂事比较多，所以看得进度比较慢。幸亏下周就没什么杂事啦，可以多学很多。RMQ问题可以解决对于一个整数数组(也可以是其他可比较大小的元素类型)的任意区间[L, R]查询最值时，能在经过O(nlogn)的时间预处理后，做到O(1)时间复杂度的任意区间最大最小值查询。接下来大概写一下几种题目：题目：给出一个非降序排列的整数数组a1,a2,...an，你的任...

最近这两天主要看了树状数组部分的题目。树状数组主要用于单点更新和区间查询，像区间更新和单点查询还是用线段树更为方便一些。这两天看的题目有：1.单点修改 + 区间查询的模板题，一眼就出2.由于数据量大用树状数组+离散化处理的3.用树状数组求逆序对的（好多道题目）4.还看了道树状数组和扫描线结合的题目（其实用线段树做就行）5.还有几道是二维的树状数组的题目想看多点题，所...

今天，我们近期6场网络赛结束了。结束后，费老师也给我们开了个小会。首先明确自己目前在比赛中的定位：我感觉自己就是做那种签到题的。老师说打比赛ACM主要也就全都归结为那6种类型。按难以程度可以分为签到题（就是那种动动脑子用用基本算法就可以做出来的简单题），第二种就是一些算法的基本应用。老师说这种题目是我么应该目前努力学习看题多见应该达到的水平。最后一种就是很多算法综合在一起的综合应用题，当然是难度最...

昨天和今天两天，重新看了数据结构的并查集和树状数组两部分。并查集，可以用来动态维护许多具有互相导出的传递性的关系。很多具有传递性关系的题目都可以联想到并查集解决。此外，还要注意数据量，一般当给的约束条件变量x的范围很大时，几乎为10^9,我们首先要运用离散化将变量x的范围映射到与询问有关的数据范围内。另外，边带权的并查集是利用了路径压缩来统计每个节点到树根之间的路径上的一些信息。这是并查集...

开学的第一周已经过去啦。周六周天打的两场比赛暴露出自己很多问题：昨天一道马拉车算法的题本应该我数据结构的范围内，但我在我在学这一章相关知识的时候却没有重视起来导致那道题就没有出。所以说现在学算法和高考一样，学习的时候所以接触到的知识点都要学到位，面面俱到，不要打比赛的时候才后悔：当初为什么学习的时候没有学这一块知识，要是早学啦，我就可以出这道题啦。还有今天的那道E题的纯暴力模拟就可以做，但我却一直...

今天看了Bellman-Ford算法以及优化后的SPFA算法。然后看了几道用这这两天两种算法做的几道图论的题，都是一些很简单的把题意转化一下就可以转化为最短路的相关问题，不足是：看的效率有些低，还应该加强自己的效率。明天要把学的最短路的两个算法多看题巩固一下。...

今天晚上没有学很多，主要复习了邻接表的部分，然后就新学习了Dijkstra算法及堆优化的Dijkstra算法。其主要用于解决稠密图的问题，复杂度大概为O（mlogn）;另外，今天学习的具体知识及模板算法就先不写啦。今天把算法这一章的资料单独弄了下来方便平时看，明天继续学习Bellman-Ford算法以及优化后的SPFA算法。加油，每天只要愿挤时间总是很多的。...

ACM暑假训练感想总结及开学后对ACM学习的规划这个暑假仔细想想，就是学习了第一章的基本算法，一些递推递归，前缀和与差分，二分法，各种常用排序法，倍增，贪心的思想都会在各种题目中出现，是做很多题的都会用到的思想即题目解决所包含的一种知识点吧。还有第二章的基本数据结构以及第四章的数据结构进阶两章，数据结构是我所负责的专项，所以对于涉及到这一块的知识一定要真正地弄明白，弄...

昨天上午就看了前晚比赛的题目，随便翻了翻图论什么的。下午打网络赛，基本上能出的题目我们都出了，就是那道找规律的概率题难了我好久，后来还是队友搞定的。还有F的那道floyd题，因为我们队没有看图论的所以就很惨地没有做出来，我们后面的队伍说那道题很简单，如果没有读错题意的话就可以1A啦。好吧。反正我现在已经包揽了凸轮的重任，就要好好学啦。因为图论的题目在比赛中是必不可少的，分量很重。总之，加油...

今天看了bfs和dfs的相关知识。bfs看了几种题型的：求出最短路径并输出最短路径；bfs+优先队列；bfs+二分枚举区间；bfs+Hash判重的题也看了一下。关于dfs只看了几个求连通分量的题，剩下的关于像dfs回溯加剪枝的题型还没有看。然后后来又水了一篇社会实践报告，感觉今天学习有点浮躁。晚上做题的感觉，就是以后要注意开long long，今天又因为王凯long lon...

昨天看了AC自动机和后缀数组的两节，后缀数组就是把一个文本串的所有后缀按字典序从小到大排放的数组。AC自动机和后缀数组都可以处理多模板的文本匹配问题。AC自动机需要事先知道所有的模板，然后对于一个在线输入的文本串进行多模板匹配，即模板一定要全部事先知道，而需要匹配的文本可以后面输入。 而后缀数组需要事先知道整个文本串，模板可以一个一个的动态输入。后缀数组我看了几方面的题：找...

昨天因为看的KMP算法和字典树看的不认真，只是单纯的看了一遍题，对题目理解的也不透彻。所以今天上午首先把昨天学得不好的这两节重新又认真看了一遍，把所有看的题目又重新整理了一遍（应该怎么解决）。今天后下午才开的AC自动机，发现AC自动机是KMP算法和字典树结合的更高级算法，还有文章中用一个例子用三种方法计算的时间复杂度，所说的这三者都是用来解决字符串问题的。但具体却各有所长，KMP算法专门解决长...

今天主要学习了两部分的内容：KMP和字典树两部分的内容和题目。KMP算法是当当前某个字符匹配失败时，不是向纯暴力一样，将文本串匹配的起点往右移一个，而是将在模板中当前的匹配点左移到文本串当前点所能匹配到的最大的匹配点处。通过预处理出当文本串在模板某个位置匹配失败时，应跳转到的位置，即next或F数组，将时间复杂度从O（m*n）降低为O（m+n）;KMP算法主要是应用于三类题：看的博客上都有...

老师说让我们这一周负责好自己的那一章，所以今天看的并查集和线段树这两部分的知识点。首先是关于并查集，一般它处理的是无向图的)的连通分量问题。看的资料上将并查集问题分为了三类：一类是并查集的基础应用问题，一类是并查集根节点可以维护信息的题，还有一类是并查集路径压缩问题。上午看的关于这类的问题都基本上是并查集的裸题加一些知识点就可以实现，怪不得老师说这个博客适合我们算法初入门学习。...