CFGYM102394L CCPC2019哈尔滨 L题 LRU Algorithm

首先做法很简单:令缓存大小为n,然后直接把操作模拟一遍,后期如果我们限制了缓存大小为x,那就等价于取我们在模拟时长度为x的前缀。

然后我们显然可以把前缀哈希算一算,插到std::unordered_map里,然后成功TLE。

然后我们考虑另一个做法:把询问插到字典树里,仍然对操作进行模拟,每模拟一次后,在字典树上把序列走一遍,并标记对应的询问为Yes。

但是有几个地方要注意

  • 一个点可能对应多个询问,所以用一个vector来挂询问吧。
  • 一组询问在去除后缀0之后可能长度为0,此时询问是被挂在根上的,务必进行处理,否则WA!

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据