题目链接 题意 一天做到两道这种题目描述如此神仙的题也是够了。真锻炼语文能力。 题目的意思其实就是，给你一个序列，然后每次询问一个区间。使得尽量按照严格上升的顺序从这个区间内取数。如果当前取得数字小于等于前面的其中一个，就让rp--，然后重新开始记录。问rp最多可以是多少。 思路 思考一下可以发现，其实就是求区间内众数出现的次数。 原因如下: 如果有相等的数字，那么这些数字是无法避免rp--的。既然无论如何都要减了，那么就要考虑如何让他减得更有价值。 比如说有一段序列:1 1 1 2 2 5 5 6 7 8 现在1 和 2都是有多个，显然按照下面的顺序取数是最优秀的: 1 2 5 6 ...

题目链接 题意 一天做到两道这种题目描述如此神仙的题也是够了。真锻炼语文能力。 题目的意思其实就是，给你一个序列，然后每次询问一个区间。使得尽量按照严格上升的顺序从这个区间内取数。如果当前取得数字小于等于前面的其中一个，就让rp--，然后重新开始记录。问rp最多可以是多少。 思路 思考一下可以发现，其实就是求区间内众数出现的次数。 原因如下: 如果有相等的数字，那么这些数字是无法避免rp--的。既然无论如何都要减了，那么就要考虑如何让他减得更有价值。 比如说有一段序列:1 1 1 2 2 5 5 6 7 8 现在1 和 2都是有多个，显然按照下面的顺序取数是最优秀的: 1 2 5 6 ...

题目链接 题意 读完题目就一个感受：这出题人tm不会说人话吗。真的感觉这个题理解题意比想出正解更难。 其实题目的意思就是，给出一些单词，给这些单词编个号，然后要求其他的单词中是这个单词后缀的词都在这个词的前面。每个单词的贡献是当前单词的标号减去他的后缀中标号最大的那个的标号。 希望我能表达明白吧233 思路 因为后缀不好考虑，所以先把字符串倒过来，就都变成了前缀 然后把这些字符串在全都挂到trie树上，每个字符串的结尾打的标记是这个字符串的标号。 删去trie树中的虚点(没有打标记的点)。就可以得到一棵新的树，然后发现，每个字符串的前缀肯定都是他的祖先。然后要求给这些节点编号，是的每个...

题目链接 题意 读完题目就一个感受：这出题人tm不会说人话吗。真的感觉这个题理解题意比想出正解更难。 其实题目的意思就是，给出一些单词，给这些单词编个号，然后要求其他的单词中是这个单词后缀的词都在这个词的前面。每个单词的贡献是当前单词的标号减去他的后缀中标号最大的那个的标号。 希望我能表达明白吧233 思路 因为后缀不好考虑，所以先把字符串倒过来，就都变成了前缀 然后把这些字符串在全都挂到trie树上，每个字符串的结尾打的标记是这个字符串的标号。 删去trie树中的虚点(没有打标记的点)。就可以得到一棵新的树，然后发现，每个字符串的前缀肯定都是他的祖先。然后要求给这些节点编号，是的每个...

