【题解】牛客NOIP暑期七天营-普及组4

A.火龙果树

0分做法

只看样例，不看题目描述，猜想答案符合某个公式，猜错即可得到0分。
如：等

70分做法

发现是斐波那契数列前n项和，对于每组数据计算

100分做法

预处理出[1, 1e7]的斐波那契数列前n项和即可。

误区

• 注意取模的问题（每次加法都要取模）
• 注意计算内存大小（两个long long类型的数组开不下）

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41179250

B.火龙果图

100分做法：

处理三视图即可。
正视图即输入的每列的最大值，左视图即输入的每行的最大值，顶视图直接输出即可。

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41179253

C.火龙果田

24分做法：

直接输出无解。

80分做法：

枚举每个格子和每个已知火龙果，取合法范围内的最大值即可。

100分做法：

堆优化的搜索，每次将当前美味值最小的一个取出，向四联通的格子内扩展D，可以保证如果有解一定是最大的解

误区

• 同一个格子种两种及以上美味度的为非法
• 同一个格子种两个及以上的相同美味度的为合法（但对答案的贡献即该美味度）
• 无解的情况可以直接判出来，不需要搜索

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41179256

D.火龙果画

70分做法：

维护三角形内部的最大值即可。

100分做法1：

维护行、列、左斜、右斜四种前缀和，维护即可。

100分做法2：

只维护行的前缀和，暴力加（时间复杂度为1e8）

代码

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=41179260

博客推荐

偶尔刷刷题

牛客NOIP暑期七天营-普及组4-A火龙果树
牛客NOIP暑期七天营-普及组4-B火龙果图
牛客NOIP暑期七天营-普及组4-C火龙果田
牛客NOIP暑期七天营-普及组4-D火龙果画