题目https://www.acwing.com/problem/content/218/
那个错误代码交上去是内存超限
把那两行超长注释符的句子注释掉是finish,不超了
我很好奇c矩阵也就1e7的int不到也能内存超限?
我一开始以为是异或有问题但用c【1】【i】【j】也是内存超限
并且注释掉那两行后,下面的遍历c也没有问题,真是玄学
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef double db;
typedef unsigned long long ull;
#define fi first
#define se second
#define pk push_back
#define mk make_pair
const ll N=1e5+10, M=40, mod=1e9+7, inf=0x3f3f3f3f3f3f3f3f, Max=5e4;
const int iinf=0x3f3f3f3f;
const ll seed=233, hashmod=1e9+7;//哈希
const db esp=1e-7;
int n, a[N], last0[N][M], last1[N][M], c[4][N][M];
bool att[N][M], b[N][M];
// int aaa[200][100005];
void work(){
scanf("%d",&n);
for(int i=1;i<=n;i++) {
scanf("%d", &a[i]);
for(int j=0;j<31;j++){
b[i][j]=(a[i]>>j)&1;
}
}
for(int j=0;j<31;j++){
for(int i=1;i<=n;i++){
last0[i][j]=last0[i-1][j];
last1[i][j]=last1[i-1][j];
if(b[i][j])
last1[i][j]=i;
else
last0[i][j]=i;
}
}
for(int j=0;j<31;j++){
int flag=0;
for(int i=1;i<=n;i++){
att[i][j]=flag;
c[flag][i][j]=c[flag][i-1][j]+1;
c[1][i][j]=c[1][i-1][j];//////////////////////////////
// if(b[i][j]) flag=flag?0:1;////////////////////////
}
}
double axor=0;
for(int j=0;j<31;j++){
for(int i=1;i<=n;i++){
int flag=att[i][j];
if(b[i][j])
axor+=1.0*(1<<j)*(c[flag][i][j]-1)*2/n/n,
axor+=1.0*(1<<j)/n/n;//ok
else
axor+=1.0*(1<<j)*c[flag^1][i][j]*2/n/n;
}
}
printf("%.3f ",axor);
db aand=0;
for(int j=0;j<31;j++){
for(int i=1;i<=n;i++){
if(b[i][j]==1)
aand+=1.0*(1<<j)*(i-last0[i][j]-1)*2/n/n,
aand+=1.0*(1<<j)/n/n;
}
}
printf("%.3f ",aand);
db aor=0;
for(int j=0;j<31;j++){
for(int i=1;i<=n;i++){
if(b[i][j]==1){
aor+=1.0*(1<<j)*(i-1)*2/n/n;
aor+=1.0*(1<<j)/n/n;
}else{
aor+=1.0*(1<<j)*(last1[i][j])*2/n/n;
}
}
//cout<<j<<" "<<(1<<j)<<" "<<aand<<endl;
}
printf("%.3f",aor);
return ;
}
int main() {
// freopen("C:\\Users\\lenovo\\Desktop\\in.txt","r",stdin);
// freopen("C:\\Users\\lenovo\\Desktop\\out.txt","w",stdout);
// ll t;
// cin>>t;
// for(ll i=1;i<=t;i++)
work();
return 0;
}