每日一题 | 灾后重建问题

每日一题 | 土豪割草问题  

昨天的问题看起来很简单，只是一个寻常的模拟题，只要我们照着题目的要求操作就可以了。但是当你实际这么做你会发现是不行的，原因也很简单，因为数据的范围太大了。草地中草的生长速率以及割草的长时间都是这个量级，在这个量级下线性的复杂度都是不可以接受的。

所以我们被逼无奈必须对算法进行优化，我们想到k的范围是，要小上不少，我们很容易可以想到我们可以用一个二维数组记录每个区域的草上次被割的时间，再对这些割草操作进行排序。这样我们每次割草的时候只需要用相邻两次割草的时间间隔乘上草的生长速度就是我们收割的草的数量。

看起来这个操作要合适不少，但是很遗憾依然会超时。原因也很简单，因为我们每次割草都是割一行或者一列。这一行或者一列当中的草上次被割的时间各不相同，我们必须要一一枚举，这是非常耗时的。我一开始做的时候遇到超时还以为是因为Python太慢了，后来换成了C++一样超时，算了一下复杂度大是。到了8次方的量级，难怪会超时，不得不说这个是出题人的陷阱了，给你一个看起来擦边的复杂度让你去试。如果没有经验的选手可能就耗在上面了。

贴一下超时的代码：

import math
 
weed = [[ for _ in range(505)] for _ in range(505)]
rate = [[ for _ in range(505)] for _ in range(505)]
 
n, m, k = map(int, input().split(' '))
 
for i in range(1, n+1):
    cur = list(map(int, input().split(' ')))
    for j in range(1, m+1):
        rate[i][j] = cur[j-1]
 
 # 记录所有割草的操作
operations = []
for _ in range(k):
    o, x, t = input().split(' ')
    operations.append((o, int(x), int(t)))
 
operations = sorted(operations, key=lambda x: x[2])
 
ret = 
 
for o, x, t in operations:
    # 枚举被割的行或列
    if o == 'r':
        for j in range(1, m+1):
            ret += rate[x][j] * (t - weed[x][j])
            weed[x][j] = t
            ret = ret % 998244353
    else:
        for i in range(1, n+1):
            ret += rate[i][x] * (t - weed[i][x])
            weed[i][x] = t
            ret = ret % 998244353
 
print(ret)

那还有什么办法吗？当然是有的，不过藏得比较深，我们来思考一个问题，每块面积上的草的成长速度但是各不相同，但是都是固定的，不会随着时间变化而变化。其实我们不管这当中收割了多少次，我们只需要知道后一次收割的时间就可以了，因为这当中草都是一直在生长的，收割草并不会影响草的生长。

既然如此，那就很简单了，我们只需要记录下每块草地后一次收割的时间乘上生长速度就可以了。这里还有一个优化，对于的草，我们并不需要用二维数组记录，因为每次收割都是针对一行或者是一列的，我们只需要记录i行与j列后一次收割的时间，其中较大的那个就是收割的时间。如此，又可以节约很多时间。

这道题并没有用到什么特殊的算法，完全是思维题，考验的就是思维的能力以及问题的分析和求解，适合每一个人挑战。

附上AC代码：

import math
 
R = [ for _ in range(505)]
C = [ for _ in range(505)]
rate = [[ for _ in range(505)] for _ in range(505)]
 
n, m, k = map(int, input().split(' '))
 
for i in range(1, n+1):
    cur = list(map(int, input().split(' ')))
    for j in range(1, m+1):
        rate[i][j] = cur[j-1]
 
 
 # 记录每行和每列收割的时间
for _ in range(k):
    o, x, t = input().split(' ')
    x, t = int(x), int(t)
    if o == 'r':
        R[x] = t
    else:
        C[x] = t
 
 
ret = 
 
for i in range(1, n+1):
    for j in range(1, m+1):
        ret = ret + max(R[i], C[j]) * rate[i][j]
        ret = ret % 998244353
 
print(ret)

今日问题

灾后重建问题

说是在虚拟世界当中有一个比特国度遭遇了一场地震，地震将国家内的所有道路都毁坏了。国王准备了m个计划重建这些道路。我们可以把这个国家看成是若干个城市组成的图，这m个计划各自代表了修建两个城市之间的道路。对于城市i和城市j来说，连接两者的道路花费是。这里的代表斐波那契数列，这个数列从第三个数开始，每个数等于前面两个数的和。所以

我们希望在重建花费小的基础上使得重建后的城市当中的大度小，对于图当中的一个点来说，度表示与它有直接边相连的其他点的数量。我们要图当中度大的点的度小。

样例

- END -