ICPC 2022 KunMing K

题目大意

G准备玩\(n\)场游戏，它心中有个胜率\(x = \frac{a}{b}\),如果当前赢的局数 / 总局书 小于等于\(x\),那么他就会赢，否则它就会输。 给定\(a,b,n\)，求他能赢多少局。 题目链接

思路

图中画出了胜场比变化图(图挂了，来博客)。 如果当前胜场比\(s > x\),那么我们就会输，反之我们就会赢！ 进行第\(n\)局时，假如我们知道了此时的\(s\),那么我们就能得本局是否会赢。

那么如何寻找\(s_{n-1}\)呢?我们可以发现，它一定在\(x\)的两侧。比如\(x = \frac{2.7}{4}\),那么\(s_{n-1}\)要么是\(\frac{2}{4}\),要么是\(\frac{3}{4}\) * 假如\(s_{n-1} = \frac{2}{4}\),那么\(s \le x\),那么第\(n\)局就会赢，\(ans = \frac{3}{5}\) * 假如\(s_{n-1} = \frac{3}{4}\),那么\(s > x\),那么第\(n\)局就会输，\(ans = \frac{3}{5}\)

可以发现，第\(n\)局的答案和\(s_{n-1}\)无关，它是个"定值"，准确的来说:\(ans = \lfloor(n-1) * x \rfloor + 1\),这个式子表示我们假设第\(n-1\)局输掉了比赛,那么我们第\(n\)局就会赢回来一局。

#include <cstdio>
#include <iostream>
using namespace std;

int main()
{
    int T;
    long long a, b, n;
    scanf("%d", &T);
    while(T--) {
        scanf("%lld%lld%lld", &n, &a, &b);
        printf("%lld\n",(n - 1) * a / b + 1);
    }
    return 0;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2022/04/23/ICPC2022KunMingK/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！