[Codeforces] probabilities (R1600) Part.1
[Codeforces] probabilities (R1600) Part.1
题单:https://codeforces.com/problemset?tags=probabilities,0-1600
9A. Die Roll
原题指路:https://codeforces.com/problemset/problem/9/A
题意
三个人丢写着数字 1 ∼ 6 1\sim 6 1∼6的六面骰子,其中前两人得到的数字分别为 a , b ( 1 ≤ a , b ≤ b ) a,b\ \ (1\leq a,b\leq b) a,b (1≤a,b≤b).若第三个人得到的数字不小于另外两个人得到的数字,则他胜.求他胜的概率,输出既约分数的形式.
思路
显然 a n s = 6 − max { a , b } + 1 6 ans=\dfrac{6-\max\{a,b\}+1}{6} ans=66−max{a,b}+1.
代码
void solve() {
int a, b; cin >> a >> b;
int up = 6 - max(a, b) + 1, down = 6;
int g = gcd(up, down);
up /= g, down /= g;
cout << up << '/' << down;
}
int main() {
solve();
}
107B. Basketball Team
原题指路:https://codeforces.com/problemset/problem/107/B
题意
小明是包含 n n n个队员的队伍中的一员.队员来自不同专业.有编号 1 ∼ m 1\sim m 1∼m的 m m m个专业,其中人数分别为 s 1 , ⋯ , s n s_1,\cdots,s_n s1,⋯,sn,小明来自专业 h ( 1 ≤ h ≤ m ) h\ \ (1\leq h\leq m) h (1≤h≤m).求小明至少有一个同专业的队友的概率,误差不超过 1 e − 6 1\mathrm{e}-6 1e−6.若组成队伍的人数不足,输出 − 1 -1 −1.
第一行输入三个整数 n , m , h ( 1 ≤ n ≤ 100 , 1 ≤ m ≤ 1000 , 1 ≤ h ≤ m ) n,m,h\ \ (1\leq n\leq 100,1\leq m\leq 1000,1\leq h\leq m) n,m,h (1≤n≤100,1≤m≤1000,1≤h≤m).第二行输入 m m m个整数 s 1 , ⋯ , s n ( 1 ≤ s i ≤ 100 ) s_1,\cdots,s_n\ \ (1\leq s_i\leq 100) s1,⋯,sn (1≤si≤100),其中 s h s_h sh包含小明.
思路
1 1 1减不含队友的概率即可.
代码
void solve() {
int n, m, h; cin >> n >> m >> h;
vi s(m);
for (int i = 0; i < m; i++) cin >> s[i];
n--, s[--h]--; // 除掉小明
int sum = 0;
for (int i = 0; i < m; i++) sum += s[i];
if (sum < n) {
cout << -1;
return;
}
double ans = 1;
for (int i = 0; i < n; i++) ans *= 1 - (double)s[h] / (sum--);
cout << fixed << setprecision(12) << 1 - ans << endl;
}
int main() {
solve();
}
312B. Archer
原题指路:https://codeforces.com/problemset/problem/312/B
题意 ( 2 s 2\ \mathrm{s} 2 s)
A和B打枪,A先手,他们射中的概率分别为 a b \dfrac{a}{b} ba和 c d \dfrac{c}{d} dc.第一个射中者胜.求A获胜的概率,误差不超过 1 e 6 1\mathrm{e}6 1e6.
第一行输入四个整数 a , b , c , d ( 1 ≤ a , b , c , d ≤ 1000 , 0 < a b , c d < 1 ) a,b,c,d\ \ \left(1\leq a,b,c,d\leq 1000,0<\dfrac{a}{b},\dfrac{c}{d}<1\right) a,b,c,d (1≤a,b,c,d≤1000,0<ba,dc<1).
思路
两人各打一次为一轮,则一轮中两人都没射中的概率为 q = ( 1 − a b ) ( 1 − c d ) q=\left(1-\dfrac{a}{b}\right)\left(1-\dfrac{c}{d}\right) q=(1−ba)(1−dc).设A获胜前经过了 n n n轮,则 a n s = p ∑ i = 0 n − 1 q i \displaystyle ans=p\sum_{i=0}^{n-1} q^i ans=pi=0∑n−1qi.令 n → ∞ n\rightarrow\infty n→∞得 a n s = p 1 − q ans=\dfrac{p}{1-q} ans=1−qp.
代码
void solve() {
int a, b, c, d; cin >> a >> b >> c >> d;
double p = (double)a / b, q = (1 - (double)c / d) * (1 - (double)a / b);
cout << fixed << setprecision(12) << p / (1 - q);
}
int main() {
solve();
}
345A. Expecting Trouble
原题指路:https://codeforces.com/problemset/problem/345/A
题意 ( 2 s ) (2\ \mathrm{s}) (2 s)
给定一个 0 − 1 0-1 0−1序列,其中 0 0 0表示好日子, 1 1 1表示坏日子, ? ? ?表示有 p p p的概率为坏日子,有 ( 1 − p ) (1-p) (1−p)的概率为好日子.求坏日子的期望天数.
思路
直接计算即可.
本题是节日题,要求用Ada语言实现.
代码
with Ada.Text_IO; use Ada.Text_IO;
with Ada.Float_Text_IO; use Ada.Float_Text_IO;
procedure a is
str: string(1..100);
l: natural;
x, p: float;
begin
get_line(str, l);
get(p);
x := 0.0;
for i in 1..l loop
if str(i) = '1' then x := x + 1.0;
elsif str(i) = '?' then x := x + p;
end if;
end loop;
x := x / float(l);
put(x, 0, 5, 0);
end;
453A. Little Pony and Expected Maximum
原题指路:https://codeforces.com/problemset/problem/453/A
题意
给定一个 m ( 1 ≤ m ≤ 1 e 5 ) m\ \ (1\leq m\leq1\mathrm{e}5) m (1≤m≤1e5)个面的骰子,其中每个面上写有数字 1 ∼ m 1\sim m 1∼m.求投掷 n ( 1 ≤ n ≤ 1 e 5 ) n\ \ (1\leq n\leq1\mathrm{e}5) n (1≤n≤1e5)次后能得到的最大值的期望.
思路
即给定 n n n个取值范围为 [ 1 , m ] ⋂ Z [1,m]\bigcap\mathbb{Z} [1,m]⋂Z的随机变量 X 1 , ⋯ , X n X_1,\cdots,X_n X1,⋯,Xn,求 max { X 1 , ⋯ , X n } \max\{X_1,\cdots,X_n\} max{X1,⋯,Xn}的期望.
由离散随机变量的前缀和性: P ( X = k ) = P ( X ≤ k ) − P ( X ≤ k − 1 ) P(X=k)=P(X\leq k)-P(X\leq k-1) P(X=k)=P(X≤k)−P(X≤k−1).
E ( X ) = ∑ i = 1 m i ⋅ P ( X = i ) = ∑ i = 1 m i ⋅ [ P ( X ≤ i ) − P ( X ≤ i − 1 ) ] = ∑ i = 1 m i ⋅ [ ( i m ) n − ( i − 1 m ) n ] \displaystyle E(X)=\sum_{i=1}^m i\cdot P(X=i)=\sum_{i=1}^m i\cdot [P(X\leq i)-P(X\leq i-1)]=\sum_{i=1}^m i\cdot\left[\left(\dfrac{i}{m}\right)^n-\left(\dfrac{i-1}{m}\right)^n\right] E(X)=i=1∑mi⋅P(X=i)=i=1∑mi⋅[P(X≤i)−P(X≤i−1)]=i=1∑mi⋅[(mi)n−(mi−1)n].
代码
void solve() {
int m, n; cin >> m >> n;
double ans = 0;
for (int i = 1; 4i <= m; i++)
ans += i * (pow((double)i / m, n) - pow((double)(i - 1) / m, n));
cout << fixed << setprecision(8) << ans;
}
int main() {
solve();
}
476B. Dreamoon and WiFi
原题指路:https://codeforces.com/problemset/problem/476/B
题意
某人在数轴上移动,初始时在原点.给定一个只包含字符’+‘和’-‘的字符串 s 1 s_1 s1,其中’+‘表示向右移动一个单位,’-‘表示向左移动一个单位.给定一个与 s 1 s_1 s1等长的、只包含字符’+‘、’-‘和’?‘的字符串 s 2 s_2 s2,其中’?‘等概率地取’+‘或’-'.分别进行操作 s 1 s_1 s1和操作 s 2 s_2 s2,求最后停在同一位置的概率,误差不超过 1 e − 9 1\mathrm{e}-9 1e−9.
第一行输入一个只包含字符’+‘和’-‘的字符串 s 1 s_1 s1.第二行输入一个与 s 1 s_1 s1等长的、只包含字符’+‘、’-‘和’?'的字符串 s 2 s_2 s2.数据保证两字符串的长度都不超过 10 10 10.
思路I
显然操作 s 1 s_1 s1后停在的位置 t a r g e t target target可求得.
显然 s 2 s_2 s2中’?‘的位置不影响概率,可先求出只操作 s 2 s_2 s2中确定的字符后停在的位置 l a s t last last,并统计 s 2 s_2 s2中’?'的个数 u n k n o w n unknown unknown.
考察两终点的距离(相差的 + 1 +1 +1数) d i s = t a r g e t − l a s t dis=target-last dis=target−last.
① d i s dis dis与 u n k n o w n unknown unknown奇偶性不同或 u n k n o w n < a b s ( d i s ) unknown<abs(dis) unknown<abs(dis)时无解,概率为 0 0 0.
②设从 l a s t last last走到 t a r g e t target target所需的步数为 n e e d need need,则 n e e d − ( u n k n o w n − n e e d ) = ∣ d i s ∣ need-(unknown-need)=|dis| need−(unknown−need)=∣dis∣,解得 n e e d = ⌊ u n k n o w n + ∣ d i s ∣ 2 ⌋ need=\left\lfloor\dfrac{unknown+|dis|}{2}\right\rfloor need=⌊2unknown+∣dis∣⌋.
a n s = C u n k n o w n n e e d 2 u n k n o w n ans=\dfrac{C_{unknown}^{need}}{2^{unknown}} ans=2unknownCunknownneed.
代码I
void solve() {
string s1, s2; cin >> s1 >> s2;
int target = 0; // s1序列的终点
for (int i = 0; i < s1.length(); i++)
target += s1[i] == '+' ? 1 : -1;
int last = 0; // s2已知序列的终点
int unknown = 0; // s2中的?数
for (int i = 0; i < s2.length(); i++) {
if (s2[i] == '?') unknown++;
else last += s2[i] == '+' ? 1 : -1;
}
int dis = target - last; // 两终点相差的+1数
if ((dis + unknown & 1) || unknown < abs(dis)) {
cout << 0;
return;
}
int need = unknown + abs(dis) >> 1; // 到达终点所需的步数
int ans = 1;
for (int i = 0; i < need; i++) ans *= unknown - i;
for (int i = 2; i <= need; i++) ans /= i;
cout << fixed << setprecision(18) << (double)ans / (1 << unknown);
}
int main() {
solve();
}
思路II
因’?‘的个数至多有 10 10 10个,可枚举每个’?'取何值.
思路III
d p [ i ] [ j ] dp[i][j] dp[i][j]表示走到第 i i i个问号时坐标为 j j j的概率.
状态转移方程 d p [ i ] [ j ] = d p [ i − 1 ] [ j − 1 ] ∗ 0.5 + d p [ i − 1 ] [ j + 1 ] ∗ 0.5 dp[i][j]=dp[i-1][j-1]*0.5+dp[i-1][j+1]*0.5 dp[i][j]=dp[i−1][j−1]∗0.5+dp[i−1][j+1]∗0.5.
因坐标可能为负,第二维加一个 B A S E = 10 BASE=10 BASE=10的偏移值即可.
代码III
const int MAXN = 25; // 两倍空间
const int BASE = 10; // 偏移量
string s1, s2;
double dp[MAXN][MAXN]; // dp[i][j]表示走到第i个问号时坐标为j的概率
void solve() {
cin >> s1 >> s2;
int pos1 = 0, pos2 = 0, cnt = 0;
for (int i = 0; i < s1.length(); i++) {
pos1 += s1[i] == '+' ? 1 : -1;
if (s2[i] == '?') cnt++;
else pos2 += s2[i] == '+' ? 1 : -1;
}
dp[0][pos2 + BASE] = 1;
for (int i = 1; i <= cnt; i++) {
for (int j = -10; j <= 10; j++) // 枚举下标
dp[i][j + BASE] = dp[i - 1][j - 1 + BASE] * 0.5 + dp[i - 1][j + 1 + BASE] * 0.5;
}
cout << fixed << setprecision(18) << dp[cnt][pos1 + BASE];
}
int main() {
solve();
}
839C. Journey
原题指路:https://codeforces.com/problemset/problem/839/C
题意 ( 2 s ) (2\ \mathrm{s}) (2 s)
给定一棵包含编号 1 ∼ n 1\sim n 1∼n的 n n n个节点的、边长都为 1 1 1的树.某人从节点 1 1 1出发,每次等概率地选择一个与当前节点相邻的且之前未经过的节点,行走到该节点,若不存在这样的节点,则结束.求经过的路径长度的期望,误差不超过 1 e − 6 1\mathrm{e}-6 1e−6.
第一行输入一个整数 n ( 1 ≤ n ≤ 1 e 5 ) n\ \ (1\leq n\leq 1\mathrm{e}5) n (1≤n≤1e5).接下来 ( n − 1 ) (n-1) (n−1)行每行输入两个整数 u , v ( 1 ≤ u , v ≤ n , u ≤ v ) u,v\ \ (1\leq u,v\leq n,u\leq v) u,v (1≤u,v≤n,u≤v),表示节点 u u u与节点 v v v间存在边.数据保证给定边构成一棵树.
思路
设以节点 u u u为起点的的答案为 d p [ u ] dp[u] dp[u].显然 d p [ u ] = ∑ v ∈ s o n u d p [ v ] + 1 \displaystyle dp[u]=\sum_{v\in son_u} dp[v]+1 dp[u]=v∈sonu∑dp[v]+1.每个节点对期望的贡献为路径长度之和除以路径数.
代码
const int MAXN = 2e5 + 5;
int n;
vi edges[MAXN];
double dfs(int u, int fa) { // 当前节点、前驱节点
double res = 0;
for (auto v : edges[u]) {
if (v == fa) continue;
res += dfs(v, u) + 1;
}
return sgn(res) < eps ? 0 : res / (edges[u].size() - (fa != -1));
}
void solve() {
cin >> n;
for (int i = 1; i < n; i++) {
int u, v; cin >> u >> v;
edges[u].push_back(v), edges[v].push_back(u);
}
cout << fixed << setprecision(12) << dfs(1, -1);
}
int main() {
solve();
}
930B. Game with String
原题指路:https://codeforces.com/problemset/problem/930/B
题意 ( 2 s ) (2\ \mathrm{s}) (2 s)
给定一个长度为 l e n len len的字符串 s s s.现有操作:选一个整数 k ∈ [ 0 , l e n − 1 ] k\in [0,len -1] k∈[0,len−1],将 s s s循环左移 k k k位,即变为 t = s k + 1 ⋯ s n s 1 ⋯ s k t=s_{k+1}\cdots s_n s_1\cdots s_k t=sk+1⋯sns1⋯sk.初始时给定 t t t的首字符,你可询问 t t t串的某位置的另一字符,问能唯一确定 k k k的概率,误差不超过 1 e − 6 1\mathrm{e}-6 1e−6.注意可能能确定但非一定能唯一确定视为不能确定.
第一行输入一个长度不超过 5000 5000 5000的、只包含小写英文字母的字符串.
思路
设与字符 c h 1 ch_1 ch1相距 l e n len len的字符为 c h 2 ch_2 ch2.考察三元组 ( c h 1 , l e n , c h 2 ) (ch_1,len,ch_2) (ch1,len,ch2),则当且仅当这样的三元组在串中恰出现一次才能唯一确定 k k k.
循环移位相当于将 s s s倍增. c n t [ c h 1 ] [ l e n ] [ c h 2 ] cnt[ch_1][len][ch_2] cnt[ch1][len][ch2]表示字符 c h 1 ch_1 ch1相距 l e n len len的字符为 c h 2 ch_2 ch2的出现次数.枚举每个下标作为首字符,预处理出所有的 c n t [ ] [ ] [ ] cnt[][][] cnt[][][],统计 c n t [ ] [ ] [ ] = 1 cnt[][][]=1 cnt[][][]=1的个数即可.
代码
const int MAXN = 5005, MAXM = 26;
int n;
string s;
int cnt[MAXM][MAXN][MAXM]; // cnt[ch1][len][ch2]表示与字符ch1相距len的字符为ch2的出现次数
void solve() {
cin >> s;
n = s.length();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
int len = j - i;
if (len < 0) len += n;
cnt[s[i] - 'a'][len][s[j] - 'a']++;
}
}
int ans = 0;
for (int i = 0; i < 26; i++) { // 枚举字符
int res = 0;
for (int j = 1; j < n; j++) { // 枚举长度
int tot = 0; // cnt[][][]为1的个数
for (int k = 0; k < 26; k++) tot += cnt[i][j][k] == 1;
res = max(res, tot);
}
ans += res;
}
cout << fixed << setprecision(12) << (double)ans / n;
}
int main() {
solve();
}
1459A. Red-Blue Shuffle
原题指路:https://codeforces.com/problemset/problem/1459/A
题意 ( 2 s ) (2\ \mathrm{s}) (2 s)
有编号 1 ∼ n 1\sim n 1∼n的 n n n张卡片,每张卡片上分别有一个红色数码 r 1 , ⋯ , r n r_1,\cdots,r_n r1,⋯,rn和蓝色数码 b 1 , ⋯ , b n b_1,\cdots,b_n b1,⋯,bn.现将所有卡片排序,等概率地对应一个 1 ∼ n 1\sim n 1∼n的全排列,后依次读出每张卡片上的红色数码得到数字 R R R,依次读出每张卡片上的蓝色数码得到数字 B B B.若 R > B R>B R>B则红色胜出;若 R < B R<B R<B则蓝色胜出;否则平局.若红色胜出的概率严格大,输出"RED";若蓝色胜出的概率严格大,输出"BLUE";否则输出"EQUAL".
有 t ( 1 ≤ t ≤ 100 ) t\ \ (1\leq t\leq 100) t (1≤t≤100)组测试数据.每组测试数据第一行输入一个整数 n ( 1 ≤ n ≤ 1000 ) n\ \ (1\leq n\leq 1000) n (1≤n≤1000).第二行输入 n n n个数码 r 1 , ⋯ , r n r_1,\cdots,r_n r1,⋯,rn.第三行输入 n n n个数码 b 1 , ⋯ , b n b_1,\cdots,b_n b1,⋯,bn.
思路
对每个下标 i ∈ [ 1 , n ] i\in[1,n] i∈[1,n]:
(1)若 r i = b i r_i=b_i ri=bi,显然该数码对双方获胜的概率无影响.
(2)若 r i ≠ b i r_i\neq b_i ri=bi,更新 s [ i ] > t [ i ] s[i]>t[i] s[i]>t[i]和 s [ i ] < t [ i ] s[i]<t[i] s[i]<t[i]的下标的个数 c n t 1 cnt1 cnt1和 c n t 2 cnt2 cnt2.
①若最终 c n t 1 > c n t 2 cnt1>cnt2 cnt1>cnt2,则红色胜出的概率严格大.
②若最终 c n t 1 < c n t 2 cnt1<cnt2 cnt1<cnt2,则蓝色胜出的概率严格大.
③若最终 c n t 1 = c n t 2 cnt1=cnt2 cnt1=cnt2,则两颜色胜出的概率相等.
代码
void solve() {
int n; cin >> n;
string s, t; cin >> s >> t;
int cnt1 = 0, cnt2 = 0; // s[i]>和<t[i]的个数
for (int i = 0; i < n; i++) {
if (s[i] != t[i]) {
if (s[i] > t[i]) cnt1++;
else cnt2++;
}
}
if (cnt1 == cnt2) cout << "EQUAL" << endl;
else cout << (cnt1 > cnt2 ? "RED" : "BLUE") << endl;
}
int main() {
CaseT // 单测时注释掉该行
solve();
}
1461C. Random Events
原题指路:https://codeforces.com/problemset/problem/1461/C
题意 ( 2 s ) (2\ \mathrm{s}) (2 s)
给定一个 1 ∼ n 1\sim n 1∼n的排列 a 1 , ⋯ , a n a_1,\cdots,a_n a1,⋯,an.现有 m m m个操作,每个操作记作 ( r , p ) (r,p) (r,p),表示有 p p p的概率将 a [ 1... r ] a[1...r] a[1...r]升序排列.依次做 m m m个操作,求最后将序列升序排列的概率,误差不超过 1 e − 6 1\mathrm{e}-6 1e−6.
有 t ( 1 ≤ t ≤ 100 ) t\ \ (1\leq t\leq 100) t (1≤t≤100)组测试数据.每组测试数据第一行输入两个整数 n , m ( 1 ≤ n , m ≤ 1 e 5 ) n,m\ \ (1\leq n,m\leq 1\mathrm{e}5) n,m (1≤n,m≤1e5).第二行输入一个 1 ∼ n 1\sim n 1∼n的排列 a 1 , ⋯ , a n a_1,\cdots,a_n a1,⋯,an.接下来 m m m行每行输入一个整数 r ( 1 ≤ r ≤ n ) r\ \ (1\leq r\leq n) r (1≤r≤n)和一个实数 p ( 0 ≤ p ≤ 1 ) p\ \ (0\leq p\leq 1) p (0≤p≤1),表示一个操作.数据保证所有测试数据的 n n n之和、 m m m之和都不超过 1 e 5 1\mathrm{e}5 1e5.
思路
记最大的 s . t . a i ! = i \ s.t.\ a_i!=i s.t. ai!=i的下标 i i i为 p o s pos pos.显然答案与 r < p o s r<pos r<pos的操作无关,则只需考察 r ≥ p o s r\geq pos r≥pos的操作,将它们排序失败的概率 ( 1 − p ) (1-p) (1−p)相乘后,用 1 1 1减去该概率即可.
代码
void solve() {
int n, m; cin >> n >> m;
vi a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i];
int pos = n;
while (pos >= 1 && a[pos] == pos) pos--;
double ans = pos ? 1 : 0;
while (m--) {
int r; double p; cin >> r >> p;
if (r >= pos) ans *= 1 - p;
}
cout << fixed << setprecision(12) << 1 - ans << endl;
}
int main() {
CaseT // 单测时注释掉该行
solve();
}