昨天坐了一天的火车,在火车上看了点并查集,但有一题还没看懂,火车还晚点了,回来收拾完东西感觉累了,就睡觉了,并查集和字典树想好好做做的,但前几天的poj崩了,好吧,还是自己懒,现在也回学校了,得好好补了。
字典树,字典树要弄懂原理,不然稍微变一题就不会了,还要根据题目灵活变通,直接套模板的题也没意思,这里就需要数学思维了,就比如01字典树的异或问题,字典树的模板动态省内存,数组省时间。
并查集,普通的套一个模板,难点在于进阶并查集,以前还真刷了不少题,现在要都拾回来,next数组优化时间只是个小问题,难点在于种类并查集,还需要好好深入。
图的连通性,分为两类,有向图的强连图分量和无向图的桥与割点和双连通分量,现在只会做一些模板题,有些结论是真的不知道怎么证明,多积累把