码农场

2017-02-09阅读(5930)评论(0)

POJ 3415 Common Substrings  公共子串：统计A和B长度不小于K的公共子串个数。 4.7华丽地处理字符串  后缀数组  将A和B拼接后，累计分属两者的后缀对应的LCP-K+1即为答案，但...

2017-02-08阅读(5320)评论(0)

POJ 1509 Glass Beads  降临：在电影《降临》中，七肢桶使用了一种环形语言。给定一个环状字符串，求从哪个字符断开并反转后得到的字符串字典序最小？ 4.7华丽地处理字符串  后缀数组  将环切断...

2017-02-07阅读(5168)评论(0)

AOJ 1312 Where's Wally  找茬：从大图中找出特定方块小图，旋转翻转皆可。 4.7华丽地处理字符串  字符串匹配  利用循环哈希法计算大图中所有与小图大小一致的子阵的哈希值。 小图旋...

2017-02-06阅读(4809)评论(0)

Codeforces 25E Test  出题：众所周知，程序竞赛测试数据越变态越好玩。已知3个字符串会使选手的程序出错，出题者想构造一个超级变态数据同时包含这3个字符串。求该母串最小长度。 4.7华丽地处理字符串  字...

2017-02-05阅读(5139)评论(0)

Codeforces 86C Genetic engineering  基因工程：给定m个子串，求构造长n的母串的方案数。母串中每个字符都至少来自一个子串。 4.7华丽地处理字符串  动态规划算法  用AC自动...

2017-02-04阅读(3244)评论(0)

AOJ 2212 Stolen Jewel  夺宝奇兵：某国国宝失窃，你千辛万苦追回珍宝，正准备上交给国家时，却被怀疑是赝品。为了鉴别真伪，需要将宝石放到迷宫的魔法阵中。但迷宫中有特殊机关，不允许特定的移动模式。如下图的移动方式是...

2017-02-03阅读(3086)评论(0)

SPOJ QTREE5 Query on a tree V  染色：给定一颗黑白树，请快速执行①将给定节点颜色翻转②求给定节点到最近的白色节点距离。 4.6划分、解决、合并：分治法  树上的分治法  重心分解后...

2017-02-02阅读(3131)评论(4)

UVa 12161 Ironman Race in Treeland  赛车：给定一颗树及各边长度及花费，请计算花费在m以内的最长路径。 4.6划分、解决、合并：分治法  树上的分治法  不断根据重心分割子树，...

2017-02-01阅读(5195)评论(0)

说是机器翻译，其实只涉及最最简单的两个模型：IBM1和2以及启发式改进，用来做文本对齐。代码见文末，包括附加题在内全部达到了预期目标。 文本对齐 文本对齐是这么一个问题，将母语翻译为外语时，给定一个长l的母语句子和长度m，估计一个长m的外语...

2017-01-31阅读(3146)评论(0)

POJ 2114 Boatherds  漂流：给定一颗树及各边长度，请快速查询是否有距离为k的顶点对。 4.6划分、解决、合并：分治法  树上的分治法  与POJ1741类似 只需将“不超过k”改为“不超过k减...