NOIP训练营集训笔记—信息学基础算法（倍增与分治算法
?
本文摘自清北OI學堂內部筆記，作者潘愷璠，來自柳鐵一中曾參加過清北訓練營提高組精英班，主要記錄的是信息學基礎算法。筆記非常詳細，特分享給大家！ NOIP2019年夏令營正在報名中，6大校區10種班型，可前往微信noipnoi報名！
一、倍增算法：
定義：用f[i][j]表示從i位置出發的2j個位置的信息綜合（狀態）
一個小小的問題：為什么是2j而不是3j,5j,…？因為，假設為kj，整個算法的時間復雜度為(k-1)logk，當k=2時，時間復雜度最小。
這個算法的三個應用：
1.倍增ST表：
應用：這個ST表是用來解決RMQ問題（給你n個數，m次詢問，每次詢問[l,r]這個區間的最大值），當然，解決RMQ問題是可以用線段樹來做的，但是比較麻煩，NOIP 80%是不會用線段樹來做，還是用ST表方便。
定義：f[i][j]表示：從i到i+2j-1這2j個位置的元素最大值
初始化：f[i][0]=z[i]（第i個位置到第i+20-1個位置的最大值，對應只有一個元素的區間）
轉移：f[i][j]=max(f[i][j-1],f[i+2(j-1)][j-1]) （把[i,i+2j-1]這個區間分治為兩個區間，這兩個區間拼在一起就成了原來一個大的區間，兩個區間長度都為2j-1）
//建立ST表，引自P2O5 dalao的blog：https://zybuluo.com/P2Oileen/note/816892#應用1-st表
for(int a=1;a<=n;a++) f[a][0]=z[a];//z[]為源數據區間數組?
for(int j=1;j<=logn;j++)
{
? ? for(int i=1;i+z^j-1<=n;i++)
? ? ? ? f[i][j]=max(f[i][j-1],f[i+2^(j-1)][j-1]);
? ? ? ? //乘方是偽代碼！
}
//solve
ans=max(f[l][k],f[r-2^k+1][k]);
所以就有兩種情況：
①假如區間長度(r-l+1)正好是2k，那么就直接訪問f[l][k]；
②假如區間長度(r-l+1)是2k+p(p<2k)，也就說明2k≤(r-l+1)<2k+1，我們可以慢慢地分治下去，利用前綴和，就形成了樹狀數組那樣的東西，一段區間的最大值為 劃分成兩段區間最大值max1,max2相比取較大 ，但是這樣太慢。
有一種更好的方法：其實我們可以用兩個長度為2k的區間就一定能把這段[l,r]區間完美覆蓋起來，會有重復，但是對求最大值這件事情沒有影響，所以?這段區間的最大值=max(f[l][k],f[r-2k+1][k])。
限制：不能用來計算區間和，因為中間有重復部分，還有就是：不支持修改ST表！
2.樹上倍增LCA（最近公共祖先）：
一般是用線性Tarjan算法來求解（這個Tarjan算法和圖論中求有向圖強連通分量的Tarjan不同，都是一個人發明的），但是在ZHX十年的信息學奧賽生涯中沒有用到這個算法，原因有倆：①沒遇到這樣的題目②不會！（笑哭臉），有興趣可以了解一下。
下面介紹倍增的算法：
定義：f[i][j]表示：從樹上編號為i的節點向上走2j步會走到哪個節點。
初始化：從j=0開始考慮，也就是從i號節點向上走1步到達的節點，就是i節點的父親，所以：f[i][0]=father[i]。
轉移：f[i][j]=f[f[i][j-1]][j-1]，表示：從i節點往上走2j-1步后，再往上走2j-1步到達的點，等價于向上走2j步，因為2j-1+2j-1=2j。（j的范圍大概[20,30)≈nlogn，只要保證2j>節點數目n即可）
現在我們構造出來這個f數組，下面介紹如何求兩個點的LCA：
定義數組depth[i]表示i這個節點的深度，有以下兩種情況：
①depth[p1]==depth[p2]，具有一個重要的性質：兩個節點同時向上走同樣地步數，深度仍然相等，也就是說，我們讓p1,p2一步一步地往上走，當走到同一個點時候，這個點一定是LCA！
for(int x=19;x>=0;x--)?
{
? ? if(f[p1][x]!=f[p2][x])//如果沒有走到同一個點，繼續往上走?
? ? {
? ? ? ? p1=f[p1][x];//p1往上跳?
? ? ? ? p2=f[p2][x];//p2往上跳?
? ? }? ? ?
}? ??
if(p1!=p2)//為什么要加這個判斷？有可能p1=p2么？是有可能的！這個判斷是防止一開始跳之前p1=p2這種情況?
{
? ? p1=f[p1][0];//因為上面的循環p1，p2只是走到了LCA的下方，這個判斷只是處理最后一步：把p1或p2往上跳到它的父親，就是LCA，返回即可?
}?
return p1;//p1為LCA，返回
?
②depth[p1]!=depth[p2]，假如p1比較深，就讓p1往上跳到和p2深度一樣的地方。
利用倍增f數組p1往上跳的方法：定義往上走步數step=depth[p1]-depth[p2]，再利用二進制轉換！
舉個栗子：假如step=13，轉為二進制=1101，可以得出13=8+4+1,：先走8步，再走4步，再走1步就好了。
int get_lca(int p1,int p2)
{
? ? if(dpeth[p1]<depth[p2]) swap(p1,p2);
? ? for(int x=19;x>=0;x--)
? ? {
? ? if((2^x)<=depth[p1]-depth[p2]) p1=f[p1][x];
? ? }
}
?
下面是另一種寫法思路就不多講
int x=0;
while (p1!=p2)
{
? ? if(!x||f[p1][x]!=f[p2][x])?
? ? {
? ? ? ? p1=f[p1][x];
? ? ? ? p2=f[p2][x];
? ? ? ? x++;? ? ? ??
? ? }
? ? else x--;
}
?
3.快速冪：
按照一般思路，我們要計算ax的話，要寫一個for循環，計算a×a×a×a…這樣太?麻煩并且浪費時間！
這里運用倍增來實現快速冪，這也是運用到了分治的思想。
我們要求出x(x=2×k)個a的乘積，就可以分解為x/2個a的乘積的平方，這樣就省去一半計算量，如果x是奇數，就在原先的基礎上×a就可以了。
int ksm(int a,int x)//求a^x的快速冪 時間復雜度：O(logx)?
{
? ? int ans=1;
? ? while(x)
? ? {
? ? ? ? if(x&1) ans=(ans*a);//位運算：x&1==1則x為奇數
? ? ? ? a=a*a;
? ? ? ? x=x>>1;//位運算：右移一位，即將X除以2
? ? }
? ? return ans;
}
?
二、分治算法：
定義：將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。
這個算法的三個應用：
1.二分查找：
定義：給定排序數組，查詢某個數是否在數組中
算法描述：在查找所要查找的元素時，首先與序列中間的元素進行比較，如果大于這個元素，就在當前序列的后半部分繼續查找，如果小于這個元素，就在當前序列的前半部分繼續查找，直到找到相同的元素，或者所查找的序列范圍為空為止。
bool find(int x)//二分查找x是否在序列z[]中?
{
? ? left=0,right=n;
? ? while(left+1!=right)
? ? {
? ? ? ? middle=(left+right)>>1;
? ? ? ? if(z[middle]>=x) right=middle;
? ? ? ? else left=middle;
? ? }
}
?
還可以用lower_bound和upper_bound函數進行優化，用法詳見下：
#include <iostream>
#include <algorithm>//必須包含的頭文件，C++特有的庫函數?
using namespace std;
int main()
{
? ? int point[5]={1,3,7,7,9};
? ? int ans;
? ? /*兩個函數傳入的：(數組名，數組名+數組長度，要查找的數字)，返回的是一個地址，減去數組名即可得到數字在數組中的下標*/
? ? ans=upper_bound(point,point+5,7)-point;//按從小到大，7最多能插入數組point的哪個位置
? ? printf("%d ",ans);//輸出數字在數組中的下標?
? ? ans=lower_bound(point,point+5,7)-point;按從小到大，7最少能插入數組point的哪個位置
? ? printf("%d\n",ans);//輸出數字在數組中的下標?
? ? return 0;
}
/*
output：
4 2?
*/
?
2.歸并排序（nlogn）：
是分治法的典型應用。
歸并過程：
比較a[i]和b[j]的大小，若a[i]≤b[j]，則將第一個有序表中的元素a[i]復制到r[k]中，并令i和k分別加上1；
否則，將第二個有序表中的元素b[j]復制到r[k]中，并令j和k分別加上1。
如此循環下去，直到其中一個有序表取完，然后再將另一個有序表中剩余的元素復制到r中從下標k到下標t的單元
歸并排序的算法我們通常用遞歸實現，先把待排序區間[s,t]以中點二分，接著把左邊子區間排序，再把右邊子區間排序，最后把左區間和右區間用一次歸并操作合并成有序的區間[s,t]。
3.快速排序（nlogn）：
一般在使用時候直接調用快排函數。
sort（快速排序，是C#特有的，不會退化為n2，比下面三個都要快，一般使用這個）
qsort（最壞情況下為n2，最好是n，期望為nlogn）
merge_sort（歸并排序，穩定為nlongn）
heap_sort（堆排序，穩定為nlongn）
?
轉載于:https://www.cnblogs.com/qbxt/p/10984714.html
總結
以上是生活随笔為你收集整理的NOIP训练营集训笔记—信息学基础算法（倍增与分治算法的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： android 高德地图放大缩小,手势交
- 下一篇： cmos和ttl_TTL与CMOS详细介