2015-01-08阅读(6273)评论(0)

POJ 2987 Firing 大裁员：公司官僚成风，盘根错节，办实事的码农没几个。老板决定大裁员，每开除一个人，同时要将其下属一并开除，如果该下属还有下属，照斩不误。给出每个人的贡献值和从属关系，求最小裁员数及最大贡献值和。 3.5借助水...

2015-01-01阅读(5221)评论(0)

POJ 3713 Transferring Sylla 三连通图：判断一个无向图是否三连通？ 3.5借助水流解决问题的网络流 最大流 刷个题报平安，果然无论是主观还是客观我都闲不下来，明天加班！ 三连通图指的是去掉3个点就不连通的图，但是并...

2014-12-23阅读(30370)评论(32)

本文使用Double Array Trie实现了一个性能极高的Aho Corasick自动机，应用于分词可以取得1400万字每秒，约合27MB/s的分词速度。其中词典为150万词，构建耗时1801 ms。以前就在构想将AC自动机与双数组Tr...

2014-12-15阅读(4987)评论(0)

POJ 3171 Cleaning Shifts 铲屎官：约翰希望在时间[M,E]内保持牛舍始终有牛在打扫，有N头牛分别愿意在时间[T1,T2]内打扫并收工钱S。求最小花费。 3.4熟练掌握动态规划 利用数据结构高效求解 是POJ 2376...

2014-12-12阅读(5233)评论(1)

POJ 3735 Training little cats 调教猫咪：有n只饥渴的猫咪，现有一组羞耻Play，由k个操作组成，全部选自： 1. g i 给第i只猫咪一颗花生 2. e i 让第i只猫咪吃光它的花生 3. s i j 交换猫咪...

2014-11-24阅读(5618)评论(2)

POJ 3420 Quad Tiling 贴瓷砖：4*N的地板上用2*1的瓷砖铺满，求所有方案数对M求余。 3.4熟练掌握动态规划 矩阵的幂 久违地上了节课，太无聊，只好刷一题。 假设S[n]表示填满n时的方案数，有S[0]=1。定义矩阵 ...

2014-11-07阅读(11862)评论(1)

前言 以前HanLP使用“最短编辑距离”来做推荐器，效果有待提高，主要缺点是根据拼音序列的编辑距离推荐的时候，同音字交错很常见，而编辑距离却不那么大。这时我就在寻求一种补充的评分算法，去评判两个句子在拼音这一维度上的相似程度。 最终决定导入...

2014-11-01阅读(19607)评论(5)

简介 Aho-Corasick算法简称AC算法，通过将模式串预处理为确定有限状态自动机，扫描文本一遍就能结束。其复杂度为O(n)，即与模式串的数量和长度无关。 思想 自动机按照文本字符顺序，接受字符，并发生状态转移。这些状态缓存了“按照字符...

2014-10-26阅读(5001)评论(0)

POJ 3411 Paid Roads 开路：N个城市间有m条单向路，分别从a到b，可以在c处交P路费，也可以直接交R路费。那么问题来了，你的挖掘机怎么开最省钱？ 3.4熟练掌握动态规划 状态压缩DP 乍一看可以Dijkstra，实际上的确...

2014-09-28阅读(5235)评论(0)

POJ 1795 DNA Laboratory DNA拼接：弗兰肯斯坦从尸体里提取了一堆DNA碎片，想拼成字典序最小的整体，于是他找了几个实习生，你就是其中一个。 3.4熟练掌握动态规划 状态压缩DP 首先，如果一个字串包含在另一个母串中，...