### 前言
题目传送门
\(\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; }
首发:2022-05-17 17:37:47