23.8.17 杭电暑期多校10部分题解

1004 - Do You Like Interactive Problems?

题目大意

给定一个 $n$，存在一个 $x\in [1,n]$，每次猜测你将进行随机一个 $y\in [1,n]$，每次猜测会告诉你 $x<y$， $x>y$ 或 $x=y$，当你猜到 $x$ 或者只剩下一个数符合条件时停止猜测，问在 $x$ 随机的情况下，你的期望猜测步数

解题思路

可以通过打表找规律来得出正解

不难发现答案就是 $\frac{2\ast n-1}{3}$，$n=1$ 时需要特判

接下来进行验证

当 $1<x<n$时

其实只有猜测到两个相邻点 $x-1$ 和 $x+1$ 或者猜测到 $x$ 时才能结束

假定以下几种状态

第一种状态：已经猜测到过两个相邻点或者猜测过 $x$，期望步数为 $0$

第二种状态：已经猜测到其中一个相邻点，再猜测到另一个或者 $x$ 会转移到第一种状态，期望步数为 $1/(2/n)=n/2$

第三种状态：两个相邻点和 $x$ 都没猜测到过，等价于初始状态

在第三种状态下，如果猜测到 $x$ 会转移到第一种状态，概率为 $1/n$

如果猜测到两个相邻点的其中一个则会转移到第二种状态，概率为 $2/n$

因此我们所求的答案 $E=1/n\ast 0+2/n\ast n/2+(n-3)/n\ast E+1$

解得 $E=2n/3$

当 $x=1$ 或 $x=n$ 时

与上面所说的第二种状态类似，因此期望步数为 $n/2$

综上，最后答案为 $(n-2)/n\ast 2n/3+2/n\ast n/2=(2\ast n-1)/3$

code

#include 
#define int long long
using namespace std;
const int MOD = 998244353;
int t, n;
int pw(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t --) {
        cin >> n;
        if (n == 1) {cout << 0 << '\n'; continue;}
        cout << (2 * n - 1) % MOD * pw(3ll, MOD - 2) % MOD << '\n';
    }
    return 0;
}
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