众所周知,今年蓝桥杯国赛 T5是一道非常板的 BFS,然后我尝试使用 DFS 解决此题。
然后在某神秘 OJ 上它 MLE 了!发现内存占用达到了四百多 MB,将内存限制开大至 512MB 即可 AC。
然后我回到洛谷上获得了 AC(洛谷内存限制就是 512MB)。后来不断测试,发现问题来源于我存储状态的一个三维数组:
const int N = xxx;
int vis[N][N][N]; // 就是这个东西
N 的大小 | 20 个数据点运行总时间 | 最大数据点占用内存 | 评测记录 |
---|---|---|---|
201 | 265ms | 31.63MB | https://www.luogu.com.cn/record/233779747 |
205 | 279ms | 33.51MB | https://www.luogu.com.cn/record/233779471 |
210 | 297ms | 36.02MB | https://www.luogu.com.cn/record/233779432 |
300 | 667ms | 103.76MB | https://www.luogu.com.cn/record/233779392 |
400 | 1.43s | 245.19MB | https://www.luogu.com.cn/record/233779454 |
500 | 3.65s | 478.74MB | https://www.luogu.com.cn/record/233679675 |
保证全部使用洛谷平台进行评测并开启 O2 优化,语言标准均为 C++23 或 C++20 并采用洛谷安装的同一版本 GCC 编译器评测,以及除了 N 的大小和注释之外没有修改任何代码。
本题有 20 个评测点,但是像 201 和 500 那样时空上都是几十上百倍的差异明显不在正常范围内,求大佬解答原因。
另外,我也用 BFS 进行了测试:
神奇的是,同样的变化,时间上二者仅相差 1ms,在 20 个点数据量下完全是可以接受的评测波动,这也就加剧了上面 DFS 的离奇(吐槽:DFS 比 BFS 慢多了!)。
另外,不知道是不是本题输入输出量均超小的原因,我在加上了自己含快读快写的模板并使用了快读快写之后反而运行速度变慢了,Link,并且几次测试都在 105ms 及以上。