首页 > 代码库 > 【NOIP模拟题】小象涂色（概率+期望+递推）
【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 << endlinline 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 << endlinline 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
3 2 2
2 2
1 3
1 3 1
1 1
5 2 2
3 4
2 4
样例输出：
2.062500000
1.000000000
【NOIP模拟题】小象涂色（概率+期望+递推）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。