警告

本 Blog 仅供蒟蒻 tiger0132 复习用。本蒟蒻

不对其内容正确性做任何保证。

若发现 Bug 请在评论区反馈。本蒟蒻欢迎一切形式的贡献。

点击屏幕以关闭。

「笔记」day6上午 - 分治

:warning:注意:这是ZROI集训的源笔记,其中有很多缺失和遗漏以及无法看懂的部分,大家就不要看了吧。

以下是原笔记:


分治

归并排序

将两个已经有序的数组用\(O(n)\)合并成一个有序的数组。

时间复杂度\(O(n\log n)\)

树的深度\(O(\log n)\)层,归并整个一层\(O(n)\),共\(O(n\log n)\)

使用范围

  • 规模小可以方便计算
  • 可以划分成较小子问题
  • 子问题全部解出后可以解决原问题
  • 子问题独立

Master Theorem

\(a\ge 1,b\ge 1\),设 \(f(n)\) 为一函数,\(T(n)\) 由递归式$ T(n)=aT(nb)+f(n)$ 定义。

  • \(f(n)<n^{\log_ba}\),则 \(T(n)=O(n^{\log_ba})\)
  • \(f(n)=n^{log_ba}\),则 \(T(n)=O(n^{log_ba}log_2n)\)
  • \(f(n)>n^{log_ba}\),且对于任意 \(c<1\) 与所有足够大的 \(n\),都有 \(af(\frac nb)\le cf(n)\),则 \(T(n)=O(f(n))\)

逆序对

\(n\le10^5\)

一分为二。考虑左边自身、右边自身、跨两边。跨两边就two-pointers解决。

快速幂

分治大法好==位运算大法好==

即时战略(WC2018T2)

35pts

从一个点开始,枚举所有其它点,然后把它周围所有点探索出来,类似于bfs\(O(n^2)\)

完全二叉树

Solution 1

\(O(\frac n2)\)查出一个点在哪个子树。

然后查下面的\(O(n)\)个点,在标记中使用堆式编号。

然后就用主定理证出\(O(n\log n)\)了。

Solution 2

因为完全二叉树的深度是\(O(\log n)\)的,所以可以用\(O(n\log n)\)过掉。

Solution 3

在完全二叉树上BFS!

百度地图的实时路况

分治严格不经过的点\(solve(l,r)\)代表\([l,r]\)都没有被考虑。

= =

区间的价值

枚举最小值。然后从左右两端找最大值。

BD String

超淼题

可以证明,\(S(n)\)B的数量是\(2^{n-1}\)

然后计算\(solve(n)\)

  • \(n=0\)返回\(0\)

  • \(n=1\)返回\(1\)
  • \(mid=2^{\lfloor\log_2n\rfloor}\)。如果\(2mid-1=n\),返回\(mid\)
  • 否则返回\(f(2mid-1-n)+n+1-mid\)

My solution

\(f(x)\)\(S(n)\)\([0,x)\)B的数量。

那么答案就等于\(f(l)-f(r-1)\)

然后考虑\(x\)的位置。如果在后半段就将\(2^{n-1}+1\)加上后半段。

前半段就直接从\(n-1\)算。

欧几里得最近点对

先按\(x\)排序,然后把点分成两半。

然后初始化答案\(d=+\infty\)

然后在左右两边枚举点,对答案更新有用的点一定是在该点为圆心半径为\(d\)的点。这样的点最多只有不到\(6\)个。

Tricky Function

\(g(i,j)\)就是算\((i,j]\)的区间和。

\(b\)\(a\)的前缀和,那么\(g(i,j)=b[i]-b[j]\)

\(x\)坐标为编号,\(y\)坐标为前缀和。

然后就差一个根号!

然后交个板子就AC了。