hiho一下第170周《Word Construction》题目分析

3
0

《Word Construction》题目分析

本题是一道比较基础的深度优先搜索题目。

猛一看这道题可能会感觉复杂度很高,暴搜会超时。因为有N个单词,每个单词都可能选或不选,一共有2^N中可能。N=40的时候这个数值非常大。

不过仔细分析题目中给出的单词就可以发现,除了by和my,所有单词都至少包含aeiou之中的一个字母。

由于题目要求选出的不同单词不能包含相同的字母,所以实际上我们最多选出6个单词:5个单词分别包含aeiou,再加上by或者my之中的一个。

这样以来复杂度就降为O(N^5),基本可以暴搜解决了。(实际上"不能包含相同的字母"这个剪枝条件很强,合法的组合远远小于O(N^5))。

当然我们还可以增加一些降低复杂度的优化。例如先对单词集合预处理一遍,剔除明显不够"优"的单词。例如,如果同时有单词i和it,那显然选it不如选i好,所以我们完全可以将it剔除出单词集合。

4 answer(s)

1

弱弱的问一下,用“最大独立集”来求解,是不是想多了。

  • 其实这题也就是个最大独立集问题。

  • 添加评论
  • reply
0

我的做法不太一样,我用vis[i][j]=1表示第i个字符串在第j个字符串有字符相同,cnt[i]记录Σvis[i][j],再对cnt[i]排序,最后贪心做一遍....

  • 用你的方法a了这个题目哈哈,感谢哦~感觉本质好像就是最大独立集的解法,就是把度最大的点从集合中删掉~直到最后剩下都是单独的点

  • 添加评论
  • reply
1

特别说明一下一般图上的最大独立集是NP问题,贪心是有反例的。

1)第一种贪心,把点按度排序之后从小到大依次尝试加入独立集。
反例是下面的图
w是一个点,与xyz相连,度是3。
A是一个包含N个点的完全图。A中每个点都与xyz相连。A中的每个点度都是N+2。
xyz三个点的度都是N+1。

          w
      /   |   \
     x    y    z  
       \  |   /
          A

从小到大的贪心会一开始就把w加入独立集,这时xyz都不能加入,只能再从A中选一个点加入,求得的集合大小是2。显然不是最大的,最大的应该是{x, y, z}。

2)第二种贪心是把度最大的点从集合中删掉,直到剩下的点互相独立。
反例是下面的图
A是一个包含N个点的完全图。A中每个点都与xyz相连。A中的每个点度都是N+2。
B也是一个包含N个点的完全图。B中每个点都与xyz相连。B中的每个点度都是N+2。
xyz三个点与A和B中的每个点都相连,xyz度都是2N。

          B
      /   |   \
     x    y    z  
       \  |   /
          A

贪心算法一开始就会把xyz都删除,最终会留下A中的一个点和B中的一个点,集合大小位2。显然也不是最优的,{x, y, z}才是最大独立集。

本题由于条件限制,两点之间连边当且仅当两个单词有相同字母,所以贪心的反例不太好构造
┑( ̄Д  ̄)┍

有谁构造出的话,欢迎提供~

0

补充一个无关紧要的事…… TOP 100 words其实只有99个…… 调试了半天

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


转发分享