一.D - increment of coins (atcoder.jp)
（1）题目大意
给定你金银铜牌的数量，每次你能等概率的从里面随机抽取一枚牌，然后放回两枚同样颜色的牌，现在问你，当有某个袋中有一百个牌就不执行操作，问你操作次数的期望。
（2）解题思路
很容易想到当100枚币在一块的时候，我们的操作就结束了，因此期望次数为0，因此我们定义dp[a][b][c]为金牌有a，银牌有b，铜牌有c的期望操作次数。因此把每一个状态加上多一个状态的操作次数期望就可以了，最终答案就是dp[a][b][c]。
（3）代码实现
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#include "bits/stdc++.h" using namespace std; const int N = 101; double dp[N][N][N]; double f(int a,int b,int c) { if(a == 100 || b == 100 || c == 100) return dp[a][b][c] = 0; if(dp[a][b][c] > -1) return dp[a][b][c]; dp[a][b][c] = 0; dp[a][b][c] += (f(a + 1,b,c) + 1.0) * a / (1.0 * a + b + c); dp[a][b][c] += (f(a,b + 1,c) + 1.0) * b / (1.0 * a + b + c); dp[a][b][c] += (f(a,b,c + 1) + 1.0) * c / (1.0 * a + b + c); return dp[a][b][c]; } void solve() { int a,b,c; cin >> a >> b >> c; memset(dp,-1,sizeof(dp)); cout << fixed << setprecision(9) << f(a,b,c) << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int T; T = 1; while(T --) { solve(); } return 0; }
二.Problem - F - Codeforces
（1）题目大意
给定你一个序列，有两个操作，第一个操作是把第i个数改为x，第二个操作询问l，r中每个数的数量是否是k的倍数，如果是，则输出YES，否则输出NO。
（2）解题思路
对于每个询问我没补可能直接做，套数据结构直接做也是不现实的问题，因为有个带修的操作，因此我们考虑一个概率，我们把原数组里面每个数和查询的数都离散化一下。我们已知一个性质若又区间里面的所有个数都是k的倍数，那么s % k == 0,若我们反过来推，则这个性质不一定成立，但是我们可以多验证40次，每一次失败的概率都是1/2，若我们验证40次，有一次失败，那我们则认为他就是失败的，否则认为他是成功的，那么这样答案不正确的概率仅仅为1/2^40。因此我们需要随机40*N个数，存放到每一次验证中，采用线性同余法生成随机数，对于区间和查询，我们只需要建立40个树状数组即可。
（3）代码实现
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89#include "bits/stdc++.h" using namespace std; using ll = long long; const int N = 3e5 + 10; long long s[40][N]; int num[40][N],a[N]; int n,q,loc; struct qry {int op,l,r,x;}qr[N]; int lowbit(int x) { return x & -x; } void add(int now,int p,int v) { while(p <= n) { s[now][p] += v; p += lowbit(p); } } ll query(int now,int p) { ll res = 0; while(p > 0) { res += s[now][p]; p -= lowbit(p); } return res; } unsigned int seed = 1e9+7; int Random() { seed = (seed << 10) + (seed >> 10) + seed + 1e9 + 7; return seed / 2; } void solve() { cin >> n >> q; vector <int> all; for(int i = 1;i <= n;i++) { cin >> a[i]; all.push_back(a[i]); } for(int i = 1;i <= q;i++) { cin >> qr[i].op; if(qr[i].op == 1) { cin >> qr[i].l >> qr[i].r; all.push_back(qr[i].r); } else cin >> qr[i].l >> qr[i].r >> qr[i].x; } sort(all.begin(),all.end()); all.erase(unique(all.begin(),all.end()),all.end()); for(int i = 0;i < all.size();i++) for(int j = 1;j <= 37;j++) num[j][i] = Random(); for(int i = 1;i <= n;i++) { a[i] = lower_bound(all.begin(),all.end(),a[i]) - all.begin(); for(int j = 1;j <= 37;j++) add(j,i,num[j][a[i]]); } for(int i = 1;i <= q;i++) { if(qr[i].op == 2) { bool ok = true; for(int j = 1;j <= 37;j++) { if((query(j,qr[i].r) - query(j,qr[i].l - 1)) % qr[i].x) { ok = false; break; } } if(!ok) cout << "NO" << endl; else cout << "YES" << endl; } else { qr[i].r = lower_bound(all.begin(),all.end(),qr[i].r) - all.begin(); for(int j = 1;j <= 37;j++) { add(j,qr[i].l,num[j][qr[i].r] - num[j][a[qr[i].l]]); } a[qr[i].l] = qr[i].r; } } } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); int T; T = 1; while(T --) solve(); return 0; }
三.E - Critical Hit (atcoder.jp)
（1）题目大意
给你一个怪兽的血量n，和攻击概率p，让怪兽掉1滴血的概率为1-p/100，让怪兽掉两滴血的概率是p/100，问你使怪兽变成0滴血或者更低的期望次数是多少？ 
（2）解题思路
考虑概率dp，对于有i滴血的状态可以从i-1和i-2分别加一次转移过来，注意一定要加1（被自己犯傻笑到了）。
转移方程为
dp[i] += (dp[i - 1] + 1) * (1-p) / 100
dp[i] += (dp[i - 2] + 1) * p / 100
（3）代码实现
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
51
52
53
54
55
56
57
58
59
60// Problem: E - Critical Hit // Contest: AtCoder - Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280) // URL: https://atcoder.jp/contests/abc280/tasks/abc280_e // Memory Limit: 1024 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org) #include "bits/stdc++.h" #define rep(i, z, n) for (int i = z; i <= n; i++) #define per(i, n, z) for (int i = n; i >= z; i--) #define ll long long #define db double #define PII pair<int, int> #define fi first #define se second #define vi vector<int> #define yes cout << "YES" << endl; #define no cout << "NO" << endl; using namespace std; const int N = 2e5 + 10; const int mod = 998244353; ll dp[N]; ll ksm(ll a, ll p) { ll res = 1; while (p) { if (p & 1) res = res * a % mod; a = a * a % mod; p >>= 1; } return res; } void solve() { int n, p; cin >> n >> p; ll tmp1 = 1LL * (100 - p) * ksm(100, mod - 2) % mod; ll tmp2 = 1LL * p * ksm(100, mod - 2) % mod; dp[0] = 0; for (int i = 1; i <= n; i++) { dp[i] += (dp[max(0, i - 1)] + 1) * tmp1 % mod; dp[i] += (dp[max(0, i - 2)] + 1) * tmp2 % mod; dp[i] %= mod; } cout << dp[n] << endl; } int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int T = 1; // cin >> T; while (T--) solve(); return 0; }
四.Problem - D - Codeforces
（1）题目大意
有两个长度为n的01串分别为a和b，每一次操作你都能随机选择一个位置翻转他，问你把这两个字符串相等的期望操作次数是多少？
（2）解题思路
考虑期望DP：dp[i]表示已经有i-1个相同，正在凑第i个。
状态转移方程为：dp[i+1]=从不相同的选一个期望+从相同选一个的期望次数
dp[i+1]=(n-i)/n+i/n*(dp[i]+dp[i+1]+1)
移项的 dp[i+1]=(n+i*dp[i])/(n-i)
（3）代码实现
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#include "bits/stdc++.h" #define rep(i,z,n) for(int i = z;i <= n; i++) #define per(i,n,z) for(int i = n;i >= z; i--) #define PII pair<int,int> #define fi first #define se second #define vi vector<int> #define vl vector<ll> #define pb push_back #define sz(x) (int)x.size() #define all(x) (x).begin(),(x).end() using namespace std; using ll = long long; const int N = 1e6 + 10; char a[N],b[N]; ll inv[N]; const ll mod = 998244353; void init() { int n=1e6; inv[1]=inv[0]=1; rep(i,1,n)inv[i+1]=(1ll*(mod-mod/(i+1)))*inv[mod%(i+1)]%mod; } ll dp[N]; void solve() { int n,cnt=0; ll ans=0; cin>>n; cin>>(a+1)>>(b+1); dp[1]=1; rep(i,1,n-1)dp[i+1]=(n+i*dp[i]%mod)*inv[n-i]%mod; rep(i,1,n) if(a[i]==b[i])cnt++; rep(i,cnt+1,n)ans=(ans+dp[i])%mod; cout<<ans<<endl; } int main() { ios::sync_with_stdio(false); cin.tie(0),cout.tie(0); init(); int T = 1; cin >> T; while(T --) solve(); return 0; }
最后
以上就是甜甜斑马最近收集整理的关于概率/期望类Dp列题的全部内容，更多相关概率/期望类Dp列题内容请搜索靠谱客的其他文章。
发表评论 取消回复