HDU 4691 Front compression

By NodeKey in ACM on

后缀数组之最长公共前缀的不定查询。 因为查询很多，所以要结合RMQ算法。这个也是很简单的，一般不会有什么变化，只要套一下木板就好了。 但是这个有一个非常困扰我的地方，就是题目给定的查询不是后缀之间的最长公共前缀查询，而是子串之间的查询，这可难倒我了，我也不知道该如何解决。 看了题解后，发现其实解决方法很简单，只要将求得的 LCP 与两个子串长度互相比较，三个长度取最小就是我们要得答案。 题意： 给你一个字符串，再给你很多子串，要你将所有给定的子串进行压缩。 压缩方式为将两个字符串的最长公共前缀在第二个字符串用数字表示。 输出未压缩的长度和压缩后的长度，要记空格和换行。 思路： 不断求 LCP 即可。 在求的过程中有几个注意的地方。 * 注意后缀相同的情况。 * 得到两个后缀的 rank 后不能直接使用 RMQ ，一方面有不确定的大小关系，另一方面，我们是对height 数组求 RMQ ，做区间应为 较小的 rank + 1 。 * 注意将RMQ数组开大…… 这道题使用的代码已经能成为我求 LCP 的模板了 除了改成DC3 AC Code…

HDU 4552 怪盗基德的挑战书

By NodeKey in ACM on

一道不知所以然的题目…… 没什么好废话的，直接上题解。 题意： 要你求一个字符串的所有前缀在自己本身的所有出现次数。 思路： 这道题如果用KMP的话是十分简单的，但是我一开始没想到用KMP，想了一些时间，看了kuangbin的博客说可以用KMP求解，略想了一下，果真如此。 KMP思路： 直接next数组跳几下就可以了。 后缀数组思路： 后缀数组的思路让我有点蒙逼……只要将所有后缀与最长的后缀，也就是原串的最长公共前缀相加再加上原串长度就是答案。 而看过论文的都应该知道，这个是可以( O( n ) )直接求出来的。 但是还是有点似董非董。 #include #define each(i, n) for (int(i) = 0; (i) < (n); (i)++) #define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)…

POJ 2774 Long Long Message

By NodeKey on

后缀数组论文题，也是后缀数组的入门题——最长公共子串。 另外这题是双倍经验 HDU 1403 Longest Common Substring不过HDU的数据更水一点。 题意： 给你两个字符串，求最长公共子串。 思路： 因为是论文题，我不可能讲的比论文还详细的啦……这不是显然的吗 看了论文后基本就是套板子，因为它已经吧最关键的地方给证明了，然后有一个小地方，为什么可以直接拿 sa 数组与第一个字符串长度 key 比较呢？ 那是因为，sa数组本身就是记录后缀排名第 idx 位的是哪一个后缀，而后缀和第一个字符串 key ，都是从左往右正向计数的。故可以直接拿来比较。 AC Code #include #include #include #include #define each(i, n) for (int(i) = 0; (i) < (n); (i)++) #define…

HDU 3585 maximum shortest distance

By NodeKey in ACM on

淦啊……我之前自以为入门的最大团DP优化板子是错的，我说怎么和极大团计数差别这么多，那个原先的根本就是一个被谁自创的dfs+dp优化算法，速度平均慢一倍！！！ 说句别的，终于刷完这套……给出链接 最大团与稳定婚姻专题 题意： 要你找出一个数量不小于 k 的最大团，使得最大团中的最短距离最大。 思路： 二分距离+最大团判定 老实说我一开始没想到，但看到这个思路之后就是豁然开朗，感觉二分的思路都是这样的…… 然后疯狂TLE……不知道为什么，查了一下，最大团板子太慢了……原来学得是民间算法！！ AC Code #include #include #include #include #include #include #include #include #include #include #include #define each(i, n) for (int(i)…

ACM C++ 正则表达式使用简明指南

By NodeKey on

