A - Luogu P2719 搞笑世界杯#

Problem Statement

This is a straightforward problem. We can solve it easily using DP.

DP State:
Let $dp[i][j]$ denote the probability that A and B end up with the same type of ticket when there are $i$ A-type tickets and $j$ B-type tickets remaining.

Answer:
Obviously, the final answer is $dp[n][n]$.

Initialization:
When only one type of ticket remains, A and B will get the same type for sure, except for the case where only one ticket is left.
So we have: $dp[i][0] = dp[0][i] = 1$ for $i \ge 2$.

State Transition:
Each ticket is sold based on a fair coin flip, so each choice has a probability of 50%. Therefore,

I won’t include the code here since the implementation is straightforward.

B - Luogu P8804 [蓝桥杯 2022 国 B] 故障#

Problem Statement

The basic application of Bayes’ formula.

The original statement is long and packed with information, which makes it hard to follow at first glance.
So the first step is to rewrite it in a more formal and structured way.

Let $P(A)$ denote the probability that event $A$ occurs, and $P(A \mid B)$ denote the probability that $A$ occurs given that $B$ has occurred.

• $S_i$ denotes the $i$-th fault Symptom
• $C_i$ denotes the $i$-th fault Cause

Since both terms come with the prefix “fault” and can be confusing, we will simply use the English words Symptom and Cause in the following discussion.

The problem provides:

• The prior probability of each Cause $i$, namely $P(C_i)$
• The conditional probability $P(S_j \mid C_i)$, meaning that Symptom $j$ occurs given Cause $i$
• A set $S$ of Symptoms that have already been observed

Our task is to compute the probability of each Cause occurring and then sort them accordingly.

Important assumptions:

1. The system can have only one active Cause
2. Given a Cause, all Symptoms occur independently

Based on the conditions above, this is a standard application of Bayes’ theorem.
The probability that Cause $i$ is responsible for the observed symptoms can be written as:

For clarity, we summarize the notation again:

• $C_i$: the $i$-th Cause
• $S_j$: the $j$-th Symptom
• $S$: the set of observed Symptoms

Thus, the problem reduces to efficiently computing $P(S \mid C_i)$ and $P(S)$.
The prior probability $P(C_i)$ is already given in the input.

Since all Symptoms are independent given a Cause, we have:

Note that $S$ represents a specific combination of symptoms.
Therefore, we must consider not only that all symptoms in $S$ have occurred, but also that all symptoms not in $S$ have not occurred.

Once $P(S \mid C_i)$ is known, computing $P(S)$ becomes straightforward.
Since the system can have only one active Cause, we can treat this as a weighted sum:

With these probabilities computed, we can obtain $P(C_i \mid S)$ for each Cause and sort them as required.

D - Luogu P1297 [国家集训队] 单选错位#

Problem Statement

Let’s analyze this case by case.

• Case 1 $a_i = a_{i+1}$: In this case, it’s clear that the answer for question $i+1$ is also random. The expected value is: $\frac{1}{a_i} = \frac{1}{a_{i+1}}$
• Case 2 $a_i > a_{i+1}$: only $\frac{a_{i+1}}{a_i}$ of the possible answers for question $i$ fall within the range $1 \sim a_{i+1}$. Thus, the expected value is: $\frac{a_{i+1}}{a_i} \cdot \frac{1}{a_{i+1}} = \frac{1}{a_i}$
• Case 3 $a_i < a_{i+1}$: the random answer for question $i$ is only within $1 \sim a_i$, and the probability that the correct answer for question $i+1$ falls within this range is $\frac{a_i}{a_{i+1}}$. So the expected value becomes: $\frac{a_i}{a_{i+1}} \cdot \frac{1}{a_i} = \frac{1}{a_{i+1}}$

Combining all cases, the final answer is:

E - Luogu P1850 [NOIP 2016 提高组] 换教室#

DP State: $dp[i][j][k]$ denote for a prefix of classroom $[1, i]$, switch classroom for $j$ times, and we decide (not) to switch classroom on $i$ (record by $k$, 1 for yes and 0 for no).

Transition:

1
int C1 = c[i - 1][0];
2
int C2 = c[i - 1][1];
3
int C3 = c[i][0];
4
int C4 = c[i][1];
5

6
dp[i][j][0] = std::min(
7
    dp[i][j][0],
8
    std::min(
9
        dp[i - 1][j][0] + mp[C1][C3], // not change anymore
10
        dp[i - 1][j][1]               // change on i-1 but i not
11
            + mp[C1][C3] * (1 - k[i - 1])
12
            + mp[C2][C3] * k[i - 1]
13
    )
14
);
15

16
dp[i][j][1] = std::min(
17
    dp[i][j][1],
18
    std::min(
19
        dp[i - 1][j - 1][0]           // change on i but i-1 not
20
            + mp[C1][C3] * (1 - k[i])
21
            + mp[C1][C4] * k[i],
22
        dp[i - 1][j - 1][1]           // change both i-1 and i
23
            + mp[C2][C4] * k[i] * k[i - 1]
24
            + mp[C2][C3] * k[i - 1] * (1 - k[i])
25
            + mp[C1][C4] * (1 - k[i - 1]) * k[i]
26
            + mp[C1][C3] * (1 - k[i - 1]) * (1 - k[i])
27
    )
28
);

Answer is obviously.

F - Luogu P3750 [六省联考 2017] 分手是祝愿#

DP State: $dp[i]$ denote the expect operator number when button quantity we need press decrease from $i$ to $i-1$.

Transition:

This transition means have $\frac i n$ probability press right button, and have $\frac{n-i}{n}$ probability press wrong button. if we press wrong button, we need pay $dp[i+1]$ to make the button quantity we need press decrease to $i$ again, and continue using $dp[i]$ times operation.

then we need simplify the transition equation:

Now answer is obviously.

G - Luogu P2473 [SCOI2008] 奖励关#

DP State: $dp[i][S]$ denote the expected score from round $i$ to round $k$ when, after the first $i−1$ rounds, the selection state of each item is $S$.

Transition:
For all $i\le j\le n$

1. if $S$ satisfy the state requirement of item $j$, we can decide to select it or not;
2. or, just not select it.

Now answer is obiously.

Summarize#

Above is the all problem of this topic.

Most of problem with probability or expectation will not use very further knowledge so just solve these problem like solving basic DP problem.