看到长度为1的或网格图求最短路径要想到BFS,观察题目是否需要记录一些特殊的状态进行BFS,类似拯救大兵瑞恩
最近又碰到一题类似的但是又不一样的题, 🔗 ABC 301 E
这一题咋一看好像可以用类似拯救大兵瑞恩那题的方法,但是仔细一分析BFS需要记录的状态数为300 * 300 * 2^18,显然是不符合时间复杂度和空间复杂度的,接下来思维的难点就是在我们不需要考虑那些空地,我们只需要考虑一个糖果到另一堆糖果之间的距离和到目的地的距离,我们只需要把糖果所在的坐标和起点终点一起放入一个集合建图即可。然后就类似最短哈密顿路径,相当于从起点到终点,每个糖果只经过一次的最短路径,用状压dp即可求出
2023/5/21
ABC 302 F Merge Set
每个集合里面有不重复的数字,两个集合AB只要有相同的数字就可以那么A集合就能走到B集合,如何建图呢?开始我想着是直接暴力把集合之间的边建出来,但是复杂度太高了。后来发现可以集合本身可以代表一个点,里面的数字也代表一个点,然后建图,算最后距离的时候长度除2再减1就是答案了
2023/5/28
105双周赛T4
继续学习一下建图,把数组下标当作每一个点,然后再对当前数的质数连接边,然后可以使用并查集、dfs等判断联通性。有一个小技巧,可以通过埃氏筛预处理出每个数的质因数,这样就不会超时。不能先把质数求出来,然后用所求数 % 质数 == 0这种做法,会超时。
2023/5/31
记录一下在C+ +学习中遇到的一些坑,map在循环中删除的时候,因为erase(迭代器)后,迭代器的指向就是没有意义的,这时候迭代器++毫无意义,所以要预先存下要删除的迭代器再删除。
2023/6/4
在set中假设有[1, 2, 3, 4 ,5, 6],那么如果我们想找到4的前驱该怎么找?
//这里有两种方法,第一种写法是我找到的
auto it = --set.lower_bound(4);
//第二种是看到别人代码中写的,同时我也在网上找到了相关的还有next方法的使用方法
auto it = prev(set.lower_bound(4));