2021.10.07pm

2021.10.07PM

预期 实际
A 100 100
B 0 0
C 100 100
S 200 200

B是最简单的,反而没做(wu)

可能水,一定菜

A [TJOI2013]松鼠的聚会 \(\blacktriangle\!\blacktriangledown\!\blacktriangle\)

  1. 据说是啥切比雪夫距离,但考试的时候咱也不会啊,就只能乱搞了。
  2. 首先,可以发现两点之间距离定义为 \(max(\left| x_i-x_j \right|,\left| y_i-y_j \right|)\)
  3. 由于这个地方有个 \(max\) 非常难搞,而且里面又是一个绝对值。
  4. 首先考虑把 \(max\) 拆开
    2021.10.07pm
  5. 通过对类棋盘的题的联系,我抓住了这两条直线,而这也是至关重要的地方。
  6. 这两条直线把它分成了四个象限,而每个象限由于斜率影响,能直接比较出 \(\Delta y\) 和 \(\Delta x\) 。
    2021.10.07pm
  7. 我们进行按照常规坐标系命名象限。
    2021.10.07pm
  8. 对于第一象限有 \(x+y>N,x-y>M\) ,第二象限有 \(x+y>N,x-y<M\),三四象限类似。
  9. 而第一三象限,显然有 \(\Delta y < \Delta x\) ,而二四象限有 \(\Delta x < \Delta y\)。
  10. 同时,第一象限中 \((x+y+x-y)>M+N=2*x\) ,第三象限 \((x+y+x-y)<M+N=2*x\),第二象限中 \((x+y-(x-y))>M+N=2*y\),第四象限中 \((x+y-(x-y))<M+N=2*y\)。(其实看图很容易得出来)
  11. 那么对于每个点分别计算每一块的大小就行,为了更快计算,显然排序+前缀和乱搞就行。由于我考试的时候因为树状数组学魔障了套了个树状数组扫描线,其实没有必要,直接离线二分查找就行·····
  12. 由于写得实在是太丑而且三颗树状数组调了半小时改了计算方式,所以就不贴具体实现了······
  13. 有搞随机数整过去的

B [TJOI2013]拯救小矮人 \(\blacktriangle\!\blacktriangledown\)

  1. 这道题做法花样多得很,这里讲一个\(O(n\log n)\) 的算法。
  2. 首先,我们预处理处每个人要上天堂需要的高度。(脚底下要踩多高。人上人),并进行升序排列。(显然需要帮助最多的只能先离开)
  3. 然后处理出后缀和,以判断每个人是否能上天堂。
  4. 从 \(1\) 到 \(n\) 依次判断能不能上天堂,能上就先塞进去。而对于目前上不了天堂的,由于我们只关心上天堂人数,而不关心谁上去,所以如果拉一个人下来这个人可以上天堂就把这个人送进天堂,而出于贪心,我们会把最高的人拉下来(维护一个堆),垫在最底下;同时最高的人都不能推该人上天堂,那只能把该人垫在最底下。

C [TJOI2013]最长上升子序列 \(\blacktriangle\!\blacktriangledown\!\blacktriangle\)

  1. 这道题属于是把两道题混一起了。前半部分是Buy Tickets(POJ),后半部分是最长上升子序列优化。

  2. 前半部分由于最后一个的位置是确定的,而倒数第二个位子也是要求满足前面有a[i]个空位,从后往前状态是明确的,所以从n到1依次加人,维护空位用树状数组+二分(非常可恶的是 \(vector\) 也能过)。这里放一道板题。[SHOI2013]发牌

  3. 后半部分我记得有一些高级的优化,但是咱不会,现想只会用线段树维护区间最大值。但是!!!!这里找的前缀区间最大值。所以,可以用树状数组 。\(树状数组是前缀的KING\) 。我们只需要把维护前缀和改成维护前缀最大值,还是用\(lowbit\) 实现。

  4. 给大家看下效率对比:

    2021.10.07pm

  5. 第一名是某不知名巨佬,第二名是两个树状数组,第三名是树状数组+线段树。从时间和空间和码量来说,\(树状数组YYDS\)

2021.10.07pm

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

上一篇:Nuget-Doc:NuGet 介绍


下一篇:多元函数中连续,可导,可微,偏导数连续的关系及意义