zcmimi's blog

arrow_backtrie共4篇文章

avatar
zc
2020-10-13 21:01:06

查看原题

点击跳转

首先将所有RNA序列插入trie

然后用病毒模版片段trie上搜索

对于?,可以匹配任意一种

对于*,可以选择

  1. 不匹配,*当作没有
  2. 匹配,下一个停止用*匹配
  3. 匹配,下一个继续用*匹配
avatar
zc
2020-03-01 00:37:00
查看原题

点击跳转

题意:

给一棵trie树,可以删掉某一层的所有边

求删掉哪一层边后合并出的trie树最小?

解法:

trie的启发式合并

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

先求个异或前缀和,然后就变成求k对最大异或和

因为(i^j) = (j^i)

所以我们设2k对,到答案在除以2就可以了

我们先找出每个点能得到的最大异或和,然后放堆里

每次取出堆顶,求出它能得到的第rk+1大的异或和

如果rk+1 \le n,那就放到堆里

(因为一个点最多用n次,要不就重复了)

记得long\ long

avatar
zc
2019-12-21 19:47:00
查看原题

点击跳转

考虑如何快速找出拥有(与它的前缀相同的)后缀的串。这个东西可以通过把字符串放到Trie里面。 分类两种情况,短串+长串长串+短串。对于短串+长串的情况,先将字符串按len排序,然后顺序将字符串倒着插入trie里面,并在trie中的尾节点记录hash。利用当前串作为查询串来找答案,这样能保证当前串一定是长串,并且找到的所有短串都有和它的前缀相同的后缀,所以再利用hash判断一下就可以确定拼出来的是不是回文串了。另外一个情况同理。 复杂度是O(26\sum len)

1/1
Search
search