提高2二分法與倍增法

1、二分與倍增思想清華大學(xué) 錢橋主要內(nèi)容：二分法倍增法矩陣及其應(yīng)用什么是二分法？讓我們做個(gè)小游戲：請(qǐng)猜出我的生日已知我是1992年出生每次你猜出一個(gè)答案，我都會(huì)告訴你“早了”、“晚了”或“對(duì)了”若不超過10次猜對(duì)，可以得到一份獎(jiǎng)品1月1日12月31日7月2日可能的答案共366天情況1：答案正確人品至上情況2：“早了”可能的答案共182天情況3：“晚了”可能的答案共183天只要我們?cè)儐枀^(qū)間的正中間，無論反饋哪種結(jié)果，都能使區(qū)間長度減半。初始區(qū)間長度為N，LogN次詢問后，一定可以得到正確結(jié)果。如何用程序?qū)崿F(xiàn)二分法？例：集合A中有n個(gè)正整數(shù)。給出Q個(gè)詢問，每次詢問給定一個(gè)x，問集合A中小于x的數(shù)有多少

2、個(gè)。樸素算法：對(duì)于每次詢問給定的x，與A集合中的每個(gè)元素做比較，統(tǒng)計(jì)答案即可。時(shí)間復(fù)雜度O(N*Q)。有沒有更好的解法呢？把A集合中的元素排序！二分！=x我們的任務(wù)是：找到紅色線條在哪L=1; R=n; mid = (L+R+1)/2; if (amid = x) R = mid-1 else L = mid;while (LR) return L;L右側(cè)即為紅色線段例： x6+x5+x4+x3+x2+x=10086在(0,+)的解是多少？答案精確3位小數(shù)。二分法的應(yīng)用提示：f(x)=x6+x5+x4+x3+x2+x在(0,+)區(qū)間是單調(diào)遞增的！實(shí)數(shù)區(qū)間如何二分？二分法的應(yīng)用例：給出n片木板，

3、編號(hào)1n，第i片木板的高度為Hi?，F(xiàn)讓你選取連續(xù)的m片木板圍成一個(gè)木桶，問木桶最多能盛多高的水。最小值最大問題，通?？梢杂枚执鸢附鉀Q！命題P(k)：存在連續(xù)m個(gè)數(shù)的最小值大于等于k對(duì)于0=kans，命題P(k)不成立對(duì)于一個(gè)k，如何驗(yàn)證“是否存在連續(xù)m個(gè)數(shù)的最小值大于等于k”？二分法的應(yīng)用思考題：n個(gè)硬幣，初始均正面朝上。1n時(shí)刻，第i時(shí)刻把編號(hào)是i的倍數(shù)的硬幣翻過來。問最后多少硬幣反面朝上。數(shù)據(jù)規(guī)模：n=10200倍增法例：給出三個(gè)正整數(shù)x、y、p，問xy對(duì)p取模的結(jié)果是多少？數(shù)據(jù)規(guī)模：x、y、p=109。For (i=1; i=y; i+) s=s*x % p;超時(shí)！第一步：求出x1、x

4、2、x4、x8、x16、x32、x64第二部：對(duì)于任意一個(gè)y，xy都可以拆成以上某些結(jié)果的乘積最多30個(gè)！也不超過30個(gè)！最多做60次乘法解法1：麻煩但好理解a1=x; for(i=2; i=30; i+) ai=ai-1*ai-1 % p;b1=1;For(i=2; i=30; i+) bi=bi-1*2;s=1;For(i=1; i0) if (y & 1 = 1) s = s * x % p; x = x * x % p; y = y 1;倍增法例：給出n、x、p三個(gè)正整數(shù)，問(x0+x1+x2+xn) 對(duì)p取模的結(jié)果。數(shù)據(jù)規(guī)模：n、x、p=109。等比數(shù)列求和公式？ x(n+1)-1

5、x-1我們能求出x(n+1)-1 % p的結(jié)果但除以x-1如何解決？有沒有其他做法？介紹兩種“拆”法：x0+x1+x2+x3+x4+x5+x6+x7=(1+x)(1+x2)(1+x4)要求：個(gè)數(shù)恰好為2的整數(shù)次冪x0+x1+x2+x3+x4+x5=(x0+x1)+(x2)(x0+x1+x2+x3)拆成每段長度為2的整數(shù)次冪RMQ問題：給出一個(gè)長度為n的數(shù)列，再給出Q個(gè)詢問，每次詢問給出兩個(gè)位置x、y，問xy之間的最小值。倍增法對(duì)于每次詢問 For (i=x; i=y; i+) 時(shí)間復(fù)雜度O(N*Q)有沒有更好的算法呢？F(i,1)表示第i個(gè)位置開始，往后1個(gè)數(shù)的最小值是多少F(i,2)表示第i

6、個(gè)位置開始，往后2個(gè)數(shù)的最小值是多少F(i,3)表示第i個(gè)位置開始，往后4個(gè)數(shù)的最小值是多少F(i,4)表示第i個(gè)位置開始，往后8個(gè)數(shù)的最小值是多少最多LogN行倍增法xy 16 + 8 + 2+1 對(duì)于任意的xy，一定能拆分成不超過LogN段遞推式F(i,k)=min(F(i, k-1) , F(i+2(k-2), k-1)兩段即可！時(shí)間復(fù)雜度：O(NLogN+Q)倍增法思考題：給出一個(gè)長度為n的數(shù)列A，請(qǐng)對(duì)于每個(gè)數(shù)，輸出他右面第一個(gè)比他大的數(shù)是多少。N=100000。矩陣的基礎(chǔ)知識(shí)一個(gè)n*m的矩陣A：n行，每行m個(gè)數(shù)。第i行第j列用Ai,j表示。矩陣乘法： 一個(gè)n*m的矩陣和一個(gè)p*q的矩

7、陣可以做乘法，當(dāng)且僅當(dāng)m=p。A矩陣的規(guī)模為n*m，B矩陣的規(guī)模為m*pA*B=C，則C矩陣的規(guī)模為n*pABCCi,j=Ai,k*Bk,j 1=k=m矩陣的基礎(chǔ)知識(shí)考慮矩陣乘法是否滿足交換律？考慮矩陣乘法是否滿足結(jié)合律？矩陣的應(yīng)用例：已知F1=1，F(xiàn)2=1，F(xiàn)i=Fi-1+Fi-2。求Fn模65521的結(jié)果。n=109Fi-1 Fi0 11 1Fi Fi+1ABC*=F1 F20 11 1AB*=F2 F3CA * B * B * * B = ANS (Fn-1 Fn) n-2個(gè)BA * B(n-2) = ANS快速冪！矩陣的應(yīng)用例：已知F1=1，F(xiàn)2=1，F(xiàn)i=Fi-1+Fi-2。求(F1+F2+F3+Fn)模65521的結(jié)果。數(shù)據(jù)范圍：n=109。Fi-1 F