2023學(xué)年完整公開課版第10單元電子_第1頁
2023學(xué)年完整公開課版第10單元電子_第2頁
2023學(xué)年完整公開課版第10單元電子_第3頁
2023學(xué)年完整公開課版第10單元電子_第4頁
2023學(xué)年完整公開課版第10單元電子_第5頁
已閱讀5頁,還剩114頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

第10單元位運(yùn)算及標(biāo)準(zhǔn)模板庫林厚從信息學(xué)奧賽課課通(C)第1課位運(yùn)算學(xué)習(xí)目標(biāo)1理解與掌握C中的位運(yùn)算。2靈活應(yīng)用位運(yùn)算優(yōu)化程序。任何信息在計算機(jī)中都是采用二進(jìn)制表示的,數(shù)據(jù)在計算機(jī)中是以補(bǔ)碼形式存儲的,位運(yùn)算就是直接對整數(shù)在內(nèi)存中的二進(jìn)制位進(jìn)行運(yùn)算。由于位運(yùn)算直接對內(nèi)存數(shù)據(jù)進(jìn)行操作,不需要轉(zhuǎn)換成十進(jìn)制,因此處理速度非??欤谛畔W(xué)競賽中往往可以優(yōu)化理論時間復(fù)雜度的系數(shù)。同時,一個整數(shù)的各個二進(jìn)制位互不影響,利用位運(yùn)算的一些技巧可以幫助我們簡化程序代碼。1位運(yùn)算符C提供了按位與()、按位或(|)、按位異或(^)、取反(~)、左移(<<)、右移(>>)這6種位運(yùn)算符。這些運(yùn)算符只能用于整型操作數(shù),即只能用于帶符號或無符號的char、short、int與long類型。1位運(yùn)算符(1)按位與()“ab”是指將參加運(yùn)算的兩個整數(shù)a和b,按二進(jìn)制位進(jìn)行“與”運(yùn)算。如果兩個相應(yīng)的二進(jìn)制位數(shù)字都為1,則該位的結(jié)果為1;否則為0。這里的1可以理解為邏輯中的true,0可以理解為邏輯中的false。“按位與”其實與邏輯上“與”的運(yùn)算規(guī)則一致。1位運(yùn)算符(2)按位或(|)“a|b”是指將參加運(yùn)算的兩個整數(shù)a和b,按二進(jìn)制位進(jìn)行“或”運(yùn)算。如果兩個相應(yīng)的二進(jìn)制位數(shù)字有一個為1,則該位的結(jié)果為1;否則為0?!鞍次换颉逼鋵嵟c邏輯上“或”的運(yùn)算規(guī)則一致。1位運(yùn)算符(3)按位異或(^)“a^b”是指將參加運(yùn)算的兩個整數(shù)a和b,按二進(jìn)制位進(jìn)行“異或”運(yùn)算。如果兩個相應(yīng)的二進(jìn)制位數(shù)字不相同,則該位的結(jié)果為1;否則為0。1位運(yùn)算符(4)取反(~)“~a”是指將整數(shù)a的各個二進(jìn)制位都取反,即1變?yōu)?,0變?yōu)??!皛”是一元運(yùn)算符。1位運(yùn)算符(5)左移(<<)“a<<b”是指將整數(shù)a的各個二進(jìn)制位左移b位,高位丟棄,低位用0補(bǔ)齊。需要注意的是b必須是非負(fù)整數(shù)。在高位沒有1丟棄的情況下,a<<1相當(dāng)于a*2。1位運(yùn)算符(6)右移(>>)“a>>b”是指將整數(shù)a的各個二進(jìn)制位右移b位,低位丟棄。對于無符號數(shù),高位補(bǔ)0。對于有符號數(shù),某些機(jī)器將對左邊空出的部分用符號位填補(bǔ)(即“算術(shù)移位”),而另一些機(jī)器則對左邊空出的部分用0填補(bǔ)(即“邏輯移位”)。同樣,b必須是非負(fù)整數(shù)。a>>1相當(dāng)于a/2。1位運(yùn)算符位運(yùn)算符也可以與賦值運(yùn)算符組成復(fù)合運(yùn)算符。例如a=b相當(dāng)于a=ab,a<<=2相當(dāng)于a=a<<2。位運(yùn)算符也是有優(yōu)先級的,“~”的運(yùn)算優(yōu)先級高于“乘除”而與“!”、“”、“--”一致,“>>”和“<<”的運(yùn)算優(yōu)先級低于“加減”,“”的運(yùn)算優(yōu)先級低于“關(guān)系運(yùn)算”而高于“^”,“^”的優(yōu)先級高于“|”,而“|”的優(yōu)先級高于“”和“||”。為了避免出錯,增強(qiáng)程序的可讀性,利于調(diào)試,建議在需要的地方添加括號來保證優(yōu)先運(yùn)算。比如1<<5-1,建議寫成1<<5-1,等價于1<<4。2位運(yùn)算應(yīng)用舉例位運(yùn)算的應(yīng)用場合非常廣泛,如高效代替布爾型數(shù)組,表示集合、搜索算法中的狀態(tài)判重(hash)、動態(tài)規(guī)劃算法中的狀態(tài)壓縮等。例1、閱讀程序,寫出程序的運(yùn)行結(jié)果,體會位運(yùn)算的思想。//esain{ int=3,y=8,; ^=y;y^=;^=y; cout<<<<““<<y<<endl; =y^y>>1; cout<<<<endl; return0;}例2、整數(shù)冪判斷一個數(shù)n是不是2的整數(shù)冪,比如64=26,所以輸出“yes”,而65無法表示成2的整數(shù)冪形式,所以輸出“no”。n在int范圍以內(nèi)?!締栴}分析】我們考慮一個數(shù)如果是2的整數(shù)冪會有什么特殊性。觀察發(fā)現(xiàn)64轉(zhuǎn)換成二進(jìn)制為01000000,只有一個位是1。將這個數(shù)減去1,就變成00111111的形式,我們將這2個數(shù)做按位與運(yùn)算,發(fā)現(xiàn)結(jié)果為0。分析發(fā)現(xiàn),如果一個數(shù)不能表示成2的整數(shù)冪形式,則以上過程的運(yùn)算結(jié)果一定不為0。所以,可以利用位運(yùn)算將算法的時間復(fù)雜度優(yōu)化成O1。//esain{ intn; cin>>n; ifnn-1cout<<“no“<<endl; elsecout<<“yes“<<endl; return0;}例3、找數(shù)【問題描述】給出n個整數(shù),n為奇數(shù),其中有且僅有一個數(shù)出現(xiàn)了奇數(shù)次,其余的數(shù)都出現(xiàn)了偶數(shù)次。用線性時間復(fù)雜度、常數(shù)空間復(fù)雜度找出出現(xiàn)了奇數(shù)次的那個數(shù)?!据斎敫袷健康谝恍幸粋€整數(shù)n,1≤n≤5×106。接下來n行,每行一個數(shù)。【輸出格式】輸出一行一個整數(shù),表示出現(xiàn)了奇數(shù)次的那一個數(shù)?!据斎霕永?331242554【輸出樣例】1【問題分析】從頭到尾“異或”一遍,最后得到的那個數(shù)就是出現(xiàn)了奇數(shù)次的數(shù)。這是因為異或有一個神奇的性質(zhì):兩次異或同一個數(shù),結(jié)果不變。再考慮“異或”運(yùn)算滿足交換律,先異或、后異或都是一樣的,因此這個算法顯然正確。參考程序見教材510-511頁。實踐鞏固第2課vector學(xué)習(xí)目標(biāo)1了解C的標(biāo)準(zhǔn)模板庫。2掌握vector容器的使用方法。標(biāo)準(zhǔn)模板庫(StandardTemplateLibrary,STL)C功能強(qiáng)大,為開發(fā)者提供了標(biāo)準(zhǔn)模板庫,其中封裝了很多實用的容器。容器可以理解成能夠?qū)崿F(xiàn)很多功能的系統(tǒng)函數(shù),或者說用來存放數(shù)據(jù)的對象,開發(fā)者可以根據(jù)接口規(guī)范(調(diào)用格式)直接調(diào)用,而不用關(guān)心其內(nèi)部實現(xiàn)的原理和具體代碼,十分方便快捷。常見的容器有vector、stac、queue、map、set等。vectorvector直接翻譯為“向量”,一般說成“變長數(shù)組”,也即“長度根據(jù)需要而自動改變的數(shù)組。在信息學(xué)競賽中,有些題目需要定義很大的數(shù)組,這樣會出現(xiàn)“超出內(nèi)存限制”的錯誤。比如,如果一個圖的頂點太多,使用鄰接矩陣就會超出內(nèi)存限制,使用指針實現(xiàn)鄰接表又很容易出錯,而使用vector實現(xiàn)簡潔方便,還可以節(jié)省存儲空間。使用vector,首先需要添加vector頭文件,即include<vector>,同時,必須要有“usingnamespacestd”。1vector的定義定義一個vector的方法如下:vector<tye>name;以上定義相當(dāng)于定義了一個一維數(shù)組name,只是sie不確定,其長度可以根據(jù)需要而變化。其中tye可以是任何基本類型,例如int、double、char、結(jié)構(gòu)體等,也可以是STL標(biāo)準(zhǔn)容器,例如vector、queue等。訪問vector中的元素一般有兩種方式。第一種是通過“下標(biāo)”訪問。例如,對于容器vector<int>v,可以使用v來訪問它的第inde個元素。其中,0≤inde≤-1,表示vector中元素的個數(shù)。第二種方式是通過“迭代器”訪問??梢詫⒌鳎╥terator)理解為一種類似指針的變量。其定義為:vector<tye>::iteratorit;2vector的訪問例如:vector<int>::iteratorit=;forinti=0;i<=5;iprintf"%d",*iti;3vector的常用函數(shù)(1)push_bacpush_bac用來在vector后面添加一個元素,時間復(fù)雜度為01。(2)sie如果是一維數(shù)組,sie用來獲得vector中元素的個數(shù);如果是二維數(shù)組,sie用來獲得vector中第二維的元素個數(shù),時間復(fù)雜度為01。(3)pop_bacpop_bac用來刪除vector的尾元素,時間復(fù)雜度為01。3vector的常用函數(shù)(4)clearclear用來清空vector中的所有元素,時間復(fù)雜度為0n,其中n為vector中元素的個數(shù)。(5)insertinsertit,用來向vector任意迭代器it處插入一個元素,時間復(fù)雜度為0n。(6)eraseerase用來刪除vector中的元素,有兩種用法。一種是eraseit,刪除迭代器it處的元素;另一種是erasefirst,last,刪除左閉右開區(qū)間[first,last內(nèi)的所有元素。4vector的應(yīng)用舉例例1、中間數(shù)【問題描述】依次讀入若干正整數(shù),如果是奇數(shù)個就輸出最中間的那個數(shù);否則,輸出中間兩個數(shù)的和。以0作為結(jié)束標(biāo)志,但0不計數(shù)。【問題分析】參考程序見教材516-517頁。例2、上網(wǎng)統(tǒng)計【問題描述】在一個網(wǎng)絡(luò)系統(tǒng)中有N個用戶、M次上網(wǎng)記錄。每個用戶可以自己注冊一個用戶名,每個用戶名是一個只含小寫字母且長度小于1000的字符串。每個上網(wǎng)的賬號每次上網(wǎng)都會瀏覽網(wǎng)頁,網(wǎng)頁名是以一個只含小寫字母且長度小于1000的字符串,每次上網(wǎng)日志里都會有記錄,現(xiàn)在請統(tǒng)計每個用戶每次瀏覽了多少個網(wǎng)頁?!据斎敫袷健康?行包含兩個用1個空格隔開的正整數(shù)N(1≤N≤1000)和M(1≤M≤5000)。第2~M1行,每行包含2個用1個空格隔開的字符串,分別表示用戶名和瀏覽的網(wǎng)頁名?!据敵龈袷健抗睳行,每行的第一個字符串是用戶名,接下來的若干字符串是這個用戶依次瀏覽的網(wǎng)頁名(之間用一個空格隔開)。按照用戶名出現(xiàn)的次序排序輸出。【輸入樣例】57goodstudyerbooshoeeweb【輸出樣例】goodstudyerbooshoeeweb【問題分析】由于用戶名和瀏覽的網(wǎng)頁名長度不固定,用vector解決比較方便,可以分別通過“下標(biāo)”訪問和“迭代器”訪問。參考程序見教材517-519頁。例3、蛇形方陣【問題描述】輸入n,n≤100,輸出n階蛇形方陣。例如n=5時,輸出如下:12671535814164913172210121821231119202425【問題分析】定義一個二維數(shù)組,模擬蛇形方陣填數(shù)的過程。具體程序參見教材520頁。實踐鞏固第3課stac學(xué)習(xí)目標(biāo)掌握stac容器的使用方法。stac的定義stac翻譯為棧,是STL中實現(xiàn)的一個“后進(jìn)先出”的容器,其只能通過toese>name;其中,tye可以是任何基本類型或者容器,name是棧的名字。1stac的常用函數(shù)(1)pty用來檢測stac是否為空,空返回true,否則返回false,時間復(fù)雜度為01。(5)siesie用來返回stac內(nèi)元素的個數(shù),時間復(fù)雜度為01。2stac的應(yīng)用舉例例1、括號的匹配【問題描述】棧在計算機(jī)科學(xué)領(lǐng)域有著廣泛的應(yīng)用。比如在編譯和運(yùn)行計算機(jī)程序的過程中,就需要用棧進(jìn)行語法檢查,如檢查begin和end、{和}、(和)等是否匹配。假設(shè)一個表達(dá)式只由小寫英文字母、運(yùn)算符(,-,*,/)和左、右小括號構(gòu)成,以“@”作為表達(dá)式的結(jié)束符。請編程檢查表達(dá)式中的左、右小括號是否匹配,若匹配,則返回“YES”;否則返回“NO”,不必關(guān)心表達(dá)式中的其他錯誤。【問題分析】用一個棧存放表達(dá)式中從左往右的左小括號。從左往右按順序掃描表達(dá)式的每個字符,若是“(”,則將它壓棧;若是“)”,則執(zhí)行一次出棧操作。當(dāng)棧發(fā)生下溢(右括號多)或當(dāng)表達(dá)式處理完畢而棧非空(左括號多)時,意味著表達(dá)式中的括號不匹配,則輸出“NO”;否則,表示小括號完全匹配,就輸出“YES”。參考程序見教材524頁。例2、溶液模擬器【問題分析】小Y雖有很多溶液,但還是沒有辦法配成想要的溶液,因為萬一倒錯了就沒有辦法挽回了。他從網(wǎng)上下載了一個溶液配置模擬器:模擬器在計算機(jī)中構(gòu)造一種虛擬溶液,然后可以虛擬地向當(dāng)前虛擬溶液中加入一定濃度、一定質(zhì)量的這種溶液,模擬器會快速地算出倒入后虛擬溶液的濃度和質(zhì)量。模擬器的使用步驟如下:(1)為模擬器設(shè)置一個初始質(zhì)量和濃度V0、C0%(0≤C0≤100)。(2)進(jìn)行一系列操作,模擬器支持兩種操作:一種是P(v,c)操作,表示向當(dāng)前的虛擬溶液中加入質(zhì)量為v、濃度為c的溶液;另一種是操作,即撤銷上一步P操作?!据斎敫袷健康?行兩個整數(shù)V0、C0。第2行1個整數(shù)n,n≤10000,表示操作數(shù)。接下來的n行,每行一條操作,格式為:P_v_c或。其中“_”代表一個空格,當(dāng)只剩初始溶液的時候,再撤銷就沒有用了。任意時刻質(zhì)量都不會超過231-1。【輸出格式】輸出n行,每行兩個數(shù)Vi、Ci,之間用一個空格隔開,其中Vi為整數(shù),Ci為實數(shù)(保留5位小數(shù))。其中,第i行表示第i次操作以后的溶液質(zhì)量和濃度?!据斎霕永?001002P1000【輸出樣例】200500000010010000000【問題分析】使用棧來模擬實現(xiàn)。讀入撤銷時,棧頂元素出棧;讀入溶液時,把新的溶液的質(zhì)量和濃度壓棧。每次操作完,輸出棧頂?shù)馁|(zhì)量和濃度。參考程序見教材525-526頁。例3、表達(dá)式求值【題目描述】給定一個只包含加法和乘法的算術(shù)表達(dá)式,請編程計算表達(dá)式的值?!据斎敫袷健枯斎雰H有一行,為計算所需要的表達(dá)式,表達(dá)式中只包含數(shù)字、加法運(yùn)算符“”和乘法運(yùn)算符“*”,且沒有括號,所有參與運(yùn)算的數(shù)字均為0~231-1之間的整數(shù)。輸入數(shù)據(jù)保證這一行只有0~9、、*這12種字符?!据敵龈袷健枯敵鲋挥幸恍?,包含一個整數(shù),表示這個表達(dá)式的值。注意:當(dāng)答案長度多于4位時,請只輸出最后4位,前導(dǎo)0不輸出?!据斎胼敵鰳永俊緲永忉尅繕永?計算的結(jié)果為8,直接輸出8。樣例2計算的結(jié)果為1234567891,輸出后4位,即7891。樣例3計算的結(jié)果為1000000004,輸出后4位,即4?!緮?shù)據(jù)規(guī)?!繉τ?0%的數(shù)據(jù),0≤表達(dá)式中加法運(yùn)算符和乘法運(yùn)算符的總數(shù)≤100。對于80%的數(shù)據(jù),0≤表達(dá)式中加法運(yùn)算符和乘法運(yùn)算符的總數(shù)≤1000。對于100%的數(shù)據(jù),0≤表達(dá)式中加法運(yùn)算符和乘法運(yùn)算符的總數(shù)≤100000。【問題分析】由于只有加號和乘號,只要從左往右掃一遍,如果遇到乘號直接計算(做乘法);如果遇到加號,若后面沒有符號或者后面的一個符號也是加號,則直接計算(做加法),否則先把后面緊接著的連續(xù)的乘號算完,最后再加。算法實現(xiàn)中,只要設(shè)置一個棧保存沒有立即進(jìn)行的加法,掃描結(jié)束后再一起處理棧中的加法運(yùn)算。同時,因為把一個數(shù)字串轉(zhuǎn)換成數(shù)也需要單獨編寫一個子程序。最后,還要注意在運(yùn)算過程中及時對10000取模。參考程序見教材527-528頁。實踐鞏固第4課queue和priority_queue學(xué)習(xí)目標(biāo)1掌握queue容器的使用方法。2初步掌握priority_queue容器的使用方法。隊列queue翻譯為隊列,是STL中實現(xiàn)的一個“先進(jìn)先出”的容器,只能通過函數(shù)front來訪問隊首元素,或通過函數(shù)bac來訪問隊尾元素。要使用queue,必須先添加queue頭文件,即include<queue>,同時,必須要有“usingnamese>name;其中,tye可以是任何基本類型或者容器,name為隊列的名字。1queue的常用函數(shù)(1)pty用來檢測queue是否為空,返回true或者false,時間復(fù)雜度為01。(5)siesie返回queue內(nèi)元素的個數(shù),時間復(fù)雜度為01。2queue的應(yīng)用舉例例1、瓷磚【問題描述】在一個w×h的矩形廣場上,每一塊1×1的地面都鋪設(shè)了紅色或黑色的瓷磚。小林同學(xué)站在某一塊黑色的瓷磚上,他可以從此處出發(fā),移動到上、下、左、右四個相鄰的且是黑色的瓷磚上。現(xiàn)在,他想知道,通過重復(fù)上述移動所能經(jīng)過的黑色瓷磚數(shù)?!据斎敫袷健康?行為h、w,2≤w、h≤50,之間由一個空格隔開。以下為一個w行h列的二維字符矩陣,每個字符為“”“”“@”,分別表示該位置為黑色的瓷磚、紅色的瓷磚,以及小林的初始位置。【輸出格式】輸出一行一個整數(shù),表示小林從初始位置出發(fā)可以到達(dá)的瓷磚數(shù)?!据斎胼敵鰳永俊締栴}分析】本題是典型的“求連通塊”問題,可以采用經(jīng)典的“寬度優(yōu)先搜索”算法求解,使用隊列維護(hù)。參考程序見教材531-532頁。例2、關(guān)系網(wǎng)絡(luò)【問題描述】有n個人,他們的編號為1~n,其中有一些人相互認(rèn)識,現(xiàn)在想要認(rèn)識y,可以通過他所認(rèn)識的人來認(rèn)識更多的人(如果認(rèn)識y、y認(rèn)識,那么可以通過y來認(rèn)識),求出最少需要通過多少人才能認(rèn)識y?!据斎敫袷健康?行3個整數(shù)n、、y,n≤100,1≤、y≤n。接下來是一個n×n的鄰接矩陣,a=1表示i認(rèn)識j,0表示不認(rèn)識。保證i=j時,a。行中的每兩個數(shù)之間用一個空格分開?!据敵龈袷健枯敵鲆恍幸粋€數(shù),表示認(rèn)識y最少需要通過的人數(shù)。【樣例輸入】5150100010110010100110100010【樣例輸出】2【問題分析】本題是典型的“求最優(yōu)值”問題,可以通過經(jīng)典的“寬度優(yōu)先搜索”算法解決,使用隊列維護(hù)。參考程序見教材533-534頁。3priority_queueSTL的容器中還有兩種容器與隊列有關(guān),分別是雙端隊列(deque)和優(yōu)先隊列(priority_queue)。priority_queue翻譯為優(yōu)先隊列,一般用來解決一些貪心問題,其底層是用“堆”來實現(xiàn)的。在優(yōu)先隊列中,任何時刻,隊首元素一定是當(dāng)前隊列中優(yōu)先級最高(優(yōu)先值最大)的那一個(大根堆),也可以是最小的那一個(小根堆)??梢圆粩嗤鶅?yōu)先隊列中添加某個優(yōu)先級的元素,也可以不斷彈出優(yōu)先級最高的那個元素,每次操作其會自動調(diào)整結(jié)構(gòu),始終保證隊首元素的優(yōu)先級最高。3priority_queue定義和使用e>name;其中,tye可以是任何基本類型或者容器,name為優(yōu)先隊列的名字。和queue不一樣的是,priority_queue沒有front和bac,而只能通過top或pop訪問隊首元素(也稱堆頂元素),也就是優(yōu)先級最高的元素。4priority_queue的常用函數(shù)(1)pushpush是將加入優(yōu)先隊列,時間復(fù)雜度為Olog2n,n為當(dāng)前優(yōu)先隊列中的元素個數(shù)。加入后會自動調(diào)整priority_queue的內(nèi)部結(jié)構(gòu),以保證隊首元素堆頂元素的優(yōu)先級最高。(2)toptop是獲得隊首元素堆頂元素,時間復(fù)雜度為O1。(3)poppop是讓隊首元素堆頂元素出隊,時間復(fù)雜度為Olog2n,n為當(dāng)前優(yōu)先隊列中的元素個數(shù)。出隊后會自動調(diào)整priority_queue的內(nèi)部結(jié)構(gòu),以保證隊首元素堆頂元素的優(yōu)先級最高。4priority_queue的常用函數(shù)如何定義priority_queue內(nèi)元素的優(yōu)先級是應(yīng)用好優(yōu)先隊列的關(guān)鍵。對于可以直接使用的基本數(shù)據(jù)類型(int等),優(yōu)先隊列對它們的優(yōu)先級設(shè)置一般是數(shù)字越大的優(yōu)先級越高(對于char,則是字典序最大的)。以下兩種優(yōu)先隊列的定義是等價的:priority_queue<int>q;priority_queue<int,vector<int>,less<int>>q;第二種定義方式的尖括號內(nèi)多出了2個參數(shù):一個是vector<int>,表示的是承載底層數(shù)據(jù)結(jié)構(gòu)——堆(heap)的容器,其類型要與第1個參數(shù)一致;另一個是less<int>,是對第1個參數(shù)的比較類,less<int>表示數(shù)字越大的優(yōu)先級越大(大根堆),而如果用greater<int>則表示數(shù)字越小的優(yōu)先級越大(小根堆)。5priority_queue應(yīng)用舉例例3、有序表的最小和【問題描述】給出兩個長度為n的有序表A和B,在A和B中各任取一個元素,可以得到n2個和,求這些和中最小的n個?!据斎敫袷健康?行包含1個整數(shù)正n(n≤400000)。第2行與第3行分別有n個整數(shù),各代表有序表A和B。一行中的每兩個整數(shù)之間用一個空格隔開,大小在長整型范圍內(nèi),數(shù)據(jù)保證有序表單調(diào)遞增?!据敵龈袷健枯敵龉瞡行,每行一個整數(shù),第i行為第i小的和。數(shù)據(jù)保證在longlong范圍內(nèi)。【輸入樣例】3125247【輸出樣例】345【問題分析】可以把這些和看成n個有序表:然后用堆來維護(hù),堆中始終保持n個元素,每次取出堆中最小的元素,把如上對應(yīng)的有序表中后一個元素加入堆。一共輸出n個元素,時間復(fù)雜度為Onlog2n,空間復(fù)雜度為On。參考程序見教材536-537頁。實踐鞏固第5課map和pair學(xué)習(xí)目標(biāo)1掌握map容器的使用方法。2掌握pair容器的使用方法。maaap可以將任何基本類型(包括STL容器)映射到任何基本類型(包括STL容器)。mapmaaap當(dāng)布爾型數(shù)組使用(哈希表)。3)字符串與字符串之間的映射。map要使用maaaesaae1,tye2>name;其中,tye1是映射前的類型(鍵ey),tye2是映射后的類型(值value),name為映射的名字。普通int數(shù)組a就是maaaaap的鍵和值都是唯一的。map1map的訪問訪問maaae1,tye2>::iteratorit;因為mae,所以,我們使用“it->first”來訪問鍵,而使用“it->second”來訪問值。2map的常用函數(shù)(1)find和siefindey是返回鍵為ey的映射的迭代器,時間復(fù)雜度為0log2n,n為maaap,時間復(fù)雜度為0n。2map的常用函數(shù)(3)eraseerase可以刪除單個元素,也可以刪除一個區(qū)間內(nèi)的所有元素。刪除單個元素可以用:eraseit,it為要刪除的元素的迭代器,時間復(fù)雜度為O1。也可以用:eraseey,ey為要刪除的映射的鍵,時間復(fù)雜度為Olog2n。刪除一個區(qū)間內(nèi)的所有元素用:erasefirst,last,first為區(qū)間的起始迭代器,last為區(qū)間的末尾迭代器的下一個地址,也就是左閉右開的區(qū)間[first,last,時間復(fù)雜度為Olast-first。3pair的定義和使用e1first; tye2second;}3pair的定義和使用要使用esaae1,tye2>name;4map和pair的應(yīng)用舉例例1、指數(shù)序列【問題描述】伊凡在紙上寫下了一個由n個非負(fù)整數(shù)組成的序列a1,a2,…,an。這個序列保證單調(diào)不降。接著,伊凡又在紙上寫下了另一個序列2a1,2a2,…,2an?,F(xiàn)在他想知道,最少要在這個序列中添加多少個形式為2的數(shù)(為非負(fù)整數(shù)),才能使這個序列所有整數(shù)的和為2v-1,其中v為某個非負(fù)整數(shù)。【輸入格式】第1行包括1個正整數(shù)n(1≤n≤105)。第2行包括n個由空格隔開的整數(shù)a1,a2,…,an。其中,0≤ai≤2×109,保證a1≤a2≤…≤an?!据敵龈袷健枯敵鲆恍幸粋€整數(shù),表示最少在序列中添加數(shù)的數(shù)量?!据斎霕永?】40111【輸出樣例1】0【輸入樣例2】13【輸出樣例2】3【樣例解釋】在第1個樣例中不需要添加任何數(shù),因為20212121=1222=7=23-1。在第2個樣例中,需要至少添加3個數(shù),分別為20,21,22。【問題分析】如果問題中的序列ai單調(diào)遞增,則相當(dāng)于已知一個ai位為1的二進(jìn)制數(shù),只需在剩余的零位補(bǔ)上1即可。對于單調(diào)不降的序列大致一樣,只是需要增加進(jìn)位操作。由于進(jìn)位是連續(xù)的,所以0的位置也是連續(xù)的。暴力統(tǒng)計0的數(shù)量即可??紤]到ai≤2×109,可以使用map來進(jìn)行優(yōu)化。參考程序見教材544-545頁。例2、查字典【問題描述】小明正在復(fù)習(xí)全國英語四級考試,他手里有一本詞典,現(xiàn)在有很多單詞要查。請編寫程序幫助他快速找到要查的單詞所在的頁碼?!据斎敫袷健康?行1個正整數(shù)N,N≤10000,表示字典中一共有多少單詞。接下來每兩行表示一個單詞,其中:第1行是一個長度小于或等于100的字符串,表示這個單詞,全部小寫字母,單詞不會重復(fù)。第2行是1個整數(shù),表示這個單詞在字典中的頁碼。接下來的一行是1個整數(shù)M,M≤10000,表示要查的單詞數(shù)。接下來的M行,每行一個字符串,表示要查的單詞,保證在字典中存在。【輸出格式】M行,每行一個正整數(shù),表示第i個單詞在字典中的頁碼。【輸入樣例】2scan10word152scanword【輸出樣例】1015【問題分析】由于單詞各不相同,所以只要將單詞映射到數(shù)字即可。參考程序見教材546頁。實踐鞏固第6課set學(xué)習(xí)目標(biāo)掌握set容器的使用方法。set翻譯為集合,是一個內(nèi)部自動有序且不含重復(fù)元素的容器。set最主要的作用就是自動去重并按升序排序,因此遇到需要去重但是又不方便直接開數(shù)組的情況。set中的元素是唯一的,其內(nèi)部采用“紅黑樹”實現(xiàn)。使用set前,必須先添加set頭文件,即include<set>,同時,必須要有“usingnamese>name;其中,tye可以是任何基本類型或者容器,name是集合的名字。set也可以定義set數(shù)組,例如:set<int>st中的每一個元素都是一個set容器。需要注意的是,set只能通過迭代器訪問。即先定義一個迭代器:set<tye>::iteratorit;然后使用“*it”來訪問set中的元素。set也不支持“*iti”和“it<”的訪問方式(實際上除了vector和string之外的STL容器都不支持)。set(1)insert和sieinsert用來將插入到set中,并自動遞增排序和去重,時間復(fù)雜度為Olog2n,n為set中的元素個數(shù)。sie用來獲得set中的元素個數(shù),時間復(fù)雜度為O1。(2)findfind(value)是返回set中對應(yīng)值為value的迭代器,時間復(fù)雜度為Olog2n。(3)clearclear用來清空set中的所有元素,時間復(fù)雜度為On。1set的常用函數(shù)(4)eraseerase可以刪除單個元素,也可以刪除一個區(qū)間內(nèi)的所有元素。刪除單個元素可以用:eraseit,it為要刪除的元素的迭代器,時間復(fù)雜度為O1。也可以用:erasevalue,value為要刪除的元素的值,時間復(fù)雜度為Olog2n。刪除一個區(qū)間內(nèi)的所有元素用:erasefirst,last,first為區(qū)間的起始迭代器,last為區(qū)間的末尾迭代器的下一個地址,也就是左閉右開的區(qū)間[first,last),時間復(fù)雜度為Olast-first。1set的常用函數(shù)2set的應(yīng)用舉例例1、NOI道題。他有n個學(xué)生,第i個學(xué)生完成了,表示學(xué)生數(shù)和題庫中的題目總量。第2~n1行,先是1個正整數(shù)p,然后p個整數(shù)表示第i個學(xué)生的做題記錄(可能重復(fù)做同一道題)。第n2行,1個正整數(shù),表示要舉行的比賽和訓(xùn)練總數(shù)(可能有學(xué)生重復(fù)報名)。接下來的行,每行的第1個整數(shù)type表示是訓(xùn)練或者比賽(1為訓(xùn)練,0為比賽)。第2個數(shù)q表示參賽學(xué)生數(shù),然后q個正整數(shù)表示參賽學(xué)生編號。每一行中的兩個數(shù)之間有一個空格。【輸出格式】共行,每行表示本次訓(xùn)練或比賽可選的題目(由小到大排序,中間用一個空格隔開,如果沒有輸出一個空行)?!緲永斎搿?102371324733610712347896033450313412130151121235【樣例輸出】51258975610347【問題分析】本題只要使用set去重與查找,對于每一問維護(hù)一個答案集合。參考程序見教材552-553頁。例2、列車調(diào)度【問題描述】兩端分別是一條入口(Entrance)軌道和一條出口(Eit)軌道,它們之間有N條平行的軌道,如圖106-1所示。每趟列車從入口可以選擇任意一條軌道進(jìn)入,最后從出口離開。在圖中有9趟列車,在入口處按照{(diào)8,4,2,5,3,9,1,6,7}的順序排隊等待進(jìn)入。如果要求它們必須按序號遞減的順序從出口離開,則至少需要多少條平行鐵軌用于調(diào)度?【輸入格式】第1行給出1個正整數(shù)N,2≤N≤105。第2行給出從1~N的正整數(shù)序號的一個重排列,數(shù)字間以一個空格分隔?!据敵龈袷健枯敵鲆恍幸粋€數(shù),表示可以將輸入的列車按序號遞減的順序調(diào)離所需要的最少的鐵軌條數(shù)?!据斎霕永?842539167【輸出樣例】4【問題分析】因為調(diào)度結(jié)束后的序列是有序的,所以每一條鐵軌也要是有序的。因為如果A與B同在一條中間鐵軌上,且A在B前,那么駛離時A一定也在B前。對于這么多條有序的數(shù)列,只要使用一次類似“歸并排序”的操作便可得到有序的解。這樣,問題就變成了經(jīng)典的導(dǎo)彈攔截的第二問,用貪心法解決即可。具體程序見教材554頁,其中使用set維護(hù)單調(diào)的鐵軌數(shù)列,使用lower_bound實現(xiàn)二分查找,lower_bound()是返回指向大于或等于的第一個元素的迭代器。實踐鞏固第7課string學(xué)習(xí)目標(biāo)掌握string容器的使用方法。string在C語言中,一般使用字符數(shù)組charstr來存放字符串,但是操作麻煩,容易出錯。C在STL中加入了string類型,對字符串常用的需求功能進(jìn)行了封裝,使得操作起來更加方便,且不必?fù)?dān)心內(nèi)存是否足夠、字符串的長度等問題。使用string,需要添加string頭文件,即include<string>,同時必須要有“usingnamese;其中,name是字符串變量的名字。例如:stringstr;也可以定義的同時初始化,即:stringstr=“abcd”。1string的訪問一種訪問string的方法,就像普通字符數(shù)組一樣操作。例如:stringstr=“abcd“;forinti=0;i<;iprintf“%c“,str;//輸出abcd如果要讀入或者輸出整個字符串,一般只能用cin和cout。如果非要用printf輸出string,則需要用c_str函數(shù)將string轉(zhuǎn)換成字符數(shù)組。例如:stringstr;cin>>str;cout<<str<<endl;printf"%s\n",;1string的訪問另一種訪問string的方法是通過迭代器,主要與insert、erase等函數(shù)配合使用。先定義string迭代器:string::iteratorit;然后就可以通過“*it”來訪問string里的每一個字符了,而且string和vector一樣,支持直接對迭代器進(jìn)行加減某個數(shù)字,3等。例如:stringstr="abcdefg";forstring::iteratorit=2;it!=;itprintf"%c",*it;//輸出cdefg2string的運(yùn)算字符串可以做“加法”運(yùn)算。加法是把兩個字符串直接拼接起來。例如:stringstr1=“abc“,str2=“y“,str3;str3=str1str2;str1=str2;cout<<str1<<endl;//輸出abcycout<<str3<<endl;//輸出abcy字符串還可以做“關(guān)系”運(yùn)算,是按照字典序比較兩個string類型的大小。例如:stringstr1=“aa“,str2=“aaa“,str3=“abc“;ifstr1<str2printf“O1“;//輸出O1ifstr1<str3printf“O2“;//輸出O23string的常用函數(shù)(1)length和sielength用來返回string的長度(字符個數(shù)),時間復(fù)雜度為O1。sie與length一樣。(2)clearclear用來清空string中的所有元素,時間復(fù)雜度為O1。(3)substrSubstrpos,len返回從pos號位置開始、長度為len的子串,時間復(fù)雜度為On。(4)insert函數(shù)insert有多種寫法,時間復(fù)雜度都是On。insertpos,string,表示在pos號位置插入字符串string。insertit,it2,it3,it為原字符串的欲插入位置,it2和it3為待插入字符串的首尾迭代器(左閉右開區(qū)間)。(5)eraseerase可以刪除單個元素,也可以刪除一個區(qū)間內(nèi)的所有元素,時間復(fù)雜度均為On。刪除單個元素用eraseit,it為要刪除的元素的迭代器。刪除一個區(qū)間內(nèi)的所有元素可以用兩種方法。erasefirst,last,first為區(qū)間的起始迭代器,last為區(qū)間的末尾迭代器的下一個地址,也就是左閉右開的區(qū)間[first,last。erasepos,length,pos為需要刪除的字符串起始位置,length為要刪除的字符個數(shù)。(6)findstr2,當(dāng)str2是str的子串時,返回其在str中第一次出現(xiàn)的位置;否則返回string::n,其中n和m分別為str和str2的長度。(7)replacepos,len,str2表示把str從pos號位開始、長度為len的子串替換為str2。it1,it2,str2,表示把str的迭代器it1~it2范圍內(nèi)(左閉右開區(qū)間)的子串替換為str2。時間復(fù)雜度都是O。時間復(fù)雜度都是O。4string的應(yīng)用舉例例1、字符串匹配【問題描述】現(xiàn)定義兩個僅由大寫字母組成的字符串的匹配程度如下:將某一字符串的首字符與另一字符串的某一字符對齊,然后后面的字符也一一對齊,直至某一字符串的串尾為止。對于每一組對齊的兩個字符,若這兩個字符相等,則計數(shù)。匹配程度為每種對齊方法的計數(shù)的最大值。最后計算這個匹配程度的2倍,與兩串總長度的最大比值?!据斎敫袷健慷嘟M數(shù)據(jù),每組一行兩個字符串,中間用一個空格隔開,以-1結(jié)束輸入?!据敵龈袷健繉τ诿拷M數(shù)據(jù),輸出兩個字符串的最大匹配數(shù)與兩串總長度的比值,具體格式見輸出樣例?!据斎霕永緾ARCARTTUREYCHICENMONEYONEY,POVERTY)=1/3app(ROUGH,PESY)=0【問題分析】本題是簡單字符串處理,暴力枚舉兩串匹配的首字母,不斷更新最大匹配值即可,最后的答案需要對最大匹配值和兩串總長進(jìn)行輾轉(zhuǎn)相除。參考程序見教材560-561頁。例2、字符串乘方【問題描述】給定兩個字符串a(chǎn)和b,定義a*b為它們的連接。例如,如果a=“abc“而b=“def“,則a*b=“abcdef“。如果將連接考慮成乘法,一個非負(fù)整數(shù)的乘方將用一種通常的方式定義:a^0=““(空字符串),a^(n1)=a*(a^n)?!据斎敫袷健棵恳粋€測試樣例是一行可打印的字符,用s表示。s的長度至少為1,且不會超過100萬。最后的測試樣例后面將是一個點號作為一行?!据敵龈袷健繉τ诿恳粋€s,你應(yīng)該打印最大的n,使得存在一個a,讓s=a^n?!据斎霕永縜bcdaaaaababab【輸出樣例】143【問題分析】分析題意可知,有循環(huán)節(jié)必定為字符串長度的約數(shù),枚舉約數(shù)判斷即可。另外,由于本題輸入量很大,如果需要請用scanf代替cin,從而避免超時。參考程序見看教材562頁。實踐鞏固第8課algorithm學(xué)習(xí)目標(biāo)初步掌握algorithm的使用方法。algorithmalgorithm翻譯為算法,是C標(biāo)準(zhǔn)模版庫中最重要的頭文件之一,提供了大量基于迭代器的非成員模板函數(shù)。要使用這些函數(shù),需要添加algorithm頭文件,即include<algorithm>,同時,必須要有“usingnamespacestd”。1ma、min、abs和swapma,y和min,y分別返回和y中的較大值和較小值,且參數(shù)必須是兩個,可以是浮點數(shù)。如果要返回3個數(shù)、y、的最大值,可以使用ma,may,的方法。abs是返回的絕對值,必須是整數(shù)。如果要求浮點數(shù)的絕對值,可以使用math頭文件下的fabs。swap,y用來交換和y的值。2reversereverse(it,it2)可以將數(shù)組指針在it~it2之間的元素,或容器的迭代器在it~it2范圍內(nèi)的所有元素進(jìn)行反轉(zhuǎn)。注意:it~it2是左閉右開區(qū)間。inta={10,11,12,13,14,15};reversea,a4;//將a這4個元素反轉(zhuǎn)forinti=0;i<6;iprintf"%d",a;//輸出131211101415stringstr="abcdefghi";reverse2,6;forinti=0;i<;iprintf"%c",str;//輸出abfedcghi3net_utationnet_utation是求出一個序列在全排列中的下一個序列。例如,n=3的全排列為:123,132,213,231,312,321,所以231的下一個排列就是312。inta={1,2,3};do{utationa,a3;//a三個元素的排列//net_utation在達(dá)到全排列的最后一個時會返回false4fill

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論