题目链接 思路 这道题我用的是AC自动机的做法。 先把子串挂到trie树上，在单词结尾打标记的时候，标记的是当前单词的长度。然后去上面查询母串的时候，每查询到一个单词，就建立一条线段，这条线段的结尾位置是母串当前的位置，开始位置就是用当前位置减去这个单词的长度。 然后只要去判断，选出一些线段，使得这些线段紧挨着(既不相互覆盖，中间也不遗漏)从母串开始位置铺，能铺到的最远的地方。所以只需要一遍bfs就行了。 代码 /* * @Author: wxyww * @Date: 2018-12-17 08:38:38 * @Last Modified time: 2018-12-17 09:...

题目链接 思路 这道题我用的是AC自动机的做法。 先把子串挂到trie树上，在单词结尾打标记的时候，标记的是当前单词的长度。然后去上面查询母串的时候，每查询到一个单词，就建立一条线段，这条线段的结尾位置是母串当前的位置，开始位置就是用当前位置减去这个单词的长度。 然后只要去判断，选出一些线段，使得这些线段紧挨着(既不相互覆盖，中间也不遗漏)从母串开始位置铺，能铺到的最远的地方。所以只需要一遍bfs就行了。 代码 /* * @Author: wxyww * @Date: 2018-12-17 08:38:38 * @Last Modified time: 2018-12-17 09:...

用途 AC自动机适用于一类用多个子串在模板串中匹配的字符串问题。 也就是说先给出一个模板串，然后给出一些子串。要求有多少个子串在这个模板串中出现过。 KMP与trie树 其实AC自动机就是KMP与trie的结合版。或者说是在trie上进行的kmp算法。所以学会kmp和trie是学习AC自动机的基础。 对于上面那类问题。可以对于每个子串都用kmp算法在母串中匹配一次。但是复杂度就成了\(n^2\) AC自动机 而对于这类问题，AC自动机的实现是先把所有的子串都挂到trie树上，然后在用母串去trie上匹配。 首先往trie上挂子串和普通的trie一样。就像这样 void add() ...

用途 AC自动机适用于一类用多个子串在模板串中匹配的字符串问题。 也就是说先给出一个模板串，然后给出一些子串。要求有多少个子串在这个模板串中出现过。 KMP与trie树 其实AC自动机就是KMP与trie的结合版。或者说是在trie上进行的kmp算法。所以学会kmp和trie是学习AC自动机的基础。 对于上面那类问题。可以对于每个子串都用kmp算法在母串中匹配一次。但是复杂度就成了\(n^2\) AC自动机 而对于这类问题，AC自动机的实现是先把所有的子串都挂到trie树上，然后在用母串去trie上匹配。 首先往trie上挂子串和普通的trie一样。就像这样 void add() ...

昨天考试分层图最短路用个dp暴力水了90分。今天只有10分。。。还是好好来学分层图吧。(实际是不想学数据结构2333) 一类问题 分层图最短路得经典模板题就是这样 给出一个n个点m条边的无向图，每条边有边权，可以选择最多k条边，把他们的边权变为0。问从S到T的最短路是多少。 解法 一般这类问题K都会比较小。所以可以建K层图。第i层图表示已经把i条边变成0。 然后就是怎么连边。首先在每层图中，u和v之间还是要连边的。那么两层图之间的边呢。为了表示出已经把一条边变为0了，所以要把第i - 1层图中的u向第i层中的v连一条权值为0的边，因为是无向图。所以还要把第i - 1层中的v...

昨天考试分层图最短路用个dp暴力水了90分。今天只有10分。。。还是好好来学分层图吧。(实际是不想学数据结构2333) 一类问题 分层图最短路得经典模板题就是这样 给出一个n个点m条边的无向图，每条边有边权，可以选择最多k条边，把他们的边权变为0。问从S到T的最短路是多少。 解法 一般这类问题K都会比较小。所以可以建K层图。第i层图表示已经把i条边变成0。 然后就是怎么连边。首先在每层图中，u和v之间还是要连边的。那么两层图之间的边呢。为了表示出已经把一条边变为0了，所以要把第i - 1层图中的u向第i层中的v连一条权值为0的边，因为是无向图。所以还要把第i - 1层中的v...

题目链接 思路 对于每一种颜色都建立一个动态开点线段树。然后每次查询的时候就去这个颜色的线段树上查询就行了。修改之后不要忘记交换颜色。 这个题目数据有点强。抄了个比较快的读入优化才卡过去。 代码 /* * @Author: wxyww * @Date: 2018-12-13 08:59:51 * @Last Modified time: 2018-12-13 09:56:16 */ #include<cstdio> #include<iostream> using namespace std; typedef long long ll; const int ...

题目链接 思路 对于每一种颜色都建立一个动态开点线段树。然后每次查询的时候就去这个颜色的线段树上查询就行了。修改之后不要忘记交换颜色。 这个题目数据有点强。抄了个比较快的读入优化才卡过去。 代码 /* * @Author: wxyww * @Date: 2018-12-13 08:59:51 * @Last Modified time: 2018-12-13 09:56:16 */ #include<cstdio> #include<iostream> using namespace std; typedef long long ll; const int ...

机房同传了新的系统，不使用dev的话每次开机都要重新更改环境变量(其实也可以在编译命令里添加绝对路径)。所以就去学习了一下用bat脚本更改path。以便每次开机可以一键更改添加环境变量 wmic environment where "name='PATH' and username='<system>'" set VariableValue="%PATH%;这里是要添加的路径" 其中前面是一些语法，PATH可以更改成其他的变量，但是作为一个OIER一般不用吧。后面抄上就行了。\(\%path\%\)是引用原来的path,然后加一个&quo...

机房同传了新的系统，不使用dev的话每次开机都要重新更改环境变量(其实也可以在编译命令里添加绝对路径)。所以就去学习了一下用bat脚本更改path。以便每次开机可以一键更改添加环境变量 wmic environment where "name='PATH' and username='<system>'" set VariableValue="%PATH%;这里是要添加的路径" 其中前面是一些语法，PATH可以更改成其他的变量，但是作为一个OIER一般不用吧。后面抄上就行了。\(\%path\%\)是引用原来的path,然后加一个&quo...