# [题解] 2023 杭电多校 Do You Like Interactive Problems? [期望][分类讨论]

# 题目大意$\footnotesize^{传送门}$

你需要猜一个在$[1,n]$ 范围内的整数$x$，每次你随机选择一个$y \in [1,n]$ 进行询问，并得到答案 $y>x,y<x,y=x$ 其中之一，直到能确定$x$ 的值停止询问。
问期望询问次数。

# 题解

题解说暴力打表推式子
对$[1,n]$ 的每个$x$ 求期望，再加权平均即为总期望。

$$Ans=\frac{1}{n}\sum\limits_{x=1}^{n}E_x$$

只需要考虑最终一刻，什么情况下才可以确定$x$ 的值。
分为两种情况：

• 左右端点$l,r$ 已经满足$r-l=2$，这时即可确定$x=l+1=r-1$。
• 某一次询问直接问出$y=x$

所以我们只关注三种状态：

1. 当前已经确定$x$，即 y=x 或者$r-l=2$
2. 当前未确定$x$，但$l=x-1$ 或者$r=x+1$ 满足其一
3. 当前未确定$x$，且有$r-l>2$

考虑从这三种状态出发，期望询问次数。
易得状态$1$ 到达结果的期望

$$E_1=0$$

在状态$2$，若下次询问有$y=x+1$ (或$y=x-1$) 或$y=x$，使得$x$ 被两端点夹住，则转为状态$1$、确定$x$。这一步发生的概率为$P_2=\frac{2}{n}$。实际上这就是几何分布的模型，那么由状态 2 到达结果的期望便是

$$E_2=\frac{1}{P_2}=\frac{n}{2}$$

状态$3$ 的下次询问有$\frac{1}{n}$ 概率直接转为状态$1$，有$\frac{2}{n}$ 的概率确定端点之一，转为状态$2$，那么有方程

$$E_3=\frac{1}{n}E_1+\frac{2}{n}E_2+\frac{n-3}{n}E_3+1$$

解得$E_3=\frac{2n}{3}$
当$x\in\{1,n\}$ 时，不存在状态$3$，从初态到结束的期望为 E_2；当$x\notin\{1,n\}$ 时，从初态到结束的期望为$E_3$
那么 $$Ans=\frac {1}{n}\left (2\cdot\frac {n}{2}+(n-2)\cdot\frac {2n}{3}\right)=\frac {2n-1}{3}$$