平方和
思路与感想
数列求值
思路与感想
用三元素的数组存储数据即可,由于只需要知道最后 4 位数字,当数字大小超过 10000 之后只需要对 10000 取余再存储到数组中加减。
不能用为每一个元素开一个空间,也不能存储一个元素所有的位数。
最大降雨量
思路与感想
贪心。
根据中位数的定义,7 个数中将三个较小的数删去,中位数将变为剩余 4 个数中的最小值。
那么为了保证最后的中位数最大,就需要删去 1∼49 中 (𝑛/2∗𝑛) 个较小值,使剩余的数达到最大。
同理,为了使中位数的中位数最大,则同样需要删去 𝑛/2∗(𝑛−𝑛/2) 个较小值,使该中位数的中位数最大。
最后发现该中位数的中位数就是剩余数中的最小值。
纯数学推理题,随便想想就能填出答案。
也可以按照矩阵来思考。假设是排好序的 7x7 矩阵,那么这个所求值就是最中间的那个格填的值。不过这样算法写出来的程序怎么也不会比上面的推导出来的纯计算快。
迷宫
思路与感想
标记 BFS。
使用同样大小的标记数组标记到达每一格的最少步数,初始化为极大值。
再使用同样大小的前驱数组标记到达每个格的前驱,更新步数时同时更新前驱。
为了使字典序最小,每次询问某格下一次的方向时,按照 DLRU
的顺序询问。
由于 BFS 的性质,一旦到达右下角的格子,说明最少步数的答案已经出现。
暴力解法可以每一个方向开一个协程,维护一个父协程的ID 的上下文也行。但是这样耗费的时间和算力很多。
RSA 解密(15 分)
思路与感想
老师给的链接里面题都是错的,服了。做不出来,看网上说要欧拉函数什么的,有点困难,进行因式分解。
完全二叉树的权值(15 分)
外卖店优先级(20 分)
修改数组(20 分)
思路与感想
并查集。
每输入一个数字,并查集中查找,查找到的结果直接输出,并将结果+1保存回结果的并查集中。
(注意不是保存到输入的数字中,因为有可能下次查询查不到该数字,导致没有更新。)
(对于极端情况不能保证通过。)
并查集+哈希可以解决这些极端情况
糖果(25 分)
思路与感想
DFS。
每个糖果要么拿,要么不拿。
注意每次拿之前保存下当前已经得到的糖果状态。
如果数据很大的话就需要状态压缩 + BFS。
组合数问题(25 分)
思路和感想
按照他说的遍历之后再判断是否质数整除。不过看起来使用这个方法的都没得全分,数据量很大。