单词检索晚题解新.pdfVIP

单词检索

算法一：

算法：随便你怎么做啦！

期望得分：20分。

算法二：

拿60分应该有不少方法吧！

算法之一：枚举+KMP

22

枚举单词O(N)，匹配O(N)

4

时间复杂度：O(N)，期望得分：60分。

算法三：

Hash（开散列），详见程序

计算出所有字符串的Hash值。

时间复杂度：O(N*L)，期望得分：100分。

无聊的游戏

算法一：

x

这里的分数2本质上就是全涂黑的行列的集合的子集数目，所以给定一个全涂黑的

行集合R和列集合C，和这些行和列被涂黑的概率，那么答案可以表示为

answer=p，由于R，C集合大小相同的p也相同，所以它们可以放在一起算，

R,CR,C

R,C

nn

rc

设R=r,C=c，这里用q来表示p，所以答案还可以表示为answer=CCq，

r,cR,Cnnr,c

r=0c=0

Ck−t

m−t

这里qr,c十分好求为k，这里t=n(r+c)-rc为整行、列填黑的格子个数。

C

m

2

时间复杂度O(n)，期望得分：100分

算法二：

m≤10，实际上n≤3，于是可以枚举所有的填法和选法。

22

nn

时间复杂度O(C*2)，期望得分：30分

m

算法三：

n≤10，于是可以枚举所有选行的可能，再用算法一的方法算。

时间复杂度O(22n)，期望得分60分。

圣诞树