【题解】牛客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火龙果画

全部评论
C题的扩展能说的更具体吗
点赞 回复
分享
发布于 2019-08-22 20:42
e......第四题可以给出具体如何维护的方法吗
点赞 回复
分享
发布于 2019-08-22 14:15
饿了么
校招火热招聘中
官网直投
第四题可以给出具体如何维护的方法吗
点赞 回复
分享
发布于 2019-08-22 16:57

相关推荐

头像
03-05 09:50
C++
点赞 评论 收藏
转发
6 1 评论
分享
牛客网
牛客企业服务