社区讨论

关于搜索与二维数组的效率:求大佬解惑

学术版参与者 2已保存回复 7

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
7 条
当前快照
1 份
快照标识符
@meyblzuo
此快照首次捕获于
2025/08/30 21:51
6 个月前
此快照最后确认于
2025/11/03 23:40
4 个月前
查看原帖
众所周知,今年蓝桥杯国赛 T5是一道非常板的 BFS,然后我尝试使用 DFS 解决此题。
然后在某神秘 OJ 上它 MLE 了!发现内存占用达到了四百多 MB,将内存限制开大至 512MB 即可 AC。
然后我回到洛谷上获得了 AC(洛谷内存限制就是 512MB)。后来不断测试,发现问题来源于我存储状态的一个三维数组:
CPP
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 进行了测试:
神奇的是,同样的变化,时间上二者仅相差 1ms,在 20 个点数据量下完全是可以接受的评测波动,这也就加剧了上面 DFS 的离奇(吐槽:DFS 比 BFS 慢多了!)。
另外,不知道是不是本题输入输出量均超小的原因,我在加上了自己含快读快写的模板并使用了快读快写之后反而运行速度变慢了,Link,并且几次测试都在 105ms 及以上。

回复

7 条回复,欢迎继续交流。

正在加载回复...