hihoCoder太阁最新面经算法竞赛5题解

2
0

Problem 1

修改后的有序01串一共只有|S|+1种可能情况。我们可以枚举最后的有序01串,那么就可以通过逐位比较计算出需要修改的字符数目。复杂度O(N^2)。

如果我们通过预处理,计算出初始01串的每个前缀和后缀分别有多少个0,多少个1。那么我们就不用O(N)的逐位比较,可以直接计算出需要修改的字符数目。

Problem 2

贪心。首先我们需要分析INVALID的充分必要条件。容易看出充要条件是S中某个字符的数目超过了(|S|+1)/2。

于是我们可以采用贪心策略来找到字典序最小的解:对于输入的S,首先判断是否INVALID。如果不是INVALID,我们按照'a'-'z'的顺序枚举第一个字符c,如果除去c之后,S的剩余的字符仍然不是INVALID,那么我们就把第一个字符定为c。这样依次确定每一位即可。

Problem 3

宽度优先搜索。这类题目的关键在于状态的设计。就本题来说,我们需要把当前获得了哪些钥匙也表示进状态里。具体来说,当前状态是一个三元组(x, y, keys),表示小Hi在(x, y)这个位置,获得的钥匙集合是keys。 钥匙最多有5把,所以一共有2^5种可能。再加上100 x 100的位置状态,一共有320000种状态。

需要注意的是一些特殊情况的处理。比如钥匙在上锁的房间里,出口在上锁的房间等。

1 answer(s)

0

哪位大神能把第三题的源代码发给我一份吗?想研究一下,先谢过了。我的邮箱:954371544@qq.com

  • 比赛结束之后在排名页面是能看到别人代码的 点击分数即可

  • 嗯嗯,明白了!这种设定真是太方便了!

  • 添加评论
  • reply

write answer 切换为英文 切换为中文


转发分享