第一题：最后的投掷

题目简述

现在3个人玩筛子，前两个人分别筛了 $Y$ 点和 $W$ 点，问第三个人有多大的概率赢，要求返回最简分数，但是赢的前提只需要大于等于最大的人。

题目分析

最容易想到分母在化解为最简分数前，一定是 $6$，而分子一定是：

$$ 6 - \max(前两人点数) + 1 $$

$+1$ 的原因是因为是大于等于，所以就需要 $+1$。

最先可以想到 if 分支的方法：

int 分子 = 6 - max(y, w) + 1;
if(分子 == 1) cout << "1/6";
if(分子 == 2) cout << "2/3";
...
if(分子 == 6) cout << "1/1";

接下来往深处想，我们既然已经知道了分母和分子，那么不就可以直接求最简分数然后输出了吗？

求最简分数也只需要求最大公约数，然后求出：

$$ \frac{分子 \div \gcd(分子，分母)}{分母 \div \gcd(分子，分母)} $$

这里使用的是“更相减损术”：

int gcd(int a, int b)
{
    return (b == a - b ? b : gcd(max(b, a - b), min(b, a - b)));
}
int 分子 = 6 - 最大点数的人 + 1;
int G = gcd(分子, 6);
cout << 分子 / G << "/" << 6 / G;

::::success[正确代码]

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b)
{
    return (b == a - b ? b : gcd(max(a - b, b), min(a - b, b)));
}

int main()
{
    int a, b;
    cin >> a >> b;
    if(a == 1 and b == 1)
    {
        cout << "1/1";
        return 0;
    }
    if(a > b) swap(a, b);
    int c = 6 - b + 1;
    int fz = c, fm = 6;
    int G = gcd(fm, fz);
    cout << fz / G << "/" << fm / G;
}

::::

第二题：打击怪物

题目简述

现在有 $3$ 个数，将 $1 \sim 7$ 的炮弹看为一组，前 $6$ 个炮弹需要选中一个目标 $(a,b,c$ 中$)$ 并打击，会使任意一目标的值 $-1$。第 $7$ 次会强化光线，而强化后的打击会直接将所有值 $-1$。问：是否能在逢 $7$ 次强化光线的时候将所有值变为 $0$？

题目思路

我们可能会在第一下灵光一闪想到一个 $9$，因为一组将会打击 $9$ 次怪物。

但是套入样例：

10 1 7

会发现虽然值总和是 $18$，也是 $9$ 的倍数，但是无论怎么打击，都不会成功，同时，样例也输出了 NO。

我们往深处想，会发现，如果他要打击 $2$ 组，但是有一个数是小于 $2$（例如样例的 $b$ 是 $1$）也会判定为不行，所以可以写出正确代码。

::::success[正确代码]

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int a, b, c;
        cin >> a >> b >> c;
        int x = a + b + c;
        if(x % 9 == 0)
            if(a < (x / 9) or b < (x / 9) or c < (x / 9)) cout << "NO" << endl;
            else cout << "YES" << endl;
        else cout << "NO" << endl;
    }
}

::::

第三题：加和除

题目简述

有两个数 $a, b$，问只使用下面两种操作的情况下，让 $a = 0$ 最少要几次操作？

  1. $a = \lfloor \frac{a}{b} \rfloor$
  2. $b = b + 1$

题目思路

本题只需要一直循环，直到找到最小的 cnt 即可。循环多少次呢？理论上只要循环 $30$ 次就可以了。

因为 $2^{30}$ 已经超过了题目给定的 $a, b$ 最大范围 $(10^9)$，因此枚举 $30$ 次足够覆盖所有最优解的可能情况，不会遗漏最优解。

每次循环我们都让先求出 $b + i$，然后内部嵌套一个循环，求 $a$ 一直除以 $b + i$ 需要多少次除完，再取最小值。还要特殊处理 $b + i == 1$ 的情况，否则有可能死循环。

::::success[正确代码]

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int a, b, minn = INT_MAX;
        cin >> a >> b;
        for(int i = 0; i <= 30; i ++)
        {
            int cnt = 0, na = a;
            if(b + i == 1)
            {
                continue;
            }
            while(na)
            {
                na /= b + i;
                cnt ++;
            }
            minn = min(cnt + i, minn);
        }
        cout << minn << endl;
    }
    return 0;
}

::::

总结

本次的题目都是思维题，需要一定的思维能力来理解，做题不要想着暴力/其他算法，有时候数学也能做出来。