前言 前排提示！！！ 这里的正则表达式只用来竞赛！！！！ 只谈论正则函数的使用方法，不涉及正则表达式的基础使用方法。 尽管 C++ 的 正则表达式一直为人所诟病，一般人都会推荐你去使用boost的正则，但是ACM竞赛里显然是不能使用boost库的…… 据说 C 的正则比 boost 的正则都要快，然而我不会……自然得觉得 C++ 会好用点吧。关于 C 的以后学。 正则表达式类 regex , 头文件即 regex。 三个核心函数 C++ 的正则库有三个常用函数，也是核心函数，分别是regex_match,regex_replace,regex_search 具体见下。我在这里只介绍在ACM里常用的一两个用法，具体了解还请点开各自的官方文档链接，上面有实例代码，非常好懂。 regex_match regex_match 用来将正则表达式与整个字符串进行匹配，返回一个布尔值，如果匹配成功，返回true，…

POJ 2989 All Friends

By NodeKey in ACM on

最大团问题之极大团计数。 啊呀啊呀，基本都会是板子题啦…… 但是尽管是板子题，上次ccpc网络赛卡我的题，我当时要是有个最大团的板子，就可以直接过了…… 极大团计数和最大团不大一样，这里有wiki上的伪代码 BronKerbosch(All, Some, None): if Some and None are both empty: report All as a maximal clique //所有点已选完，且没有不能选的点,累加答案 for each vertex v in Some: //枚举Some中的每一个元素 BronKerbosch1(All ⋃ {v}, Some ⋂ N(v), None ⋂ N(v)) //将v加入All，显然只有与v为朋友的人才能作为备选，None中也只有与v为朋友的才会对接下来造成影响 Some := Some…

HDU 6165 FFF at Valentine

By NodeKey in ACM on

好烦，感觉自己的图论知识都有了，但是一旦写起来还是非常欠缺…… 什么时候我才能踩完所有的坑，成就大佬之路呢…… 今天多校的第二道签到题…… 是的，签到题……但是我没有写出来为什么呢……我也想知道为什么我老是会这样那样的地方写错…… 今天错的地方是没有去重，还像条疯狗一样跑去BC官方博客理论了…… 在这里先道个歉…… 但是题解的确没写清楚 题意： 给你一个有向图，有环，无重边，无自环。 问你是否存在两个不联通的点。 思路： 拿到题的第一思路，拓扑排序，有环就缩点呗！ 然后开始疯狂WA…… 思路没错，但是在缩点后没有去重，导致缩点后一条边的出度增加，拓扑排序失败…… 好烦……讲道理缩点+拓扑，虽然简单，但也没有沦落到这种比赛的签到题上…… 原因就是数据很小，允许 ( O ( n^2 ) )解题…… 可能因为图论学傻了，没想到也不愿意用暴力做…… 暴力的方法是，枚举每一个点，记录它可以达到的点，构成一个二维矩阵，然后遍历一下矩阵，看是否存在相互不可达的点即可。 虽然暴力在我眼里有点不齿，但是优雅的暴力还是非常值得认可的。…

最大团Bron–Kerbosch算法入门

By NodeKey in Graph on

听了Yasola瞎逼逼打算去搞一下那些很混乱的东西。 首先就是这个最大团问题 建议先点开看看上面的百度百科链接。虽然东西很多，我也只是浏览了一下 瞎逼逼与个人理解 首先必须强调的是最大团是一个NP-Hard问题，目前并没有一个合适的在多项式时间内完美求得正解的算法。 而Bron–Kerbosch算法，名字好像是非常吊，其实就是各种优化过的搜索算法。 学习博客点这里 简单说一下个人理解。 Bron–Kerbosch算法基于基本搜索，但优化之处很多，优化有如下 1. 比较常见的指定顺序搜索，避免重复 2. 对于当前深度 dep , 如果剩余点数与之相加都不能更新 ans ，就剪枝 3. dp 优化，用dp记录之前搜索得到的最大团数量，如无法更新ans，剪枝。 下面有两个入门 板子 题 HDU 1530 Maximum Clique 题意： 最大团的裸题。给你邻接矩阵，让你求最大团的点数。 思路： 套一套模板就行啦…… AC Code #include #include…