题解：P11868 抽卡

cff_0102 · 2025-03-13 10:20:21 · 题解

这题交了 30 篇题解，我打回了 28 篇。剩下两篇的证明看起来也都不是很清晰，所以我就自己写了一篇新的。

抛开期望不谈，可以证明无论如何取卡最终正确猜测的次数一定是 \max(a,b)。

假设现在 a>b，那么小海会一直选择猜 A，直到抽完后两种卡数量相等。假设这个数是 x_1，因为在这期间小海一直猜 A，而 A 卡被抽走了 a-x_1 张，所以小海一定会猜中 a-x_1 次。

现在两种卡数量相等，小海不会进行猜测。小威抽走一张后，又会回到一种卡多一种卡少的情况，也就转化为上面的情况。假设下一次两种卡数量相等时数量为 x_2，那么在这期间小海一定会猜对 x_1-x_2 次。

一直重复，直到最后剩下 0 张卡片。那么小海一共会猜中 a-x_1+x_1-x_2+\dots-x_k+0=a 次。刚开始 a<b 或 a=b 时也同理可得，答案为 \max(a,b)。

因此这个求期望没用，最终猜中的次数是确定的，直接输出 \max(a,b) 即可。

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int a,b;cin>>a>>b;cout<<max(a,b); 
    return 0;
}