# 雅礼集训 小c饮水记

## 链表乱搞题

Posted by yjjr's blog on January 18, 2018 1 minutes to read

# code

25分暴力

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=5e5+6;
double ans;
int n,w[maxn],bin[35];
inline bool cmp(int x,int y){return x>y;}

void work(int l,int r){
double t;int b[maxn],len=min(r-l+1,30);
rep(i,l,r)b[i-l+1]=w[i];
sort(b+1,b+r-l+2,cmp);
rep(i,1,len)t+=(double)b[i]/bin[i];
ans+=(double)t/(n*n);
//cout<<ans<<endl;
}
int main()
{
//freopen("T1.in","r",stdin);
//freopen("T1.out","w",stdout);
bin[1]=2;rep(i,2,30)bin[i]=bin[i-1]<<1;
//rep(i,1,30)cout<<bin[i]<<endl;
rep(l,1,n)rep(r,l,n)work(l,r);
printf("%.4lf",ans);
return 0;
}



#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=1e6+6;
int _pre[maxn],_next[maxn],n,l[36],r[36];
struct node{int id,val;}w[maxn];
double ans,bin[36];
inline bool cmp(node a,node b){return a.val<b.val;}
int main()
{
//freopen("T1.in","r",stdin);
//freopen("T1+.out","w",stdout);
bin[0]=1;rep(i,1,30)bin[i]=bin[i-1]/2.0;
sort(w+1,w+1+n,cmp);
rep(i,1,n+1)_pre[i]=i-1;rep(i,0,n)_next[i]=i+1;
rep(i,1,n){
int lnow,rnow,llen=0,rlen=0;double lans=0,rans=0;
l[0]=r[0]=lnow=rnow=w[i].id;
rep(j,1,30){
if(lnow)l[++llen]=(lnow=_pre[lnow]);
if(rnow!=n+1)r[++rlen]=(rnow=_next[rnow]);
}
rep(j,1,llen)lans+=bin[j]*(l[j-1]-l[j]);
rep(j,1,rlen)rans+=bin[j]*(r[j]-r[j-1]);
ans+=lans*rans*2*w[i].val;
_pre[_next[w[i].id]]=_pre[w[i].id];
_next[_pre[w[i].id]]=_next[w[i].id];
}
printf("%.4lf",ans/n/n);
return 0;
}