2019.8.18 集训解题报告

又一次考试前一个小时开始写解题报告…. qwq

2019.8.13 集训解题报告

为什么我觉得今天的题这么水,恐怕要被打脸 qwq,是不是我题读错了….

  • 打个广告:$Blog$
  • 翻了所有的题解,发现竟然没有用$Trie$字典树做的,那我就来一发。
  • $Trie$字典树的复杂度对于这道题来说还行,刚好卡的过去,我只是提供一种思路,泥萌最好还是用哈希表。
  • 计算复杂度:
    • 数字长度$\leq 32$,数字总数$\leq 50000$,数据组数$\leq 50$
    • 最坏所有数字都不一样,一组数据共建树结点次数:$32 \times 50000 = 1600000 = 1.6 \times 10^6$。
    • $50$组数据:$1.6 \times 10^6 \times 50 = 8 \times 10^7$
  • 所以说可以刚刚好卡过了。
  • 算法:
    • 每读入一个数,就添加到字典树中,到最后一个结点发现不存在时,输出这个数;存在时,不输出这个数。以达到去重效果。

2019.3.3高中部集训

知识清单

  • $KMP$
  • $Trie$字典树
  • $AC$自动机
  • 哈希$(Hash)$

笔记

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×