《淺談信息學(xué)競(jìng)賽中的“0”和“1”》ppt課件

1、“1與0，一切數(shù)字的神奇淵源。這是造物的愉快的典范，由于，一切無(wú)非都來(lái)自上帝。 淺談信息學(xué)競(jìng)賽中的“0和“1 二進(jìn)制思想在信息學(xué)競(jìng)賽中的運(yùn)用河北省石家莊二中 武森content二進(jìn)制思想在數(shù)據(jù)構(gòu)造中的運(yùn)用二進(jìn)制思想在數(shù)據(jù)構(gòu)造中的運(yùn)用樹(shù)狀數(shù)組樹(shù)狀數(shù)組二進(jìn)制思想在解題思想中的運(yùn)用二進(jìn)制思想在解題思想中的運(yùn)用形狀緊縮形狀緊縮模型轉(zhuǎn)化模型轉(zhuǎn)化01二叉樹(shù)二叉樹(shù)例題一：例題一：Matrix Matrix 有一個(gè)有一個(gè)M M* *N N的矩陣，每一個(gè)格子中的數(shù)是的矩陣，每一個(gè)格子中的數(shù)是1 1或或0 0，初始時(shí)為，初始時(shí)為0 0。有兩種操作：。有兩種操作：修正一個(gè)子矩陣，將子矩陣中的數(shù)字全修正一個(gè)子矩陣，將

2、子矩陣中的數(shù)字全部部0101取反。取反。查詢(xún)第查詢(xún)第x x行第行第y y列的格子中的數(shù)字。列的格子中的數(shù)字。 假設(shè)給定的是一個(gè)長(zhǎng)度為N的一排格子。退而求其次 每次可以修正一個(gè)子列中的數(shù)字。 這樣，這道標(biāo)題就變得簡(jiǎn)單了！ 根據(jù)這個(gè)標(biāo)題中引見(jiàn)的這個(gè)矩陣中的數(shù)的特點(diǎn)不是1就是0，這樣我們只需記錄每個(gè)格子改動(dòng)過(guò)幾次，即可判別這個(gè)格子的數(shù)字。 每次修正的時(shí)候，無(wú)妨把格子修正的范圍(x,y)變成兩個(gè)點(diǎn),一個(gè)為更改的初始節(jié)點(diǎn)x，另一個(gè)為更改的終止節(jié)點(diǎn)y+1，然后往這列格子中的這兩個(gè)節(jié)點(diǎn)中加 1。修正：修正： 每次修正的時(shí)候，無(wú)妨把格子修正的范圍(x,y)變成兩個(gè)點(diǎn),一個(gè)為更改的初始節(jié)點(diǎn)x，另一個(gè)為更改的終止

3、節(jié)點(diǎn)y+1，然后往這列格子中的這兩個(gè)節(jié)點(diǎn)中加 1。修正：修正： 每次訊問(wèn)的時(shí)候只需計(jì)算出Sumx就可以求出第x個(gè)格子被修正正幾次。查詢(xún)查詢(xún) 每次訊問(wèn)的時(shí)候只需計(jì)算出Sumx就可以求出第x個(gè)格子被修正正幾次。查詢(xún)查詢(xún)尋根溯源尋根溯源用上面的方法看看能否處理原來(lái)的問(wèn)題。用上面的方法看看能否處理原來(lái)的問(wèn)題。推而廣之推而廣之 假設(shè)是要處置三維的情況，甚至N維的情況呢？ 普通的數(shù)據(jù)構(gòu)造能處理嗎？普通的數(shù)據(jù)構(gòu)造能處理嗎？不能！不能！怎樣辦呢？怎樣辦呢？二進(jìn)制思想二進(jìn)制思想 二進(jìn)制思想在數(shù)據(jù)構(gòu)造中的運(yùn)用： 樹(shù)狀數(shù)組中的每一個(gè)元素的編號(hào)變成了二制編碼，再經(jīng)過(guò)這些二進(jìn)制編碼末尾的0的個(gè)數(shù)來(lái)決議存儲(chǔ)什么信息，假設(shè)

4、節(jié)點(diǎn)編號(hào)為x，那么這個(gè)節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)的區(qū)間為2k其中k為x二進(jìn)制末尾0 的個(gè)數(shù)個(gè)元素。 又由于每個(gè)十進(jìn)制數(shù)轉(zhuǎn)化成二進(jìn)制位的話(huà)，1的個(gè)數(shù)最多只需O(logN)個(gè)，所以，復(fù)雜度只需O(logN)。詳細(xì)操作：詳細(xì)操作：2k：X and X插入或刪除：插入或刪除：While x0 doBeginSum:=sum+cx;X:=x-(x and x);End;樹(shù)狀數(shù)組樹(shù)狀數(shù)組優(yōu)勢(shì)優(yōu)勢(shì) 代碼長(zhǎng)度短，不易出錯(cuò)。代碼長(zhǎng)度短，不易出錯(cuò)。 思想巧妙，算法復(fù)雜度低。思想巧妙，算法復(fù)雜度低。 維護(hù)簡(jiǎn)單，空間耗費(fèi)低。維護(hù)簡(jiǎn)單，空間耗費(fèi)低。 易推行到二維甚至三維易推行到二維甚至三維等等。等等。 例題二：Cow Xor農(nóng)民約翰

