Rainbow的信号 题解报告

2019/05/04 11:48
阅读数 27

题目传送门

【题目大意】

给定一个有n个数的数列,在这n个数中等概率的选取两个数l,r(保证l≤r),组成一个区间[l,r],求出区间的每个数异或之后的结果,求对于这个数列的异或的期望值(此处定义为所有区间异或的结果的平均数)。类似地还要求出与运算和或运算的期望值。

【思路分析】

这题乍一看有点复杂呀,其实就是一个披着概率的皮的位运算题。

既然是位运算,那就很简单啦。因为位运算是不会出现进位的,也就是说每一位之间互不影响,所以就可以拆开之后一位一位地处理。首先把数列a中的每个数都转成二进制,然后b[i]表示a[i]第k位的数,此处的k会在程序运行过程中枚举。

然后我们发现对于任意区间,只可能存在两种情况:长度=1或长度≥2。

分类讨论发现,区间长度=1时,期望值就是乘上$\frac{1}{n^2}$,而区间长度≥2时,期望值就是乘上$\frac{2}{n^2}$

接下来对于三种运算我们分别分析一下(相对二进制每一位来说)

1.与运算

根据与运算的特点可知,只要区间内出现了0,那么整个区间的结果就一定是0

2.或运算

同样根据特点可知,只要区间内出现了1,那么整个区间的结果就一定是1

3.异或运算

异或运算比较麻烦,我们需要找到区间内每个1的位置,然后一旦遇到1,结果就会变化(由1变成0或者由0变成1),所以可以以1为分界线把整个区间分割成几块,然后再具体处理

为了方便实现,我们枚举右端点,用last[0]和last[1]分别记录上一个出现0和1的位置,然后用c1和c2分别记录当前情况下可以使异或结果为1和0的左端点个数。

这里要注意一点,当我们枚举到一个新的右端点的时候,要根据这一点是1或0分类讨论,详见代码。

还有一个要注意的地方就是不能直接/(n*n),而要写成/n/n,我也不知道为什么但我就是被这个地方卡了好久,也许是精度问题?QAQ

【代码实现】

 1 #include<bits/stdc++.h>
 2 #define go(i,a,b) for(register int i=a;i<=b;i++)
 3 using namespace std;
 4 double ans_and,ans_or,ans_xor;
 5 int a[1000002],b[1000002],n;
 6 void work(int k){//计算各个区间的结果,为求期望做准备
 7     int last[2]={0,0},c1=0,c2=0;
 8     go(i,1,n){
 9         b[i]=((a[i]>>k)&1);
10         if(b[i]){//区间为一个点的情况
11             double add=(1<<k)*1.0/n/n;
12             ans_and+=add;ans_or+=add;ans_xor+=add;
13         }
14     }
15     go(i,1,n){//枚举区间右端点
16         if(!b[i])
17             ans_or+=(1<<k)*2.0/n/n*last[1];
18         else{
19             ans_and+=(1<<k)*2.0/n/n*(i-1-last[0]);
20             ans_or+=(1<<k)*2.0/n/n*(i-1);
21         }
22         ans_xor+=(1<<k)*2.0/n/n*(b[i]?c1:c2);
23         c1++;if(b[i]) swap(c1,c2);
24         last[b[i]]=i;
25     }
26 }
27 int main(){
28     scanf("%d",&n);
29     go(i,1,n) scanf("%d",&a[i]);
30     go(i,0,30) work(i);
31     printf("%.3lf %.3lf %.3lf\n",ans_xor,ans_and,ans_or);
32     return 0;
33 }
代码戳这里
展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部