83训练日记

it2024-08-12  64

今天看的是拓扑排序,刚开始看的时候,我觉得这个排序拍的是节点的位置,大概是节点距离根节点越近,就越排在前面。后来看了代码,跟广搜有点像,先是存储到一个队列中,然后一个个取出来,不同的是这里的数字不是找到它链接的节点后直接放入队列,而是将这些节点的入度减去1(入度就是有几条线通向它),直到有节点入度减为0,他才会被放入一个序列中,称为排序好了的数列。

后来又看了会深搜,深搜没什么好说哒,都是一些例题,看完递归再看这里,就能感受到一股非常强烈的联系,有时候都会觉得,其实搜索就是递归的吧?

最后的一点时间,看完了剪枝,剪枝看的不是很仔细,因为剪枝这个东西不是我想剪就能剪掉的啊!每一次的超时,我都有绞尽脑汁的思考,如何剪枝,可是情况一般不如意……

我认为,在循环里面用剪枝的作用小之又小,一半没什么屁用,该在哪超时,就在哪超时,用在深搜里面好像看起来有用的多,碰见不符合题意的、一看就知道这种情况不是最优的、已经遍历过一遍的情况下,一个return能省下好多时间,相反的,循环里面的超时,还是换方法,或者巧用前缀和、记录状态比较好啦。

说起前缀和呀,今晚的题目我好不容易居然想到可以用前缀和的!!我奋力的用前缀和记录下来了到达某个数字(当然是1~1e6这个区间)所有1~i会出现几个素数!然鹅,天不遂人意,果然该做不出来还是做不出来……啊,想了好久不知道哪里出了问题,一直输出-1,我也是没有办法啊,而且求素数那里……咳咳咳,感觉还是会超时,嗯,就算想破我的脑袋,我都想不到还能怎么办啊!素数难道还有更省时间的函数吗!!!

查找那里我用的遍历,确实不是很巧妙,用二分应该好一点,但是二分我也不是很熟……代码还是写的少了,模板都用不熟,默默嫌弃自己一秒钟。明天是久违的周末啊!!可以睡懒觉了!呜,感动,最近一直有点贪玩,害得我大晚上都要加班看点书,周末要是每人约我出去玩,不会也要加班吧??(我应该不会这么勤快?)总之,还是希望有人约我的!求约!拒绝死肥宅从我做起!

 

最新回复(0)