【NOIP模拟题】小象涂色（概率+期望+递推）

表示数学是个渣。。。

其实只需要推出每个箱子k次以后的颜色为i的概率就能算出期望了。。

对于区间[l, r]的箱子因为是任意颜色且任意取，所以概率分别为1/c和1/2，那么整体概率就为这两个的乘积。根据全概率公式，对于后边的状态我们可以累加和就行了。。

求出概率后期望就是颜色编号*概率。。。。。。。

暴力40分。。O(k*n*c^2)。。。

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <vector>

#include <map>

using namespace std;

typedef long long ll;

#define pii pair<int, int>

#define mkpii make_pair<int, int>

#define pdi pair<double, int>

#define mkpdi make_pair<double, int>

#define pli pair<ll, int>

#define mkpli make_pair<ll, int>

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << (#x) << " = " << (x) << endl

#define error(x) (!(x)?puts("error"):0)

#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }

#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

const double eps=1e-10;

double e[55][105][55];

int c, K, n, L[55], R[55];

int main() {

	int cs=getint();

	while(cs--) {

		read(n); read(c); read(K);

		for1(i, 1, K) read(L[i]), read(R[i]);

		for1(k, 1, K+1) rep(i, c) for1(j, 1, n) e[k][i][j]=0;

		for1(i, 1, n) e[1][1][i]=1.0;

		for1(k, 1, K) {

			rep(i, c) for1(j, 1, L[k]-1) e[k+1][i][j]=e[k][i][j];

			rep(i, c) for1(j, R[k]+1, n) e[k+1][i][j]=e[k][i][j];

			rep(b, c) rep(i, c) for1(j, L[k], R[k]) e[k+1][(i*b)%c][j]+=e[k][i][j]/2/c;

			rep(i, c) for1(j, L[k], R[k]) e[k+1][i][j]+=e[k][i][j]/2;

		}

		double ans=0;

		rep(i, c) for1(j, 1, n) ans+=i*e[K+1][i][j];

		printf("%.9f\n", ans);

	}

	return 0;

}

然后考虑优化：

我们发现箱子都是一样的，且是根据被区间覆盖的次数而决定的概率（就是上边代码那四个循环的前两个，如果这些点没有被覆盖到，那么将来的值都是一样的。。。）

所以我们只需要按区间覆盖次数来计算概率。

如果一个箱子被覆盖的次数是x，那么就用x次的概率来算。

这样时间复杂度优化到O(k*c^2)

#include <cstdio>

#include <cstring>

#include <cmath>

#include <string>

#include <iostream>

#include <algorithm>

#include <queue>

#include <set>

#include <vector>

#include <map>

using namespace std;

typedef long long ll;

#define pii pair<int, int>

#define mkpii make_pair<int, int>

#define pdi pair<double, int>

#define mkpdi make_pair<double, int>

#define pli pair<ll, int>

#define mkpli make_pair<ll, int>

#define rep(i, n) for(int i=0; i<(n); ++i)

#define for1(i,a,n) for(int i=(a);i<=(n);++i)

#define for2(i,a,n) for(int i=(a);i<(n);++i)

#define for3(i,a,n) for(int i=(a);i>=(n);--i)

#define for4(i,a,n) for(int i=(a);i>(n);--i)

#define CC(i,a) memset(i,a,sizeof(i))

#define read(a) a=getint()

#define print(a) printf("%d", a)

#define dbg(x) cout << (#x) << " = " << (x) << endl

#define error(x) (!(x)?puts("error"):0)

#define printarr2(a, b, c) for1(_, 1, b) { for1(__, 1, c) cout << a[_][__]; cout << endl; }

#define printarr1(a, b) for1(_, 1, b) cout << a[_] << '\t'; cout << endl

inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }

inline const int max(const int &a, const int &b) { return a>b?a:b; }

inline const int min(const int &a, const int &b) { return a<b?a:b; }

const double eps=1e-10;

double e[55][105][55];

int c, K, n, L[55], R[55];

int main() {

	int cs=getint();

	while(cs--) {

		read(n); read(c); read(K);

		for1(i, 1, K) read(L[i]), read(R[i]);

		for1(k, 1, K+1) rep(i, c) for1(j, 1, n) e[k][i][j]=0;

		for1(i, 1, n) e[1][1][i]=1.0;

		for1(k, 1, K) {

			rep(i, c) for1(j, 1, L[k]-1) e[k+1][i][j]=e[k][i][j];

			rep(i, c) for1(j, R[k]+1, n) e[k+1][i][j]=e[k][i][j];

			rep(b, c) rep(i, c) for1(j, L[k], R[k]) e[k+1][(i*b)%c][j]+=e[k][i][j]/2/c;

			rep(i, c) for1(j, L[k], R[k]) e[k+1][i][j]+=e[k][i][j]/2;

		}

		double ans=0;

		rep(i, c) for1(j, 1, n) ans+=i*e[K+1][i][j];

		printf("%.9f\n", ans);

	}

	return 0;

}

题目描述：

小象喜欢为箱子涂色。小象现在有c种颜色，编号为0~c-1；还有n个箱子，编号为1~n，最开始每个箱子的颜色为1。小象涂色时喜欢遵循灵感：它将箱子按编号排成一排，每次涂色时，它随机选择[L，R]这个区间里的一些箱子（不选看做选0个），为之涂上随机一种颜色。若一个颜色为a的箱子被涂上b色，那么这个箱子的颜色会变成（a*b）mod c。请问在k次涂色后，所有箱子颜色的编号和期望为多少？

输入描述：

第一行为T，表示有T组测试数据。

对于每组数据，第一行为三个整数n,c,k。

接下来k行，每行两个整数Li，Ri，表示第i个操作的L和R。

输出描述：

对于每组测试数据，输出所有箱子颜色编号和的期望值，结果保留9位小数。

样例输入：

3 2 2

2 2

1 3

1 3 1

1 1

5 2 2

3 4

2 4

样例输出：

2.062500000

1.000000000

巴特西

【NOIP模拟题】小象涂色（概率+期望+递推）

最新文章

热门文章