关于省选的空间限制

题目链接：P7519

评测结果：here

代码：here

问题概要：省选评测的时候，MLE 的标准是“开了多少空间”（不管用没用），还是“实际访问了多少空间”？

在做 2021 省选题的时候，我开了一个 long long 类型的数组 dp[8280][14][505]，经过计算，这个数组占用的空间是 469MB。

但是运行结果显示，最大的一个点也只占用了 441MB 的空间。我猜测可能是因为有一些数组空间并没有被访问过，也就没有占用内存。

于是，我又交了几发 A+B，都是以下格式：

CPP

#include <bits/stdc++.h>
using namespace std;
int a,b,c[500005000];
int main()
{
    a=262764093,b=446679284;// 示例
    cin>>c[a]>>c[b];
    cout<<c[a]+c[b];
    return 0;
}

得到了以下的结果（C++11，均未开 O2）：

$a$	$b$	空间
$1$	$2$	808KB
$1$	$5\times10^8$	808KB
$5\times10^8-1$	$5\times10^8$	808KB
$2.5\times10^8$	$2.5\times10^8+1$	2.45KB
$1\times10^8$	$4\times10^8$	4.39MB
$1.67\times10^8$	$3.33\times10^8$	4.46MB

推测空间不仅与访问了多少内存有关，还与访问的位置有关（访问位置靠近头尾、间隔较小可能会省空间？）

但是，在 Lemon 等本地评测软件上，根据我们机房平时测试的经验，只要数组（全局变量）开的过大，就会MLE。 像上面的 A+B 测试，在本地早就爆 MLE 了。

所以想问一下大家，省选的空间限制是按照洛谷上这样，根据实际访问的大小来测算，还是像 Lemon 那样开多大空间算多大呢？

以及追问两个问题：

O2 优化对空间有影响吗？如果有，更倾向于正优化还是负优化呢？
像 vector 这样的 STL容器，在“开了但是没有填入数据”的时候会占用多少内存呢？比如我开了一个 vector<long long> e[2000200]，但是只往里面放了 1e5 个数，实际占用空间会有多大呢？

问题较长，提前谢谢大家的理解与帮助 (^v^)

关于省选的空间限制

讨论操作

回复

相关推荐

关于省选的空间限制