hankcs
上海 松江区

加关注

【题解《挑战程序设计竞赛》系列完结】断断续续花了三年时间,终于看完这本书,完成了所有习题。看书有很多种看法,开卷有益是一种,自始至终是另一种。有些题目很难,至今AC数只有数十人。据此估计,完整读完这本书的人应该不超过十这…http://t.cn/RJaCbBY ​

2月13日 02:26转发|评论

【Codeforces 123D String 题解《挑战程序设计竞赛》】子串函数和:求字符串的所有子串出现次数n代入n(n+1)/2之和。4.7华丽地处理字符串 后缀数组 题目有些绕,直白地讲就是枚举所有不同的子串,求出现次数,代入该表达式求和。枚举子串的通用做法是,高度数组…http://t.cn/RJ60yj4 ​

2月12日 13:39转发|评论

【AOJ 2292 Common Palindromes 题解《挑战程序设计竞赛》】公共回文子串:求两个串的公共回文子串个数。4.7华丽地处理字符串 后缀数组 拼接后先预处理出后缀数组、高度数组和回文半径数组。其中,每个位置的回文半径用Manacher算法线性时间求出。定义a[…http://t.cn/RJMxDv8 ​

2月11日 12:58转发|评论

【POJ 3729 Facer’s string 题解《挑战程序设计竞赛》】公共子串:给出两个字符串A,B,求满足下列条件的C的个数:C是A的子串C也是B的子串C加上其在A中的后继字符(若在最尾则加上空格字符)不能够在B中出现4.7华丽地处理字符串 后缀数组 将A和B拼接后,l…http://t.cn/RJc3nJO ​

2月10日 14:29转发|评论

【POJ 3415 Common Substrings 题解《挑战程序设计竞赛》】公共子串:统计A和B长度不小于K的公共子串个数。4.7华丽地处理字符串 后缀数组 将A和B拼接后,累计分属两者的后缀对应的LCP-K+1即为答案,但穷举不是个好主意。如果能快速求出任意两个后缀的最…http://t.cn/RJq9wwW ​

2月9日 13:56转发|评论

【POJ 1509 Glass Beads 题解《挑战程序设计竞赛》】降临:在电影《降临》中,七肢桶使用了一种环形语言。给定一个环状字符串,求从哪个字符断开并反转后得到的字符串字典序最小?4.7华丽地处理字符串 后缀数组 将环切断相当于将序列分割为两段再分别反转拼接,可以看做是…http://t.cn/RJ4UIcT ​

2月8日 13:04转发|评论

【AOJ 1312 Where's Wally 题解《挑战程序设计竞赛》】找茬:从大图中找出特定方块小图,旋转翻转皆可。4.7华丽地处理字符串 字符串匹配 利用循环哈希法计算大图中所有与小图大小一致的子阵的哈希值。小图旋转有4种变换,乘以翻转等于8种。先预处理出小图的哈希值,然…http://t.cn/RJ2xVlK ​

2月7日 11:16转发|评论

【Codeforces 25E Test 题解《挑战程序设计竞赛》】出题:众所周知,程序竞赛测试数据越变态越好玩。已知3个字符串会使选手的程序出错,出题者想构造一个超级变态数据同时包含这3个字符串。求该母串最小长度。4.7华丽地处理字符串 字符串匹配 利用滚动哈希法可以快速预处…http://t.cn/RJzRCyX ​

2月6日 11:48转发|评论

【Codeforces 86C Genetic engineering 题解《挑战程序设计竞赛》】基因工程:给定m个子串,求构造长n的母串的方案数。母串中每个字符都至少来自一个子串。4.7华丽地处理字符串 动态规划算法 用AC自动机(后缀树)维护子串,处理出每个节点的最长后缀模…http://t.cn/RJP3aUb ​

2月5日 13:43转发|评论

【AOJ 2212 Stolen Jewel 题解《挑战程序设计竞赛》】夺宝奇兵:某国国宝失窃,你千辛万苦追回珍宝,正准备上交给国家时,却被怀疑是赝品。为了鉴别真伪,需要将宝石放到迷宫的魔法阵中。但迷宫中有特殊机关,不允许特定的移动模式。如下图的移动方式是错误的而下图才是正确的…http://t.cn/RxFQYPX ​

2月4日 13:14转发|评论

【SPOJ QTREE5 Query on a tree V 题解《挑战程序设计竞赛》】染色:给定一颗黑白树,请快速执行①将给定节点颜色翻转②求给定节点到最近的白色节点距离。4.6划分、解决、合并:分治法 树上的分治法 重心分解后,对每个子树root维护一个优先队列que,维护…http://t.cn/RxehlYZ ​

2月3日 14:05转发|评论

【UVa 12161 Ironman Race in Treeland 题解《挑战程序设计竞赛》】赛车:给定一颗树及各边长度及花费,请计算花费在m以内的最长路径。4.6划分、解决、合并:分治法 树上的分治法 不断根据重心分割子树,将通过子树根节点的路径记录到path中。记已经处…http://t.cn/Rx14j7A ​

2月2日 13:41转发|评论

【Michael Collins NLP公开课任务3 机器翻译】说是机器翻译,其实只涉及最最简单的两个模型:IBM1和2以及启发式改进,用来做文本对齐。文本对齐文本对齐是这么一个问题,将母语翻译为外语时,给定一个长l的母语句子和长度m,估计一个长m的外语句子及后者到前者的对齐方…http://t.cn/Rxncvot ​

2月1日 12:30转发|评论

【POJ 2114 Boatherds 题解《挑战程序设计竞赛》】漂流:给定一颗树及各边长度,请快速查询是否有距离为k的顶点对。4.6划分、解决、合并:分治法 树上的分治法 与POJ1741类似只需将“不超过k”改为“不超过k减去小于k”,就可以得到“等于k”的数量了。int …http://t.cn/RxQ5qmF ​

1月31日 07:45转发|评论

【Codeforces 97B Superset 题解《挑战程序设计竞赛》】Codeforces 97B Superset 点集:给定n个点,请添加一些点,使任意两点满足①在同一条水平线或竖直线上②或构成一个矩形框住其他点。4.6划分、解决、合并:分治法 平面上的分治法 从子问…http://t.cn/RxOgYM6 ​

1月29日 11:30转发|评论

【GCJ 2009 World Finals B:Min Perimeter 题解《挑战程序设计竞赛》】极小三角:从n个点中找出3个,使其形成的三角形周长最小。4.6划分、解决、合并:分治法 平面上的分治法 不断地用垂直分割线把所有点按x坐标分为左右两半,那么极小三角形的顶点无…http://t.cn/RxCRf13 ​

1月28日 12:55转发|评论

【POJ 1854 Evil Straw Warts Live 题解《挑战程序设计竞赛》】POJ 1854 Evil Straw Warts Live 文字游戏:求通过交换相邻字符使某字符串成为回文的最小步数。4.6划分、解决、合并:分治法 数列上的分治法 判断是否能组成回文的…http://t.cn/RxJOiDx ​

1月27日 12:06转发|评论

【UVa 10181 15-Puzzle Problem 题解《挑战程序设计竞赛》】UVa 10181 15-Puzzle Problem 滑动拼图:给定拼图,求解决方案。4.5开动脑筋智慧搜索 A*与IDA* 滑块拼图问题是否有解的判断方法是,先将表格平铺:然后计算N=逆序数…http://t.cn/RxVxmEp ​

1月26日 12:18转发|评论

【POJ 2032 Square Carpets 题解《挑战程序设计竞赛》】POJ 2032 Square Carpets 铺地毯:用最少的正方形覆盖所有点。4.5开动脑筋智慧搜索 A*与IDA* 大致思路是预处理出一个覆盖所有点的正方形集合,最优解下界为所有点恰好构成最大正方…http://t.cn/RxGnCsV ​

1月25日 13:13转发|评论

【POJ 3523 The Morning after Halloween 题解《挑战程序设计竞赛》】POJ 3523 The Morning after Halloween 万圣节惊魂夜:万圣节过后,鬼屋里的幽灵们到处乱窜!给定它们的位置和地图,按照如下规则移动:①每个鬼都不…http://t.cn/RxUcCyT ​

1月24日 14:05转发|评论