关于搜索与二维数组的效率:求大佬解惑
  • 板块学术版
  • 楼主Leo2011
  • 当前回复6
  • 已保存回复6
  • 发布时间2025/8/30 21:51
  • 上次更新2025/8/31 15:00:25
查看原帖
关于搜索与二维数组的效率:求大佬解惑
539066
Leo2011楼主2025/8/30 21:51

众所周知,今年蓝桥杯国赛 T5是一道非常板的 BFS,然后我尝试使用 DFS 解决此题。

然后在某神秘 OJ 上它 MLE 了!发现内存占用达到了四百多 MB,将内存限制开大至 512MB 即可 AC。

然后我回到洛谷上获得了 AC(洛谷内存限制就是 512MB)。后来不断测试,发现问题来源于我存储状态的一个三维数组:

const int N = xxx;
int vis[N][N][N];  // 就是这个东西
N 的大小20 个数据点运行总时间最大数据点占用内存评测记录
201265ms31.63MBhttps://www.luogu.com.cn/record/233779747
205279ms33.51MBhttps://www.luogu.com.cn/record/233779471
210297ms36.02MBhttps://www.luogu.com.cn/record/233779432
300667ms103.76MBhttps://www.luogu.com.cn/record/233779392
4001.43s245.19MBhttps://www.luogu.com.cn/record/233779454
5003.65s478.74MBhttps://www.luogu.com.cn/record/233679675

保证全部使用洛谷平台进行评测并开启 O2 优化,语言标准均为 C++23 或 C++20 并采用洛谷安装的同一版本 GCC 编译器评测,以及除了 N 的大小和注释之外没有修改任何代码。

本题有 20 个评测点,但是像 201 和 500 那样时空上都是几十上百倍的差异明显不在正常范围内,求大佬解答原因。


另外,我也用 BFS 进行了测试:

N = 205

N = 500

神奇的是,同样的变化,时间上二者仅相差 1ms,在 20 个点数据量下完全是可以接受的评测波动,这也就加剧了上面 DFS 的离奇(吐槽:DFS 比 BFS 慢多了!)。

另外,不知道是不是本题输入输出量均超小的原因,我在加上了自己含快读快写的模板并使用了快读快写之后反而运行速度变慢了,Link,并且几次测试都在 105ms 及以上。

2025/8/30 21:51
加载中...