Rainbow的信号 CH3801

题目链接

题意：求n个整数任意取一个区间，一起进行xor，and，或or的操作，求xor的期望值，and的期望值，or的期望值。

思路：区间取的左端点为l，右端点为r，当r==l时，选的概率为1/n/n，而r！=l时，选的概率为2/n/n。

然后因为进行二进制操作，所以枚举整数的每个二进制位。三个操作分三种情况：

1and：考虑先枚举一个右端点r,考虑and的性质,所以考虑找到前面第一个0出现的位置last[0],如果这一位也为1,那么左端点就可以取[last[0]+1,r−1]。

2or：依然考虑枚举右端点r,找到前一个1出现的位置last[1],如果这一位为1,那么左端点可以取[1,r−1],如果这一位不为0,那么左端点可以取[1,last[1]]。

3xor：算法竞赛进阶指南上写得很详细。

　　　首先依然是枚举右端点r，因为xor的性质,所以考虑找到所有为1的点,然后根据这些点进行黑白染色,就会是左端点可以取所有白段，最后再递推一下。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<map>
#include<queue>
#include<vector>
#include<string>
#include<set>
#define ll long long
using namespace std;
const int N=1e6+10;
int n;
int a[N],b[N];
double ansa,anso,ansx;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d",&a[i]);
    for(int k=0;k<31;k++)
    {
        int last[2]={0,0},c1=0,c2=0;
        for(int i=1;i<=n;i++)
        {
            b[i]=((a[i]>>k)&1);
            if(b[i])
            {
                ansa+=(1<<k)*1.0/n/n;
                anso+=(1<<k)*1.0/n/n;
                ansx+=(1<<k)*1.0/n/n;
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(!b[i])
            {
                anso+=(1<<k)*2.0/n/n*last[1];
            }
            else
            {
                ansa+=(1<<k)*2.0/n/n*(i-1-last[0]);
                anso+=(1<<k)*2.0/n/n*(i-1);
            }
            ansx+=(1<<k)*2.0/n/n*(b[i]?c1:c2);
            c1++;
            if(b[i])
            swap(c1,c2);
            last[b[i]]=i;
        }
    }
    printf("%.3lf %.3lf %.3lf
",ansx,ansa,anso);
}