2019 ECNU Campus Invitational Contest B. Black Peter

题意

一个经典的“抓乌龟”游戏，每次给出两个人手里的牌的情况，求出胜率

解法

其实这是一个数学题，比赛的时候一直没想出来因为没想到递推。
主要还是没有把它当作一个数学的竞赛吧。
$f(n)$,$g(n)$分别表示有n对牌要进行分配，王在或者不在自己手里的胜率。
于是我们可以得到这样一个式子$f(n) = 1 - g(n-1)$
如果王不在自己手里，抽对方一张牌可能抽中王也可能不抽中王，于是有$g(n) = \frac{n}{n+1}\cdot(1-f(n-1))+\frac{1}{n+1}(1-g(n))$
然后迭代一下就可以得到

$$g(n) = \frac{n/2+2}{n+2}$$

得解

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ll long long
#define eps 1e-6
using namespace std;
const int maxn = 1e6 + 10;
int a[maxn];
int n, m;
double put[maxn];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    for(int i = 1; i < maxn; i++)
        put[i] = ((i / 2) + 2.0) / (i + 2.0);
    int cas;
    cin >> cas;
    put[0] = 1;
    while(cas--)
    {
        int n;
        string s1, s2;
        cin >> n >> s1 >> s2;
        int a = 0, b = 0;
        for(int i = 0; i < n; ++i)
        {
            if(s1[i] == '1')
                a++;
            if(s2[i] == '1')
                b++;
        }
        int mmin = min(a, b);
        double ans = 0;
        if(a < b)
            ans = put[mmin];
        else if(mmin == 0)
            ans = 0;
        else
            ans = 1 - put[mmin - 1];
        printf("%.18f\n", ans);

    }
    return 0;
}