Acwing 216. Rainbow的信号
Acwing 216. Rainbow的信號
題意：
給你n個數(shù)，在這n個數(shù)中，等概率地選取兩個數(shù)l，r，如果l>r,則交換l,r
把信號中的第 l 個數(shù)到第 r 個數(shù)取出來，構(gòu)成一個數(shù)列 P。
A 部分對話的密碼是數(shù)列 P 的 xor 和的數(shù)學(xué)期望值，xor 和就是數(shù)列 P 中各個數(shù)異或之后得到的數(shù)； xor 和的期望就是對于所有可能選取的 l、r，所得到的數(shù)列的 xor 和的平均數(shù)。
B 部分對話的密碼是數(shù)列 P 的 and 和的期望，定義類似于 xor 和。
C 部分對話的密碼是數(shù)列 P 的 or 和的期望，定義類似于 xor 和。
題解：
參考題解
按位來計算答案。枚舉二進(jìn)制下的每一位，因為數(shù)<109,說明最多30位
對于每一位(這里指的是二進(jìn)制數(shù)位)，枚舉1到n每個數(shù)，把當(dāng)前枚舉的第k個數(shù)當(dāng)作是范圍的右端點，考慮左端點的取值情況來計算概率
設(shè)當(dāng)前枚舉的數(shù)位是k，當(dāng)前枚舉的是第r個數(shù)，當(dāng)前第r個數(shù)的數(shù)位的值為v(v只會是0或1)
注意：題目說了當(dāng)l>r時會交換l和r，所以l和r的取值范圍均為n，所以l = r的概率為1/n ^ 2,其他概率為2/n ^ 2.
xor 和的期望就是對于所有可能選取的 l、r，所得到的數(shù)列的 xor 和的平均數(shù)。也就是所能取到的值乘以取到的概率
當(dāng)數(shù)位的值v為1時
因為有l(wèi) = r的情況，所有xor，and，or的答案都要加上該數(shù)位的值乘以1/n ^2（如果這是第3位，那就要加上4/n ^2），我們設(shè)pos=(該數(shù)為的值)/n ^2 = (1<<k)/n ^2
對于or，or是有1則1，而當(dāng)前v正是1(也就是第r位是1)，所以左端點l隨便取(當(dāng)前不能等于r)，所以l的取值概率為(r-1) * pos * 2(別忘乘以2)
對于and，and是全部為1則1，所以我們需要用last[v]表示上一次v出現(xiàn)的位置，last[0]表示上一次0出現(xiàn)的位置，而l的取值范圍是[last[0]+1,r-1],所以概率為（r-1-last[0]）* pos * 2
當(dāng)前數(shù)位的值v為0的時候：
and怎么都是0，所以不用考慮
對于or，l的所取的區(qū)間中的數(shù)位必須出現(xiàn)一個1，last[1]表示上一次1出現(xiàn)的位置，那l區(qū)間范圍是[1,last[1]],所以概率就是last[1] * pos * 2
xor單獨(dú)討論
對于1到n各個數(shù)在第k位上的數(shù)位值：
我們現(xiàn)在以1為邊界將區(qū)間分段：
每一段內(nèi)有且只有一個1(r所在的那一段暫不考慮)，異或0對xor沒有影響，而每異或一次1，xor的值就會發(fā)生反轉(zhuǎn)，所以我們用c1表示奇數(shù)區(qū)間包含的值的個數(shù)，c2表示偶數(shù)區(qū)間包含的值的個數(shù)
如果r為1，那么l位于偶數(shù)區(qū)間的話，答案異或為1，也就是l有c1個取值可能。如果r為0，那么l就有c2個取值可能(代碼中實現(xiàn)c1和c2的方法很妙)
詳細(xì)可以看代碼diamond
代碼：
#include<bits/stdc++.h> using namespace std;int read() {int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9') {if(ch=='-') f=-1; ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();}return x*f; }const int maxn=1e5+5; int n,c1,c2; int w[maxn],p[maxn],last[2]; double ansxor,ansand,ansor;void solve(int k) {c1=c2=0;last[0]=last[1]=0;double pos=(double)(1<<k)/n/n;//當(dāng)前數(shù)位的實際值/n方的概率for(int r=1;r<=n;r++){int v=((w[r]>>k)&1);if(v){ansxor+=pos;ansand+=pos;ansor+=pos;}if(v){ansor+=pos*(r-1)*2;ansand+=pos*(r-1-last[0])*2;ansxor+=pos*c1*2;}else {ansor+=pos*last[1]*2;ansxor+=pos*c2*2;}++c1;if(v) swap(c1,c2); //到了新的區(qū)間，就開始另一個變量開始計數(shù) last[v]=r;} }int main() {n=read();for(int i=1;i<=n;i++) w[i]=read();for(int i=0;i<=30;i++) solve(i);printf("%.3lf %.3lf %.3lf",ansxor,ansand,ansor);return 0; }總結(jié)
以上是生活随笔為你收集整理的Acwing 216. Rainbow的信号的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
