首页 > 其他分享 >P1032

P1032

时间:2023-09-24 12:45:41浏览次数:42  
标签:map P1032 算法 bfs 插入 range out

写这道不算难的题目是我遇到了不少问题,复述以下过程吧。
由于数据很水,这道题用不到KMP算法,只要使用朴素算法进行字符串比对就可以了。
首先,我错误的选择了dfs算法,导致了TLE的发生。这类求最优解的问题显然大多应该用bfs解决。
其次,我忘了考虑如果一个字符串多处都可以用同一规则替换,那么各处替换都应该考虑到的这一问题。最开始我都是只替换第一处的。后来意识到这一问题是我刚开始觉得如果每一处都有换和不换两种情况且有n处可换的话,我岂不是应该把2的n次方个元素插入队列?这样实现起来好麻烦,又不如深搜了。后来我意识到我并不需要插入2
的n次方个元素,我只需要插入n个就可以了,即分别是“第一处改其他都不改”、“第二处改其他都不改”、...、等等。因为那种”“第xy处改”的情况其实当只有第x处改的那个入队的元素出队的时候自然会考虑到,所以并不需要现在考虑那个问题。于是我解决了这一问题
再然后,我发现依然TLE了,观看题解发现bfs竟然也要排重才可以,否则哪怕是bfs算法,不排重也会算的贼慢。排重自然是想到用了map,然而,使用map后五个点中有两个点RE,剩下三个点AC。我在本地ide中测试发现终端输出libc++abi: terminating due to uncaught exception of type std::out_of_range: basic_string,意思是抛出了一个out_of_range异常。我把map有关的查重代码注释掉之后就不在异常了,说明是查重代码if (m.find(tstr.s) != m.end()) {continue;}m[tstr.s]=1;导致了out_of_range异常的抛出,可我不理解为何如此已经该怎么修

标签:map,P1032,算法,bfs,插入,range,out
From: https://www.cnblogs.com/gongkai/p/17725837.html

相关文章