AtCoder ABC189 简单题解（目前完成到 D 题，缺 E 和 F）_atcoder rmq

由于开始忙起来，没有很多时间写详细题解。先简单写一个 ABC189 各题的思路。

A - Slot

题目链接，https://atcoder.jp/contests/abc189/tasks/abc189_a。

签到题，不说也罢。字符读入，然后分析。

B - Alcoholic

题目链接，https://atcoder.jp/contests/abc189/tasks/abc189_b。

根据题目意思，我们知道要对所有摄入的酒精进行累加求和。总酒精摄入计算公式如下：

$ans=\sum_{i=1}^{N}V_{i}*P{i}$。

如果 $ans>100*X$ 说明喝多了，否则还没有够。

本题注意的细节是不要使用浮点数比较。本题的数据给得比较巧妙，用浮点数比较有些样例会通不过。

C - Mandarin Orange

题目链接，https://atcoder.jp/contests/abc189/tasks/abc189_c。

本题的考点是数据结构的 RMQ 问题，即 Range Minimum/Maximum Query 问题。直接套用模板，建立 ST 表。

D - Logical Expression

题目链接，https://atcoder.jp/contests/abc189/tasks/abc189_d。

本题是一个简单的动态规划问题。状态方程如下：

$(f, t)=\left\{\begin{matrix} (2f+t, t), s_i = \text AND \\ (f, 2t+f), s_i = \text OR \end{matrix}\right.$，其中 $f$ 表示变成 false 的方法数量；$t$ 表示变成 true 的方法数量。

E - Rotate and Flip

题目链接，https://atcoder.jp/contests/abc189/tasks/abc189_e。

F - Sugoroku2

题目链接，https://atcoder.jp/contests/abc189/tasks/abc189_f。

道歉，后面都是课，先占一个坑，估计要明天才能填坑。