常用图论的邻接表时,我们都用h储存每个节点的头结点下一个点,然而如果有多组案例,我们每次都要memset成-1。
昨天Ec Final遇到一个有意思的bug,一共T组数据,总结点不超过1e6个,我当时就想1e6我岂不是随便写吗。结果写完之后超时了,我总共才用了O(n) 的时间复杂度 它居然超时了????
到后来发现 一共T组数据,T的范围是1e5, 我每次都memset一下 , memset的时间复杂度是整个数组的长度。是O(N) 不是O(n) 所以我开的数据1e5 再memset 1e5次它就超时了。
然后把所有memset都写成了for循环之后 时间复杂度就过了。
总结,下次看题不能只单单看输入的数据的范围,还要注意案例有多少。
看到你的头像,我承认我恍惚了。。。。。doge
hhh