• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

2021.09.13am

开发技术 开发技术 6小时前 2次浏览
预期 实际
A 100 100
B 100 100
C 100 100
D 100 100
E 100 100
F 30 45
G 40 10
H 100 100
I 60 60
S 730 715

可能水,一定菜

A 营救 (blacktriangle)

典型 (BFS)

B 细胞 (blacktriangle)

典型 (DFS) ( (BFS) 也行)

C 体积 (blacktriangle)

这道题考三次了吧?????

D 数的拆分 (blacktriangle)

  1. 提示写的是递归拆(n,n-1,n-2····)
  2. 但是咱写不来,就写了个 简单 (DFS) 满足序列不下降。

E 全排列问题 (blacktriangle)

经典 (DFS)

F 最优调度问题 (blacktriangle)

  1. 这道题告诉我一个道理:状态要设计得清晰易懂。这样才能更好进行剪枝。
  2. 我设计的状态:对于每一个位置(不是每一个数),选择一个未使用的数,再选择是重开一个机器,还是放在之前的机器。(dfs) 内有四个参数
  3. 标答的状态:先降序排列,对于每个数选择一个机器放进去,(dfs) 内有两个参数
  4. 这就是世界的参差

G 埃及分数 (blacktriangle!blacktriangledown)

  1. 作为一道优秀的搜索,它成功恶心到了我
  2. 这道题告诉我另一个道理:时间复杂度对了也不一定能过,选择 (for) 的排列顺序(从小到大,从大到小)也能对算法时间产生巨大的影响
  3. 对于这种题,明显只能暴力。
  4. 我的状态选择是先枚举选几个数,再从小到大枚举每个位置的数。
  5. 优化
    • 每次选的数大于上一次选的数
    • 若按现在这个数的大小往后拼满都达不到答案就退出
    • 现在枚的数大于答案中最大的数就退出
  6. 对于分数的模拟:
    • 不建议用 (double) 精度又拉,速度也慢
    • 直接相乘小范围可以,但一直乘很容易爆掉,所以要恰当地使用 (gcd)

H 金币问题II (blacktriangle)

模拟即可。时间复杂度有点难分析啊。大概是(O(sqrt n))

I 生日蛋糕 (blacktriangle!blacktriangledown)

  1. 也是一道有点恶心的搜索题。
  2. 恶心在那一mol多的剪枝
  3. 下限:
    • 高度和半径都至少为层数
    • 剩余的体积小于按本层体积往上拼满的大小
  4. 上限:
    • 小于上一层的高度和半径
    • 剩余的体积大于等于拼蛋糕所需最小体积(和层数相关的体积)(建议写在每一次(DFS) 开始时)
  5. (return):
    • 现在的表面积已经大于答案的表面积
    • 体积小于0
  6. 奇怪的优化
    • 高度半径从小到大枚
    • 每一层高度与半径放在函数外面赋值

2021.09.13am
(cal {Made} {by} {YuGe})


程序员灯塔
转载请注明原文链接:2021.09.13am
喜欢 (0)