2017.11.1模拟 signal

2017.11.1模拟 signal

​​#include#include#include#define N 110000using namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0,f=1;char ch=gc(); while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=gc();} while (ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();} return x*f;}long long ans1,ans2,ans3,sum1;int n,a[N],bin[35],sum[N],max1,s[2];inline int calc_even(int x){return x/2+1;}inline int calc_odd(int x){return x/2;}int main(){// freopen("signal.in","r",stdin); n=read(); for (int i=1;i<=n;++i) a[i]=read(),max1=max(max1,a[i]),sum1+=a[i]; for (int i=0;i<=31;++i) bin[i]=1<pos3) pos3++; while ((bin[i]&a[pos3])==0&&pos3<=n) ++pos3; count3+=n-pos3+1; }ans3+=(long long)bin[i]*count3; int pos2=1;long long count2=0; for (int j=1;j<=n;++j){ if (j>pos2) pos2++; while((bin[i]&a[pos2])&&pos2<=n) ++pos2; if (a[j]&bin[i]) count2+=pos2-j; }ans2+=(long long)bin[i]*count2;memset(sum,0,sizeof(sum));long long count1=0; for (int j=n;j>=1;--j) sum[j]+=sum[j+1]+(a[j]&bin[i]);int pos1=1; while ((a[pos1]&bin[i])==0&&pos1<=n)++pos1;int tmp=0; while(1){ if (pos1>n) break;pos1++;tmp++;int last=pos1; while((a[pos1]&bin[i])==0&&pos1<=n)++pos1; s[tmp%2]+=pos1-last+1; }pos1=1; while ((a[pos1]&bin[i])==0&&pos1<=n)++pos1;int last=pos1;tmp=0; for (int j=1;j<=n;++j){ if (a[j]&bin[i]) { ++tmp;last=j;pos1=j+1; while((a[pos1]&bin[i])==0&&pos1<=n)++pos1; count1+=s[tmp%2];s[tmp%2]-=pos1-last; }else{ count1+=s[(tmp+1)%2]; } }ans1+=(long long)bin[i]*count1; } ans1<<=1;ans1-=sum1;ans2<<=1;ans2-=sum1;ans3<<=1;ans3-=sum1; printf("%.3f %.3f %.3f",(double)ans1/((long long)n*n),(double)ans2/((long long)n*n),(double)ans3/((long long)n*n)); return 0;}

题意要求 求给N个数 里面任意区间的异或 或 与 的期望是多少

或的话可以固定左端点然后我们线性的去更新右端点即可 因为我们知道 右端点 只要有一个1 那么就一定可以保持一直是1 o1计算即可

与的性质和或差不多 是枚举左端点 线性找右端点什么时候为0 就不做了

异或麻烦一些 我的做法是 一个1配套后面的0分成一组 然后分奇和偶组 然后 再根据现在已有的1的个数来加答案即可 注意0100 0010这些情况也都要算在内

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。