2017年02月的文章

题解《挑战程序设计竞赛》系列完结

2017-02-13阅读(9033)评论(8)

断断续续花了三年时间，终于看完这本书，完成了所有习题。看书有很多种看法，开卷有益是一种，自始至终是另一种。有些题目很难，至今AC数只有数十人。据此估计，完整读完这本书的人应该不超过十这个量级。读书的动机也有很多种，我既不是运动员，也不为面...

2017-02-12阅读(6127)评论(0)

Codeforces 123D String 子串函数和：求字符串的所有子串出现次数n代入n(n+1)/2之和。 4.7华丽地处理字符串后缀数组题目有些绕，直白地讲就是枚举所有不同的子串，求出现次数，...

2017-02-11阅读(5532)评论(0)

AOJ 2292 Common Palindromes 公共回文子串：求两个串的公共回文子串个数。 4.7华丽地处理字符串后缀数组拼接后先预处理出后缀数组、高度数组和回文半径数组。其中，每个位置的回文...

2017-02-10阅读(5237)评论(0)

POJ 3729 Facer’s string 公共子串：给出两个字符串A,B,求满足下列条件的C的个数: C是A的子串 C也是B的子串 C加上其在A中的后继字符(若在最尾则加上空格字符)不能够在B中出现 4.7华丽地处理字符...

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

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

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

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

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

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

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

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

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

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

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

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