[提醒自己和各路神仙] NOIP中千万别MLE!!!
作者:
PrinceS
,
2022-11-21 17:09:49
,
所有人可见
,
阅读 301
两次NFLS模拟赛,两次MLE
第一次:100pts->0pts
第二次(今天):100pts->30pts
在 Catium 的细心教导下,我终于会算空间了,以后再也不MLE了!(尤其是NOIP)
废话少说,直接举例子:
这是第一次MLE的部分代码:
ll m,n;
ll a[M][N];
bool b[M];
vector<ll> g[N][531441];
ll f[N];
计算空vector所占内存大小:
ll t=110*531441*sizeof(vector<ll>);
cout<<1.0*t/1024/1024;
输出是 1338.01,很显然,vector连用都没用就已经MLE了
今天考场上苦思冥想的正解,挂成了比暴力分还低,部分代码:
ll a[N];
ll b[N];
struct nd{
ll id,x;
};
vector<nd> g[128][1024];
算出来内存很小,对吧?但其实没算上vector的元素QAQ
for(ll i=1,x,y;i<=m;i++){
cin>>x>>y;
x&=all;
ll x1=x>>10,x2=x&1023;
for(ll T=x2;T;T=(T-1)&x2){
g[x1][T].pb({i,y});
}
g[x1][0].pb({i,y});
}
这段代码最坏情况下会 pushback 100000*1024 个nd类型的元素
计算这部分的空间:
ll t=100000*1024*sizeof(nd)*2;
cout<<1.0*t/1024/1024;
输出 3125,寄!
PS:*2是因为vector内部采用倍增机制,最坏情况下开辟的元素数量是实际元素数量的二倍
栈空间的计算:递归到最深处时整条递归路径上的所有变量所占空间,加起来即可
内存限制不一定是512MB,看清楚看仔细!
还有就是判断是否MLE看的是程序占用内存的峰值,而不是最终所占内存,这点一定要注意,看看中间有没有临时开一些很大的容器,导致峰值超过限制
神神神神神
感谢博主,学到许多!
啧啧啧,郭队祝福我再也不MLE!