三 24
很容易看出来是求二分图的最佳匹配(最大权完备匹配)，直接用KM算法解决。
建图的过程中要注意细节，判断两人之间不能有第三者，距离小于等于射程。用向量共线的判定即可。
三 21
NOI2001的题目是[反正切函数的应用][聪明的打字员][陨石的秘密][食物链][炮兵阵地][方程的解数]。
其中[反正切函数的应用][聪明的打字员]较为简单，[陨石的秘密][食物链][炮兵阵地][方程的解数]稍有难度。
[反正切函数的应用]是一个求函数最值的问题，要配合数学知识解决。[聪明的打字员]是广度优先搜索问题。[陨石的秘密]是一个树形动态规划的问题，需要仔细思考。[食物链]用到了并差集。[ 炮兵阵地]是个不易看出的动态规划问题。[方程的解数]是搜索问题，需要用哈希表来优化。
三 12
NOI2000的题目是[瓷片项链][单词查找树][青蛙过河][程序分析器][古城之谜][算符破译]。[瓷片项链][单词查找树][青蛙过河][程序分析器]都是简单题，[古城之谜]难度一般，[算符破译]是较难。
[瓷片项链]是简单的二次函数求最值的问题，数学方法可以直接解决。[单词查找树]是一种基本的字符串处理的数据结构。[青蛙过河]是一个递归的数学问题，可以求出直接的公式。[程序分析器]是个模拟题，需要细心。[古城之谜]是个动态规划问题，但是需要对题意尤其是对范式的深入分析。[算符破译]是个较难的搜索题，需要大量剪枝和优化。
Read the rest of this entry »
一 05
这是一个经典的求多个串的最长公共子串的问题。如果设字符串的个数为N，每个串最大的长度为L，则这道题有时间复杂度为O(N*L^4),O(N*L^3),O(N*L^2)和O(N*L)的算法。
最简单的想法是对于某一个串，取出它的所有的L^2个子串，然后再在其他每一个字符串中进行朴素的匹配，很显然是O(N*L^4)。如果生搬硬套地用KMP，那么是O(N*L^3)的算法。仔细一想，其实枚举所有的L^2个子串是完全没有必要的，仅仅取出某一个串的L个后缀，对于每一个后缀在其他的所有串中部分匹配即可，用朴素匹配就是O(N*L^3)，用KMP就是O(N*L^2)，可以通过所有测试点。
另外，如果用Trie，把每个串的所有后缀全部插入Trie树中，标记每个节点所属的原串。找到最深的属于所有串的节点，它的最大深度就是最长公共前缀，时间复杂度依然是O(N*L^2)，但是会有一点超时。
对于这道题来说，对某个串的每个后缀进行部分模式匹配，O(N*L^2)的算法就可以了。如果想进一步探究，恐怕就要用到后缀树了，广义后缀树求最长公共子串有O(N*L)的算法，我还没有学过，现在正在苦读中。
下面是我的O(N*L^2)的KMP。
Recent Comments