刷题柱
一个小小的刷题柱记录刷过的题
kuangbin刷题柱
Dungeon Master（5.23）
bfs，细节在于搜索到点之后入队时就进行标记已经搜索到了。不然会反复入队导致超时。
Find The Multiple（5.25）
一个技巧，在dfs中如果不想让递归回到上一层之后继续执行的话，不要把dfs的返回类型设为void，而是设为bool，让多层的dfs返回到上一层就遇到一个if，就保证找到答案之后就会返回，不会寻找到多个值。常常用于有spj的搜索题。
Prime Path（8.1）
水题，素数筛 + bfs。
Shuffle’m Up（8.2）
水题，字符串模拟。注意：字符串为空的时候不要进行下标赋值，会出现问题，用s.push_back向空字符串中放置字符，否则会出现下标可以访问字符但是整体字符串为空的情况发生。
Pots（8.2）
BFS，寻找最小变换次数即最小步数。比较特殊的是这个需要保存操作的步骤，可以用一个三维vector来保存每一次操作的动作编号，然后在到达状态之后依次输出即可。
Fire Game（8.3）
离谱的是FZU挂掉了，没办法评测，样例都过了， 复习了一下如何求联通块的个数和双起点BFS。
经验：下次做题前看一下uoj在那个网站提交的标志是不是红色。。。
分类刷题柱
队列
蚯蚓（5.4）
https://ac.nowcoder.com/acm/problem/16430
这道题的解法是维护三个单调队列，由题可知蚯蚓切完的性质仍然满足蚯蚓的长度是依次递减的，由于是按照比例切的，那么切的是相同比例的蚯蚓放到一个队列中，由于靠前切的蚯蚓一定切出来的也是比之后切出来的蚯蚓长，所以当前的最长的蚯蚓只需从这三个队列中找到队头即可。
Cow Line（5.5）
https://ac.nowcoder.com/acm/problem/24876
这道题就是一个简单的双端队列的模拟，题中数据的范围是模拟可以接受的，看出来题考的数据结构是双端队列就行了，维护两边的进队和出队即可。
Team Queue
https://ac.nowcoder.com/acm/problem/50966
又是一道模拟题，团队队列只需用团队编号作为大队伍的标志，然后再委会每一个团队队列的内部次序即可。用一个queue和一个queue数组和一个map即可，细节还行，难度适中。出现的问题是数组越界了。最后发现标志该团队是否入大队列的bool数组并不是必要的。可以用检查该团队队列是否为空来代替。
长跑（5.6）
https://ac.nowcoder.com/acm/problem/14570
是道队列bfs，从起点开始搜索，如果当前节点加上maxn可以到达并且钱够的商店就入队，然后如果碰到终点就退出。就是一道朴素的bfs，但是如果看不出来的还是有点迷惑的。
道路铺设（5.8）
https://ac.nowcoder.com/acm/problem/21222
再次做到NOIP2018提高组的题，感慨万千。隐约记得在考场上发现是前两天做过的原题的兴奋的心情了。当时的我先发现是差分，处理出差分数组之后经过观察是差分数组为正值的所有值的和即为答案，当时并没有经过严谨的证明，隐约感觉正值和负值之间一定会相互抵消。今天重新写到，当时的感觉重新涌上心头。
其实就是一道水题，并不是优先队列，差分之后将正值加到一块即可。可以进行一个简单的证明，一个数列的差分数组的所有元素的和一定为0，那么想要将这个差分数组的正数变为0，那么每一个正数都要和负数相对应结合。其中一个问题是如果确定进行变化的一对差分中间没有0，其实这也好证明，因为每一个正数会找到最近的一个负数进行中和，那么可以保证在对更远的负数进行中和的时候，比较最近的负数已经进行了中和，级这个比较大的数通过和附近的数进行中和，已经和周围的数的大小基本相同，所以不会出现跨过一个比较小的数然后进行更行的情况发生。第二个问题是，会不会出现前面的正数不能将一个比较大的负数使用完就直接跳到后面的正数了，显然也是不会的，因为这个数列是一个正整数列。
栈
好串（5.7）
https://ac.nowcoder.com/acm/problem/21874
一个栈的水题。
吐泡泡
https://ac.nowcoder.com/acm/problem/15029
一个栈的应用，水题。
表达式计算4（5.8）
https://ac.nowcoder.com/acm/problem/50999
栈的经典应用，表达式求值。这是一个中缀表达式求值。维护两个栈，一个栈存数字，一个栈存符号，数字进栈没有什么要求，如果有一个符号要进栈的话，先把比该符号优先级高的在符号栈中的符号都先弹出栈，符号两边的数字进行运算。这样就保证了每一个运算都是优先级高的先运算。
模拟的过程会比较繁琐，而且注意栈如果为空的话调用栈的.top()会报错，所以把原来的表达式的最外层加一对括号来保护。
括号画家
https://ac.nowcoder.com/acm/problem/50998
括号匹配，寻找最长合法括号匹配串。由于如果出现不合法的情况，那么之前的合法的长度就不能加到后面的括号序列上了。所以只需维护一个括号匹配栈即可，如果出现了不合法的情况就将最长串和目前的最长串进行一个更新即可，最后答案中的长度就是最长的合法括号字串的长度。
并查集
奶酪（5.8）
https://ac.nowcoder.com/acm/problem/16417
经典并查集例题，怎么写都能过的无极数据友好的题，只用将两两洞进行测距然后看距离满足，如果满足就直接将两个洞用并查集连在一起。然后看离地下比较近的洞和离上面比较近的洞是否联通即可。这道题应该也可以用其他测联通的方法写出来。
关押罪犯
https://ac.nowcoder.com/acm/problem/16591
并查集的经典应用，一个非常好的思路是：我们将并查集的f数组进行拓展一下来表示更多的状态，来简化一些比较困难的逻辑表示。我们将f数组拓展一倍，i表示一个监狱i+n表示另一个监狱。我们对于每一对罪犯，都默认将他们装到不同的两个监狱中即a和b+n，a+n和b，然后检查他们在相同的监狱中是否出现冲突。这个做法其实是将一个状态拆成了比较好表示的两个状态。将逻辑上很复杂才能检测的问题变成一些很简单能判断的问题。
这种方法叫做建立虚点。
虚点的建立可以拓展表示一个点的多个状态。
食物链（5.9）
https://ac.nowcoder.com/acm/problem/16884
这题本质上应该是然用带权的并查集来写，但是有一种比较好写的方法是开虚点。用三倍的n的数组来表示每一个点的三个不同性质，对不同性质之间进行操作，这样就减小了处理复杂问题的难度。
棋盘问题（5.15）
http://poj.org/problem?id=1321
一道经典的搜索题，用dfs进行搜索，一个控制层数，一个控制放了几个棋子。注意dfs中需要将每一层的情况都列出来。
刷题打卡墙
5.8： 5道。挺麻的，又开始觉得自己是个fw了
5.15：1道题，被张宇说的网络流刺激到了，又滚来刷题了。
5.23：1道题，kuangbin的题单质量就是高，把之前的一道题改对了，还是浮躁，张文军教练的话，很有道理。
5.24：1道题，今天晚上有cf的#722的div2的比赛。但是进晚了怕掉分没打，写了一下t1，水体一道。
5.25：1道题，kuangbin的搜索专题。
