当前位置:网站首页>学习日记9

学习日记9

2022-08-10 12:52:00 51CTO


       今天上午,做了一道bfs结合最小生成树的题,这道题在思考上不是很难,把两种算法结合起来,就是有点麻烦,最重要的是这道题的输入比较坑,提交很多次都没ac,就是因为输入。这道题是一道迷宫类的题,迷宫里有很多外星人,要在最短的时间内消灭所有外星人,和以前做的走到出口的迷宫不一样,这道题的做题思路大约是,用bfs()求出所有点(包括S和所有A)之间的最短距离,再用prim最小生成树求出最短路的距离。这个题的输入非常坑,错了几次都是在那里,首先在输入地图前,有一个换行符,在输入数据中间后面还有空格,我用getchar()试过,是wr,所以就换了一个方法,在输入玩地图大小后,在后面加一个换行符,这是在一个题解上查到的一个方法。

     今天下午又深入学习了一下位运算,位运算是速度很快,在某些时候有用,但暂时我还没遇到这种题。还看了一下单调队列,通过各种知识学习了一下,单调队列是一种不太常用的编程方法,但是如果用到它,解题会变得简单许多。看名字就知道,单调队列是一种单调递增或单调递减的队列。并且,这种队列只能从队尾添加元素,能从队首和队尾读取元素,它插入元素的方法比较特别,如果是递增队列,则从队尾开始遇到比要插入元素大的,就把队尾元素删除,否则就把要插入的元素放到队尾。一般用单调队列很容易求最小值和最大值,一般队首就是最小值和最大值,所以要读取的值一般是队首。

    但是这只是一般情况,有些题目的单调队列根据题目需要,还有单调非递减,单调非递增队列。等等,还有很多变形,在我刚看了这几道题目里,就发现了不是有意思的变形,变形归变形,它的核心代码,核心优化是不会变得。

     明天就要开始复习二分,并且做二分和队列的题了,希望明天对二分和单调队列有更深的认识,做题更快。

原网站

版权声明
本文为[51CTO]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15747246/5563381