Java教程

2020.09.30am

本文主要是介绍2020.09.30am,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

2020.09.30AM

预期 实际
A 100 100
B 50 63
C 100 100
D 100 100
E 100 100
F 100 100
G 100 100
H 0 47
S 650 710

A 聪明的质检员 \(\blacktriangle\!\blacktriangledown\)

  1. 这道题打破了我对二分的固有印象。一般来说都是二分答案,而这道题是在二分的过程中找答案。
  2. 首先,Y随W的增大而减小,具有单调性,显然可以二分。
  3. 而这道题奇妙的地方就在于,我们要二分W使得Y等于S(不一定真的有等于S的时候),同时不断地更新答案。由于mid指针会不断地在Y等于S两端反复横跳,直至逼近,显然一定有位置就是答案。
  4. 只剩下一个问题:如何计算Y?显然要求离线。我们对与大于W的矿石记录两个前缀和,分别记录大于W的个数与质量总和,再对于每个区间进行区间查询。(由于前段时间练习树状数组有些魔障,这里成功把check时间复杂度从 \(O(n)\) 优化到 \(O(n\log n)\) )
  5. 其实还有一种算法,产生原因是我想起了最小生成树(贪心)的题可以用二分解。可惜需要内存太大,我没想到怎么优化。
  6. 我们先进行排序,从质量最大的开始建起,直到Y>S。则要么这一次,要么上一次是最佳答案。正确性显然。问题就在于怎么快速从点到各个区间更新,这只能时间空间二选一,确实是没有办法。

B 道路与航线 \(\blacktriangle\!\blacktriangledown\)

  1. 这道题卡Dijkstra和SPFA。
  2. 由于有负边权,Dijkstra贪心的策略会出问题(两条路合并反而可能更短),这不会导致正确性挂掉,但会T掉···(\(P.S.\) 即使在开了 \(O_2\) ,快读之后,仍然会T一个点)同时,SPFA日常被卡。(但是优化后的没有被卡)
  3. 而这道题有意思在没有负环,则双向边不能为负,那么除去单向边的部分便是几个连通块,我们按照出度进行拓扑排序,对每个团内的点跑Dijkstra。

C 城市交通路网 \(\blacktriangle\)

  1. 虽说是DP,但其实就是个Dijkstra,顶多再记住从哪来的···

D 猪猪储蓄罐 \(\blacktriangle\)

  1. 显然的完全背包。

E 金明的预算方案 \(\blacktriangle\)

  1. 写的多么高级,其实就是一个分组背包,对于主,主+附1,主+附2,主+附1+附2为一组,只能选其中之一。

F 热浪 \(\blacktriangle\)

  1. 显然单源最短路。

E 贿赂FIPA \(\blacktriangle\!\blacktriangledown\)

  1. 树形DP,可惜输入毒瘤。
  2. 比较板,没啥好说的。

F Balloons \(\blacktriangle\!\blacktriangledown\)

  1. 其实蛮水的
  2. S首先根据圆的方程能推出每个气球限制的这个气球的最大半径。(\((r_i+r_j)^2-(r_i-r_j)^2=(x_i-x_j)^2 \to r_i=(x_i-x_j)^2/r_j/2\)
  3. 其次,如果有气球半径大于等于右边的气球,该气球左侧的气球一定碰不到右侧的气球,那么显然单调栈。
  4. 最后复杂度不严格\(O(n)\)。
    image

\(\cal {Made} \ {by} \ {YuGe}\)

这篇关于2020.09.30am的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!