正解:位运算

解题报告:

其实就是个位运算,,,只是顺便加了个期望的知识点$so$期望的帕并不难来着$QwQ$

先把期望的皮扒了,就直接分类讨论下,不难发现,答案分为两个部分

$\left\{\begin{matrix}l=r & \frac{1}{n}\cdot\frac{1}{n}=\frac{1}{n^{2}}\\ \\ l\neq r & \frac{2}{n}\cdot\frac{1}{n}=\frac{2}{n^{2}}\end{matrix}\right.$

这样就只要求出值,然后乘以概率就得到期望辽$QwQ$

然后现在的问题就变成了,怎么快速求出所有区间的$xor$和,$and$和,$or$和

可以发现每一位互不影响,所以对每一位都扒出来,然后单独看这一位,只要能求出这一位中有多少个子区间满足通过$xor$/$and$/$or$运算之后是1,乘以$2^{k}$即可

(啊这儿说下,,,因为$l=r$的情况直接枚举每一个数直接算就好,$so$下面所有讨论的都是$l\neq r$的来着

先说$and$和趴,考虑先枚举一个右端点$r$,考虑$and$的性质,所以考虑找到前面第一个0出现的位置$lst_{0}$,如果这一位也为1,那么左端点就可以取$[lst_{0}+1,r-1]$,就欧克了

对于$or$和的话,依然考虑枚举右端点$r$,找到前一个1出现的位置$lst_{1}$,如果这一位为1,那么左端点可以取$[1,r-1]$,如果这一位不为0,那么左端点可以取$[1,lst_{1}]$

最后说下$xor$和,因为这个相对而言复杂一些$so$放到最后港$QwQ$

首先依然是枚举右端点$r$,因为$xor$的性质,所以考虑找到所有为1的点,然后根据这些点进行黑白染色,就会是左端点可以取所有白段($umm$其实因为我都还麻油说黑白色是染啥$but$意会下能$get$的趴,,,懒得详细说了,画图应该会好理解些但我懒得画鸭$QAQ$

然后考虑怎么递推,不难发现,从$r$变成$r+1$,首先会是黑段长度++,然后这儿要分类讨论下,就当$r$点是1的时候,要交换下黑段和白段的长度,意会下,非常显然不想详细港了

综上,这题做完辽

具体看代码趴$QAQ$

#include<bits/stdc++.h>

using namespace std;

#define il inline

#define gc getchar()

#define lf double

#define int long long

#define ri register int

#define rb register bool

#define rc register char

#define rp(i,x,y) for(ri i=x;i<=y;++i)

const int N=1e5+;

int n,a[N],lst[],p[],as_xor,as_and,as_or;

il int read()

{

    rc ch=gc;ri x=;rb y=;

    while(ch!='-' && (ch>'' || ch<''))ch=gc;

    if(ch=='-')ch=gc,y=;

    while(ch>='' && ch<='')x=(x<<)+(x<<)+(ch^''),ch=gc;

    return y?x:-x;

}

main()

{

    n=read();rp(i,,n)a[i]=read(),as_xor=as_and=as_or=as_xor+a[i];

    rp(i,,)

    {

        lst[]=lst[]=p[]=p[]=;

        rp(j,,n)

        {

            ri dat=(a[j]>>i)&;

            if(dat)

            {

                as_and+=2ll*(j-lst[]-)*(<<i);

                as_or+=2ll*(j-)*(<<i);

                as_xor+=2ll*p[]*(<<i);

                swap(p[],p[]);

                ++p[];lst[]=j;

            }

            else

            {

                as_or+=2ll*lst[]*(<<i);

                as_xor+=2ll*p[]*(<<i);

                ++p[];lst[]=j;

            }

        }

    }

    printf("%.3lf %.3lf %.3lf",(lf)as_xor/(1ll*n*n),(lf)as_and/(1ll*n*n),(lf)as_or/(1ll*n*n));

    return ;

}

这儿是代码$qwq$

对了说个细节,,,

就是这题好像有点儿卡精度,,,?如果在过程中边做边除好像就必须是/$n$/$n$,改成/$n^{2}$好像就会爆炸,,,

然后这儿的建议是过程中不除,,,直接在结尾一块儿除,,,但是这样的话就记得全程开$ll$,,,我的话是直接$define\ int\ long\ long$了,注意下$QwQ$

$over!$

巴特西

$CH$3801 $Rainbow$的信号期望+位运算

正解:位运算

解题报告:

最新文章

热门文章

巴特西

$CH$3801 $Rainbow$的信号 期望+位运算

正解:位运算

解题报告:

最新文章

热门文章

$CH$3801 $Rainbow$的信号期望+位运算