最短Hamilton路径 发表于 2019-08-01 | 分类于 算法竞赛进阶指南 | 问题给定一张 n 个点的带权无向图,点从 0~n-1 标号,求起点 0 到终点 n-1 的最短Hamilton路径。 Hamilton路径的定义是从 0 到 n-1 不重不漏地经过每个点恰好一次。 阅读全文 »
最佳牛围栏 发表于 2019-05-05 | 分类于 算法竞赛进阶指南 | 问题农夫约翰的农场由N块田地组成,每块地里都有一定数量的牛,其数量不会少于1头,也不会超过2000头。约翰希望用围栏将一部分连续的田地围起来,并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。围起区域内至少需要包含F块地,其中F会在输入中给出。在给定条件下,计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。 阅读全文 »
最高的牛 发表于 2019-05-02 | 分类于 算法竞赛进阶指南 | 问题有N头牛站成一行,被编队为1、2、3…N,每头牛的身高都为整数。当且仅当两头牛中间的牛身高都比它们矮时,两头牛方可看到对方。现在,我们只知道其中最高的牛是第P头,它的身高是H,剩余牛的身高未知。 但是,我们还知道这群牛之中存在着M对关系,每对关系都指明了某两头牛A和B可以相互看见。求每头牛的身高的最大可能值是多少。 阅读全文 »
密码破解 发表于 2019-04-28 | 分类于 算法竞赛进阶指南 | 问题小王的保险箱密码是一个升序排列的数字串,小王对密码进行加密。流程如下: 1.数字用英文单词代替 2.加密算法会按照某种规则改变原字符串中字符的排列顺序,同时还会改变某些字符的大小写。 该加密算法存在漏洞,即使不知道具体实现细节,也可还原出原始密码。写一段程序来破解小王的密码。 阅读全文 »