每日一题 | 土豪割草问题

每日一题 | 召唤兽问题  

这道题的思路很简单，我们完全可以模拟一下这个英雄的魔法值的变化过程。在游戏开始的时候是n，然后每秒钟如果魔法值超过x则召唤一个召唤兽，否则什么也不做等待魔法恢复。那么我们只需要重复m次这个过程就可以统计出一共召唤出了多少个召唤兽。

这的确非常简单，但有一个很大的问题就是m的范围是10的九次方这个量级，显然我们用循环的方法是不行的，一定会超时。既然循环不行，那么就只能通过数学方法来计算了。

我们可以分成两种情况，种情况是每秒钟的恢复速度大于等于消耗速度，由于题目中给定了这个条件。所以只要魔法值的补充速度大于消耗速度，那么一定每秒钟都可以召唤召唤兽，所以答案就是m。

第二种情况是魔法的恢复速度不如消耗速度，这种情况就会棘手一些。但有一点可以肯定，就是在游戏的过程当中一定不会出现魔法值超过上限的情况。既然这样就好办了，我们可以写出一个方程，我们假设后召唤出来的数量是h，可以得到：

n是游戏开始时的魔法量，(m-1)* y是游戏过程中总共能够恢复的魔法量，hx是消耗的魔法量。由于题目限定，后剩余的魔法量一定要大于等于0，那剩下的就很简单了，我们把这几个值带进去算一下就得到结果了。但是这里有一个trick，有可能m很小，n很大，导致后算出来的结果大于m，这也是不对的，因为m秒多只能召唤出m个召唤兽，所以我们还需要和m取个小值。

t = int(input())

for _ in range(t):
    line = input()
    n, m, x, y = int(line.split()[]), int(line.split()[1]), int(line.split()[2]), int(line.split()[3])
    if y >= x:
        print(m)
    else:
        print(min((n + y * (m-1)) // x, m))

今日问题

割草问题

从前有一个土豪有一片自己的草地，我们可以把这片草地近似看成是矩形。长度为n，宽度为m。已知这片草地当中不同区域草生长的速度不同，记为。假设土豪闲着没事要来割一割地里的草，土豪每次割一行或者一列，现在我们已经得知了土豪的割草计划，请问土豪一共能够收获多少草？

行输入三个值n，m和k，分别表示草地的行数、列数以及土豪的割草次数。

接着是一个n * m的矩阵，表示草地各个区域草的成长速度。之后是k行数据，每一行有3个值，c, x, t。c是一个字母，'r'表示割一行，'c'表示割一列。x表示割的行号或者是列号，t表示割草的时间。

其中n和m的范围是1到500，k的范围是，，每次割草的时间。

样例

- END -