P8344 题解

前言

题目传送门

\color{red}{see}\space \color{green}{in}\space \color{blue}{my}\space \color{purple}{blog}

这题作为本次比赛的 T1，难度感觉还行，算是一道结论题。

已经尽量讲得简单一些，没有用复杂的求和符号。

思路

很容易想到贪心策略，如下。

第 1 次放 (z-1) 块银色木板，再放一块金色木板。

第 2 次放 (z-2) 块银色木板，再放一块金色木板。

一直按照这个规律下去放木板，直到放完第 x 次。

注意，还有第 (x+1) 次，这一步执行时已经没有金色木板了，但可以将剩下的空位都塞满银色木板，可以塞 (z-x) 块。

因此，我们最终需要判断：(z-1) + (z-2) + \cdots + (z-x) + (z-x) 是否大于等于 y。

循环暴力累加，时间复杂度是线性的，但我们需要让时间达到 O(1)。

化简这个算式即可： (z-1) + (z-2) + \cdots + (z-x) + (z-x)。

\begin{aligned}\text{原式} &= (x+1) \cdot z - (1 + 2 + \cdots + x + x)\\&= (x+1)\cdot z - \left[ \dfrac{(x+1)\cdot x}{2} + x \right]\end{aligned}

这就是本题结论了。

坑点

切记开 long long。

开始时还需要判断一下，如果 x > z 就必定无解。

完整代码

#include <iostream>
#include <cstdio>
using namespace std;
bool solve()
{
    long long x, y, z;
    scanf("%lld%lld%lld", &x, &y, &z);
    if (x > z) return false;
    return ((x+1) * z - (x * (x+1) / 2 + x) >= y);
}
int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        bool t = solve();
        if (t) puts("Renko");
        else puts("Merry");
    }
    return 0;
}