5、在喂奶牛的時(shí)候被另一個(gè)問(wèn)題卡住了。他的一切N(1 =N = 100,000)個(gè)奶牛在他面前排成一行(按序號(hào)1.N 的順序)，按照它們的社會(huì)等級(jí)排序。奶牛#1 由最高的社會(huì)等級(jí)，奶牛#N 最低。每個(gè)奶牛同時(shí)被賦予了一個(gè)獨(dú)一的數(shù)在0.221 -1的范圍內(nèi)。協(xié)助農(nóng)民約翰找出應(yīng)該從那一頭奶牛開(kāi)場(chǎng)喂，使得從它開(kāi)場(chǎng)的某一個(gè)延續(xù)的子序列上的奶牛的數(shù)的異或值最大。假設(shè)有多個(gè)這樣的子序列，選擇結(jié)尾的奶牛社會(huì)等級(jí)最高的。假設(shè)還不獨(dú)一，選擇最短的。直接枚舉起始點(diǎn)和終結(jié)點(diǎn)直接枚舉起始點(diǎn)和終結(jié)點(diǎn) ？時(shí)間復(fù)雜度是時(shí)間復(fù)雜度是O(N*N) Impossible!根據(jù)異或的性質(zhì)，可以得出以下結(jié)論：根據(jù)異或的性質(zhì)，可以得出以下

6、結(jié)論： Sumk=a1 xor a2 xor a3 ak-1 xor ak ai xor ai+1 aj-1 xor aj=Sumj xor Sumi-1二進(jìn)制思想二進(jìn)制思想數(shù)的范圍在數(shù)的范圍在0.221 10.221 1的整數(shù)的整數(shù) 把這些數(shù)轉(zhuǎn)化成二進(jìn)制只需把這些數(shù)轉(zhuǎn)化成二進(jìn)制只需2121位位 有用嗎？有用嗎？ Of Course！0101二叉樹(shù)二叉樹(shù)顧名思義，樹(shù)的節(jié)點(diǎn)的值為顧名思義，樹(shù)的節(jié)點(diǎn)的值為0 0或或1 1。插入插入每次插入的時(shí)候，根據(jù)這個(gè)數(shù)的二進(jìn)每次插入的時(shí)候，根據(jù)這個(gè)數(shù)的二進(jìn)制數(shù)進(jìn)展建樹(shù)，第制數(shù)進(jìn)展建樹(shù)，第i i位是位是1 1那么向左兒子那么向左兒子建一條邊，反之向右兒子建邊。建

7、一條邊，反之向右兒子建邊。插入插入每次插入的時(shí)候，根據(jù)這個(gè)數(shù)的二進(jìn)每次插入的時(shí)候，根據(jù)這個(gè)數(shù)的二進(jìn)制數(shù)進(jìn)展建樹(shù)，第制數(shù)進(jìn)展建樹(shù)，第i i位是位是1 1那么向左兒子那么向左兒子建一條邊，反之向右兒子建邊。建一條邊，反之向右兒子建邊。查詢(xún)查詢(xún)每次查詢(xún)的時(shí)候，用貪婪的思想根每次查詢(xún)的時(shí)候，用貪婪的思想根據(jù)這個(gè)數(shù)的二進(jìn)制數(shù)進(jìn)展，第據(jù)這個(gè)數(shù)的二進(jìn)制數(shù)進(jìn)展，第i i位是位是1 1假設(shè)有右兒子那么向右兒子進(jìn)展，反假設(shè)有右兒子那么向右兒子進(jìn)展，反之向左兒子進(jìn)展。之向左兒子進(jìn)展。查詢(xún)查詢(xún)每次查詢(xún)的時(shí)候，用貪婪的思想根每次查詢(xún)的時(shí)候，用貪婪的思想根據(jù)這個(gè)數(shù)的二進(jìn)制數(shù)進(jìn)展，第據(jù)這個(gè)數(shù)的二進(jìn)制數(shù)進(jìn)展，第i i位是位是1 1假設(shè)有右兒子那么向右兒子進(jìn)展，反假設(shè)有右兒子那么向右兒子進(jìn)展，反之向左兒子進(jìn)展。之向左兒子進(jìn)展。這樣，每次插入和查詢(xún)的時(shí)間復(fù)雜度這樣，每次插入和查詢(xún)的時(shí)間復(fù)雜度為為O(logN)O(logN)的，對(duì)與這道標(biāo)題整體的的，對(duì)與這道標(biāo)題整體的時(shí)間復(fù)雜度為時(shí)間復(fù)雜度為O(NlogN)O(NlogN)。這道標(biāo)題完美處理這道標(biāo)題完美處理 總結(jié)總結(jié) 二進(jìn)制思