模板网站库,咸阳网站建设公司,五里桥街道网站建设,如何自创游戏Acwing 216. Rainbow的信号
题意#xff1a;
给你n个数#xff0c;在这n个数中#xff0c;等概率地选取两个数l#xff0c;r#xff0c;如果lr,则交换l,r 把信号中的第 l 个数到第 r 个数取出来#xff0c;构成一个数列 P。
A 部分对话的密码是数列 P 的 xor 和的…Acwing 216. Rainbow的信号
题意
给你n个数在这n个数中等概率地选取两个数lr如果lr,则交换l,r 把信号中的第 l 个数到第 r 个数取出来构成一个数列 P。
A 部分对话的密码是数列 P 的 xor 和的数学期望值xor 和就是数列 P 中各个数异或之后得到的数 xor 和的期望就是对于所有可能选取的 l、r所得到的数列的 xor 和的平均数。
B 部分对话的密码是数列 P 的 and 和的期望定义类似于 xor 和。
C 部分对话的密码是数列 P 的 or 和的期望定义类似于 xor 和。
题解
参考题解 按位来计算答案。枚举二进制下的每一位因为数109,说明最多30位 对于每一位(这里指的是二进制数位)枚举1到n每个数把当前枚举的第k个数当作是范围的右端点考虑左端点的取值情况来计算概率 设当前枚举的数位是k当前枚举的是第r个数当前第r个数的数位的值为v(v只会是0或1) 注意题目说了当lr时会交换l和r所以l和r的取值范围均为n所以l r的概率为1/n ^ 2,其他概率为2/n ^ 2. xor 和的期望就是对于所有可能选取的 l、r所得到的数列的 xor 和的平均数。也就是所能取到的值乘以取到的概率 当数位的值v为1时 因为有l r的情况所有xorandor的答案都要加上该数位的值乘以1/n ^2如果这是第3位那就要加上4/n ^2我们设pos(该数为的值)/n ^2 (1k)/n ^2
对于oror是有1则1而当前v正是1(也就是第r位是1)所以左端点l随便取(当前不能等于r)所以l的取值概率为(r-1) * pos * 2(别忘乘以2) 对于andand是全部为1则1所以我们需要用last[v]表示上一次v出现的位置last[0]表示上一次0出现的位置而l的取值范围是[last[0]1,r-1],所以概率为r-1-last[0]* pos * 2
当前数位的值v为0的时候 and怎么都是0所以不用考虑 对于orl的所取的区间中的数位必须出现一个1last[1]表示上一次1出现的位置那l区间范围是[1,last[1]],所以概率就是last[1] * pos * 2
xor单独讨论 对于1到n各个数在第k位上的数位值 我们现在以1为边界将区间分段 每一段内有且只有一个1(r所在的那一段暂不考虑)异或0对xor没有影响而每异或一次1xor的值就会发生反转所以我们用c1表示奇数区间包含的值的个数c2表示偶数区间包含的值的个数 如果r为1那么l位于偶数区间的话答案异或为1也就是l有c1个取值可能。如果r为0那么l就有c2个取值可能(代码中实现c1和c2的方法很妙) 详细可以看代码diamond
代码
#includebits/stdc.h
using namespace std;int read()
{int x0,f1;char chgetchar();while(ch0||ch9) {if(ch-) f-1; chgetchar();}while(ch0ch9) {xx*10ch-0; chgetchar();}return x*f;
}const int maxn1e55;
int n,c1,c2;
int w[maxn],p[maxn],last[2];
double ansxor,ansand,ansor;void solve(int k)
{c1c20;last[0]last[1]0;double pos(double)(1k)/n/n;//当前数位的实际值/n方的概率for(int r1;rn;r){int v((w[r]k)1);if(v){ansxorpos;ansandpos;ansorpos;}if(v){ansorpos*(r-1)*2;ansandpos*(r-1-last[0])*2;ansxorpos*c1*2;}else {ansorpos*last[1]*2;ansxorpos*c2*2;}c1;if(v) swap(c1,c2); //到了新的区间就开始另一个变量开始计数 last[v]r;}
}int main()
{nread();for(int i1;in;i) w[i]read();for(int i0;i30;i) solve(i);printf(%.3lf %.3lf %.3lf,ansxor,ansand,ansor);return 0;
}
