# # AtCoder Beginner Contest 189 题解

## # Problem A - Slot (opens new window)

• 时间复杂度$\mathcal{O}(1)$
• 空间复杂度$\mathcal{O}(1)$

use proconio::input;
use proconio::marker::Chars;

fn main() {
input! {
s: Chars,
}
println!("{}", if s[0] == s[1] && s[1] == s[2] {"Won"} else {"Lost"});
}

1
2
3
4
5
6
7
8
9

## # Problem B - Alcoholic (opens new window)

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(1)$

use proconio::input;

fn main() {
input! {
n: usize,
mut x: usize,
liquor: [(usize, usize); n],
}

x *= 100;
let mut tot = 0;
for i in 0..n {
tot += liquor[i].0 * liquor[i].1;
if tot > x {
println!("{}", i + 1);
return;
}
}
println!("-1");
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

## # Problem C - Mandarin Orange (opens new window)

• 时间复杂度$\mathcal{O}(N)$.
• 空间复杂度$\mathcal{O}(N)$.

use proconio::input;
use std::collections::VecDeque;

fn main() {
input! {
n: usize,
mut a: [usize; n],
}

a.push(0);
let mut ans = 0;
let mut dq: VecDeque<(usize, usize)> = VecDeque::new();
for i in 0..=n {
let mut nl = i;
while !dq.is_empty() && dq.back().unwrap().0 > a[i] {
let (h, l) = *dq.back().unwrap();
ans = ans.max(h * (i - l));
dq.pop_back();
nl = l;
}
if dq.is_empty() || dq.back().unwrap().0 < a[i] {
dq.push_back((a[i], nl));
}
}
println!("{}", ans);
}

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

## # Problem D - Logical Expression (opens new window)

(f,t)=\left\{\begin{aligned} & (2f+t,t) & s_i=\text{AND}\\ & (f, 2t+f) & s_i=\text{OR}\end{aligned}\right.

• 时间复杂度$\mathcal{O}(N)$.
• 空间复杂度$\mathcal{O}(1)$.

use proconio::input;

fn main() {
input! {
n: usize,
s: [String; n],
}

let mut f = 1u64;
let mut t = 1u64;

for si in s {
if si == "AND" {
let nf = f * 2 + t;
let nt = t;
f = nf;
t = nt;
} else {
let nf = f;
let nt = t * 2 + f;
f = nf;
t = nt;
}
}

println!("{}", t);
}

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

## # Problem E - Rotate and Flip (opens new window)

• 操作一的结果为$(y,-x)$
• 操作二的结果为$(-y, x)$
• 操作三的结果为$(2p-x,y)$
• 操作四的结果为$(x,2p-y)$

• 操作一：$swap$被翻转，$c_x$$c_y$被交换，$s_x$$s_y$被交换，之后$s_y$$c_y$被翻转。
• 操作二：$swap$被翻转，$c_x$$c_y$被交换，$s_x$$s_y$被交换，之后$s_x$$c_x$被翻转。
• 操作三：$s_x$被翻转，$c_x$翻转后加上$2p$
• 操作四：$s_y$被翻转，$c_y$翻转后加上$2p$

• 如果$swap$false，则结果为$(s_xx_0+c_x,s_yy_0+c_y)$

• 如果$swap$true，则结果为$(s_xy_0+c_x,s_yx_0+c_y)$

• 时间复杂度$\mathcal{O}(Q\log Q)$

• 空间复杂度$\mathcal{O}(Q)$

use proconio::input;
use proconio::marker::Usize1;
use std::cmp::Ordering;

fn main() {
input! {
n: usize,
points: [(i64, i64); n],
m: usize,
}

let mut ops: Vec<(usize, i64)> = vec![];
for _i in 0..m {
input! {
t: usize,
}
if t <= 2 {
ops.push((t, 0));
} else {
input! {
p: i64,
}
ops.push((t, p));
}
}

input! {
q: usize,
queries: [(usize, Usize1); q],
}

let mut ans = vec![(0i64, 0i64); q];
let mut order: Vec<usize> = (0..q).collect();
order.sort_by(|a, b| if queries[*a].0 <= queries[*b].0 {
Ordering::Less
} else {
Ordering::Greater
});

let mut swap = false;
let mut sx = 1i64;
let mut sy = 1i64;
let mut cx = 0i64;
let mut cy = 0i64;
let mut op = 0usize;
for i in order {
let (a, b) = queries[i];
while op < a {
let (t, p) = ops[op];
match t {
1 => {
swap = !swap;
std::mem::swap(&mut cx, &mut cy);
std::mem::swap(&mut sx, &mut sy);
sy = -sy;
cy = -cy;
},
2 => {
swap = !swap;
std::mem::swap(&mut cx, &mut cy);
std::mem::swap(&mut sx, &mut sy);
sx = -sx;
cx = -cx;
},
3 => {
sx = -sx;
cx = p * 2 - cx;
},
4 => {
sy = -sy;
cy = p * 2 - cy;
},
_ => {

}
}
op += 1;
}
if swap {
ans[i] = (points[b].1 * sx + cx, points[b].0 * sy + cy);
} else {
ans[i] = (points[b].0 * sx + cx, points[b].1 * sy + cy);
}
}

for i in 0..q {
println!("{} {}", ans[i].0, ans[i].1);
}
}

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

## # Problem F - Sugoroku2 (opens new window)

• 我们有一项任务，成功的概率为$p_s$，成功的花费为$E_s$；失败的概率为$p_f=1-p_s$，花费为$E_f$
• 如果成功了，我们即刻停止；否则我们将再次尝试。
• 最后的总花费的期望是多少？

$E=E_sp_s+(E_f+E_s)p_fp_s+(2E_f+E_s)p_f^2p_s+\cdots$

$E_sp_s+p_fp_s((E_f+E_s)+(2E_f+E_s)p_f+\cdots)$

$\sum_s=E_s+E_sp_f+E_sp_f^2+\cdots=E_s\frac{1}{1-p_f}=\frac{E_s}{p_s}$

$\sum_f=E_f+2E_fp_f+3E_fp_f^2+\cdots$

$\sum_fp_f=E_fp_f+2E_fp_f^2+\cdots$

$(1-p_f)\sum_f=E_f(1+p_f+p_f^2+\cdots)=E_f\frac{1}{1-p_f}=\frac{E_f}{p_s}$

$\sum_f=\frac{E_f}{p_s^2}$

$E=E_sp_s+p_fp_s(\sum_f+\sum_s)=E_sp_s+p_fp_s(\frac{E_s}{p_s}+\frac{E_f}{p_s^2})=E_sp_s+(1-p_s)(E_s+\frac{E_f}{p_s})$

$p_i=\frac{\sum_p}{M}$

$E_i=\frac{\sum p_j(E_j+1)}{\sum_p}=1+\frac{\sum p_jE_j}{\sum_p}$

$p_iE_i=\frac{\sum_p}{M}+\frac{\sum p_jE_j}{M}$

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(N)$

use proconio::input;

fn main() {
input! {
n: usize,
m: usize,
k: usize,
a: [usize; k],
}

let mut broken = vec![false; n + 1];
for i in a {
broken[i] = true;
}

let mut prob_exp = vec![0.0; n + 1];
let mut prob = vec![0.0; n + 1];
prob[0] = 1.0;

let mut prob_sum: f64 = 1.0;
let mut exp_sum: f64 = 0.0;

if m >= n {
let goal_pct = (m - n + 1) as f64 / m as f64;
prob[n] += prob[0] * goal_pct;
prob_exp[n] += (prob_exp[0] + prob[0]) * goal_pct;
}

let mut prob_exp_fail = 0.0;

for i in 1..n {
prob[i] = prob_sum / m as f64;
prob_exp[i] = prob[i] + exp_sum / m as f64;
if !broken[i] {
prob_sum += prob[i];
exp_sum += prob_exp[i];
if i + m >= n {
let goal_pct = (i + m - n + 1) as f64 / m as f64;
prob[n] += prob[i] * goal_pct;
prob_exp[n] += (prob_exp[i] + prob[i]) * goal_pct;
}
} else {
prob_exp_fail += prob_exp[i];
}
if i >= m && !broken[i - m] {
prob_sum -= prob[i - m];
exp_sum -= prob_exp[i - m];
}
}

if prob[n] < 1e-8 {
println!("-1");
} else if (prob[n] - 1.0).abs() < 1e-8 {
println!("{}", prob_exp[n]);
} else {
let exp_fail = prob_exp_fail / (1.0 - prob[n]);
println!("{}", prob_exp[n] + (1.0 - prob[n]) * (prob_exp[n] + exp_fail) / prob[n]);
}
}

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