[FZUOJ2064] Rainbow的信号 解题报告

题目背景&&题目大意

\(Freda\) 发明了传呼机之后，\(rainbow\) 进一步改进了传呼机发送信息所使用的信号。由于 现在是数字、信息时代，\(rainbow\) 发明的信号用 \(N\) 个自然数表示。为了避免两个人的对话被 大坏蛋 \(VariantF\) 偷听 T_T，\(rainbow\) 把对话分成 A、B、C 三部分，分别用 \(a、b、c\) 三个密码 加密。现在 \(Freda\) 接到了 \(rainbow\) 的信息，她的首要工作就是解密。\(Freda\) 了解到，这三部 分的密码计算方式如下：

在 \(1-N\) 这 \(N\) 个数中，等概率地选取两个数 \(l,r\)，如果 \(l>r\)，则交换 \(l,r\)。把信号中的第 \(l\) 个数到第 \(r\) 个数取出来，构成一个数列 \(P\)。

\(A\)部分对话的密码是数列 \(P\) 的 \(xor\) 和的数学期望值。\(xor\) 和就是数列 \(P\) 中各个数异或之后得到的数;\(xor\)和的期望就是对于所有可能选取的 \(l, r\)，所得到的数列的\(xor\)和的平均数。

\(A\)部分对话占接收到的信息总量的\(40%\)因此如果你计算出密码\(a\)将获得该测试点\(40%\)的分数。

\(B\)部分对话的密码是数列\(P\)的 \(and\) 和的期望，定义类似于 \(xor\) 和，占信息总量的 \(30%\)。

\(C\)部分对话的密码是数列\(P\)的 \(or\) 和的期望，定义类似于\(xor\)和，占信息总量的\(30%\)。

输入格式

第一行一个数字\(n\)，表示所发送的信号的长度

第二行\(n\)个数字，为所发送的信号。

输出格式

一行三个数字，分别表示题目所述的\(xor\)和，\(ans\)和以及\(or\)和

注意异或方面

首先依然根据期望的线性性，我们可以把每一位的贡献分别算出再累加起来。由题我们的数字的二进制长度不会超过int范围，也就是32位。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<bits/stdc++.h>
#define swap(x,y) x^=y^=x^=y
#define N ((int)1e5+2)
#define ld long double
using namespace std;
int n,a[N],last[2],len1,len2;
ld orans,andans,xorans;
inline void io(){cin.tie(nullptr),cout.tie(nullptr);}
signed main(){
	io();
	cin>>n;
	for(int i=1;i<=n;++i) 
        cin>>a[i];
	for(int i=0;i<31;++i)
    {
		last[0]=last[1]=len1=len2=0;
		for(int j=1;j<=n;++j)
        {
			int p=(a[j]>>i)&1;
			if(p==1)
            {
				orans+=(1<<i)*2.0/n/n*(j-1),orans+=(1<<i)*1.0/n/n;
				andans+=(1<<i)*2.0/n/n*(j-last[0]-1),andans+=(1<<i)*1.0/n/n;
				xorans+=(1<<i)*2.0/n/n*len1,xorans+=(1<<i)*1.0/n/n;
			}
			else
            {
				orans+=(1<<i)*2.0/n/n*last[1];
				xorans+=(1<<i)*2.0/n/n*len2;
			}
			++len1;
			last[p]=j;
			if(p) swap(len1,len2);
		}
	}
	printf("%.3Lf %.3Lf %.3Lf",xorans,andans,orans);
return 0;
}

绿豆蛙的归宿

题目背景

随着新版百度空间的上线，Blog 宠物绿豆蛙完成了它的使命，去寻找它新的归宿。

题目描述

给出张 \(n\) 个点 \(m\) 条边的有向无环图，起点为 \(1\)，终点为 \(n\)，每条边都有一个长度，并且从起点出发能够到达所有的点，所有的点也都能够到达终点。

绿豆蛙从起点出发，走向终点。 到达每一个顶点时，如果该节点有 \(k\) 条出边，绿豆蛙可以选择任意一条边离开该点，并且走向每条边的概率为 \(\frac{1}{k}\) 。现在绿豆蛙想知道，从起点走到终点的所经过的路径总长度期望是多少？

输入格式

输入的第一行是两个整数，分别代表图的点数 \(n\) 和边数 \(m\)。

第 \(2\) 到第 \((m + 1)\) 行，每行有三个整数 \(u, v, w\)，代表存在一条从 \(u\) 指向 \(v\) 长度为 \(w\) 的有向边。

输出格式

输出一行一个实数代表答案，四舍五入保留两位小数。

样例 #1

样例输入 #1

1
2
3
4
5
4 4 
1 2 1 
1 3 2 
2 3 3 
3 4 4

样例输出 #1

1
7.00

提示

数据规模与约定

  • 对于 \(20\%\) 的数据，保证 \(n \leq 10^2\)。

  • 对于 \(40\%\) 的数据，保证 \(n \leq 10^3\)。

  • 对于 \(60\%\) 的数据，保证 \(n \leq 10^4\)。

  • 对于 \(100\%\) 的数据，保证 \(1 \leq n \leq 10^5\)，\(1 \leq m \leq 2 \times n\)，\(1 \leq u, v \leq n\)，\(1 \leq w \leq 10^9\)，给出的图无重边和自环。

    分析:不妨设f[x]表示x点到终点的期望路径总长度 显然有f[n]=0 那么对于一条有向边,连接着x和y点(x->y) 那么显然有f[x]=sigma(f[y]+w[i])/degree[x] 其中degree[x]表示x点的出度,w[i]表示这条边的边权 那么假设我们已经知道了f[y] 我们就可以反推f[x] 显然只需要反向建边之后跑个拓扑排序就行了 那么最后答案即为f[1] 时间复杂度O(n+m)

    逆向转移，反向建边即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=1e9+7;
const int maxn=100003;
const int maxm=200003;
struct Edge
{
	int from,to,w;
}p[maxm];
int n,m,cnt,head[maxm],in[maxn],dg[maxn];
double f[maxn];//f[x]表示x点到终点n的期望路径总长 
inline void add_edge(int x,int y,int W)//加边
{
	cnt++;
	p[cnt].from=head[x];
	head[x]=cnt;
	p[cnt].to=y;
	p[cnt].w=W;
}
inline void toposort()//拓扑排序
{
	queue <int> q;
	q.push(n);
	while(!q.empty())
		{
			int x=q.front();
			q.pop();
			for(int i=head[x];i;i=p[i].from)
				{
					int y=p[i].to;
					f[y]+=(f[x]+p[i].w)/dg[y];//dp转移 
					if(!(--in[y]))q.push(y);
				}
		}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		{
			int x,y,w;
        cin>>x>>y>>w;
			add_edge(y,x,w);//反向建图 
			in[x]++,dg[x]++;
		}
	toposort();
	printf("%.2lf\n",f[1]);
	return 0;
}