AcWing 216. Rainbow的信号
原题链接
简单
作者:
如我所见
,
2022-04-02 11:04:45
,
所有人可见
,
阅读 218
Rainbow的信号
大佬题解
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n;
int a[N];
double and_xor , and_and , and_or;
void solve(int k)
{
int last[2] = {0 , 0};//记录last[0]最后0出现的位置last[1]最后1出现的位置
int c1 = 0 , c2 = 0;
for(int j = 1 ; j <= n ; j++)
{
int t = (a[j] >> k) & 1; //获取当前的二进制位
if(t == 1)
{
and_or += (1 << k) * 2.0 / n / n * (j - 1);
and_or += (1 << k) * 1.0 / n / n;//[l , l]的期望
and_and += (1 << k) * 2.0 / n / n * (j - (last[0] + 1));
and_and += (1 << k) * 1.0 / n / n;//[l , l]的期望
and_xor += (1 << k) * 2.0 / n / n * c1;
and_xor += (1 << k) * 1.0 / n / n;//[l , l]的期望
}else
{
and_xor += (1 << k) * 2.0 / n / n * c2;
and_or += (1 << k) * 2.0 / n / n * last[1];
}
last[t] = j;//更新0 1出现的位置
c1 ++;
if(t == 1) swap(c1 , c2);
}
}
int main()
{
scanf("%d" , &n);
for(int i = 1 ; i <= n ; i++) scanf("%d",&a[i]);
for(int i = 0 ; i < 31 ; i++) solve(i);//单独考虑每一位的情况,将每一位的贡献相加
printf("%.3lf %.3lf %.3lf" , and_xor , and_and , and_or);
return 0;
}