林厚從信息學(xué)奧賽課課通第7單元哈希表公開(kāi)課一等獎(jiǎng)市優(yōu)質(zhì)課賽課獲獎(jiǎng)?wù)n件

第7單元第9課哈希表信息學(xué)奧賽之?dāng)?shù)據(jù)結(jié)構(gòu)例1、用哈希表存儲(chǔ)以下線性表(18,75,60,43,54,90,46).問(wèn)題分析：假設(shè)選取的哈希函數(shù)為h(k)=kmodm,k為元素的關(guān)鍵字，m為哈希表的長(zhǎng)度，用余數(shù)作為存儲(chǔ)該元素的哈希地址。k和m均為正整數(shù)，并且m要大于或等于線性表的長(zhǎng)度n。此例n=7,故取m=13就已經(jīng)足夠，得到的每個(gè)元素的哈希地址為：h(18)=18mod13=5h(75)=75mod13=10h(60)=60mod13=8h(43)=43mod13=4h(90)=90mod13=12h(46)=46mod13=7根據(jù)哈希地址，依次把元素存儲(chǔ)到哈希表H(0~m-1)中的效果如下：當(dāng)然，這是一個(gè)比較理想的情況，假如要再往表中插入第8個(gè)元素30,h(30)=30mod13=4，會(huì)發(fā)現(xiàn)H[4]已經(jīng)存放了43,此時(shí)就發(fā)生了沖突，那么就可以從H[4]往后按順序找一個(gè)空位置存放30,即可以把它插入到H[6]中。0123456789101112

54

4318

4660

75

90H例2:分身數(shù)對(duì)。(sumx,1s,256MB)問(wèn)題描述：給出n個(gè)不同的正整數(shù)a[1]~a[n],它們的值在1~1000000之間。再給定一個(gè)整數(shù)x，編程計(jì)算這樣的數(shù)對(duì)個(gè)數(shù)(a[i],a[j]),1<=i<j<=n并且a[i]+a[j]=x。輸入格式：第1行1個(gè)正整數(shù)n,1<=n<=100000。第2行n個(gè)正整數(shù),表示元素a[1]~a[n],每?jī)蓚€(gè)數(shù)之間用一個(gè)空格分隔。第3行1個(gè)正整數(shù)x，1<=x<=2000000。輸出格式：1行，1個(gè)整數(shù)，表示這樣的數(shù)對(duì)個(gè)數(shù)。輸入樣例：951271091231113輸出樣例：3樣例說(shuō)明：不同的和為13的數(shù)對(duì)是(12,1),(10,3)和(2,11)共3對(duì)。問(wèn)題分析：如果使用雙重循環(huán)來(lái)查找，本題是要超時(shí)的。用哈希表來(lái)處理，定義a[x]代表x這個(gè)數(shù)在數(shù)列中是否存在，1代表存在，0代表不存在，那么只需要掃描1~x/2，若數(shù)字存在，那么只需要查看x減去這個(gè)數(shù)的結(jié)果在數(shù)列里是否存在，若存在就增加一對(duì)數(shù)列。例3：明明的隨機(jī)數(shù)(noip2016普及組復(fù)賽,randam,1s,256MB)問(wèn)題描述:明明想在學(xué)校中請(qǐng)一些同學(xué)一起做一項(xiàng)問(wèn)卷調(diào)查，為了實(shí)驗(yàn)的客觀性，他先用計(jì)算機(jī)生成了N個(gè)1到1000之間的隨機(jī)整數(shù)（N≤100），對(duì)于其中重復(fù)的數(shù)字，只保留一個(gè)，把其余相同的數(shù)去掉，不同的數(shù)對(duì)應(yīng)著不同的學(xué)生的學(xué)號(hào)。然后再把這些數(shù)從小到大排序，按照排好的順序去找同學(xué)做調(diào)查。請(qǐng)你協(xié)助明明完成“去重”與“排序”的工作。輸入格式輸入有2行，第1行為1個(gè)正整數(shù)，表示所生成的隨機(jī)數(shù)的個(gè)數(shù)N。第2行有N個(gè)用空格隔開(kāi)的正整數(shù)，為所產(chǎn)生的隨機(jī)數(shù)。輸出格式輸出也是2行，第1行為1個(gè)正整數(shù)M，表示不相同的隨機(jī)數(shù)的個(gè)數(shù)。第2行為M個(gè)用空格隔開(kāi)的正整數(shù)，為從小到大排好序的不相同的隨機(jī)數(shù)。樣例輸入102040326740208930040015樣例輸出8152032406789300400問(wèn)題分析：因?yàn)閚<=100，可以使用冒泡排序、插入排序、選擇排序等時(shí)間復(fù)雜度為O(n2)的算法實(shí)現(xiàn)，這樣做不會(huì)超時(shí)。實(shí)際上，對(duì)于產(chǎn)生的隨機(jī)數(shù)a[i]，由于0<a[i]<1001,且a[i]為整數(shù)。所以，可以使用哈希表a[i]=0表示沒(méi)有i這個(gè)數(shù)，a[i]=1表示有i這個(gè)數(shù)。那么，每次讀一個(gè)i，把a(bǔ)[i]賦值為1,讀完所有數(shù)據(jù)后，只要再掃描一下這個(gè)數(shù)組就可完成統(tǒng)計(jì)和排序輸出任務(wù)。這種方法類似“桶排序”原理。練習(xí)1：整數(shù)集合(sumsets,1s,256MB)問(wèn)題描述：給定一個(gè)整數(shù)集合s，請(qǐng)你尋找一個(gè)最大的d，使得a+b+c=d，并且a、b、c、d都是集合中的元素。輸入格式：若干集合s。對(duì)于每個(gè)集合s的第1行包含1個(gè)整數(shù)n,1<=n<=1000，表示集合中元素的個(gè)數(shù)。隨后有n行，每一行一個(gè)整數(shù)，表示集合s中的元素，每個(gè)整數(shù)的范圍是[－536870912,536870911].輸入的最后一行包含一個(gè)0。輸出格式：對(duì)于每個(gè)集合s，輸出一行一個(gè)整數(shù)d，或者“NoSolution”表示無(wú)解。輸入樣例：523571252166425610240輸出樣例：12NoSolution練習(xí)2：生日(birthday,1s,256MB)問(wèn)題描述：多多今天很高興，因?yàn)樗暮门笥烟O(píng)果要過(guò)生日了。由于今天多多得到了兩張價(jià)值不菲的SHOP購(gòu)物券，所以他決定買N件禮物送給蘋(píng)果。一個(gè)下午過(guò)去了，多多選好了N件禮物，并且它們的價(jià)格之和恰好為兩張購(gòu)物券的面額這和。當(dāng)多多被自己的聰明所折服，高興地去結(jié)賬時(shí)，他突然發(fā)現(xiàn)SHOP對(duì)購(gòu)物券的使用有非常嚴(yán)格的規(guī)定：一次只允許使用一張，不找零，不與現(xiàn)金混用。多多身上根本沒(méi)有現(xiàn)金，并且他不愿意放棄挑選好的禮物。這就意味著，他只能通過(guò)這兩張購(gòu)物券結(jié)賬，而且每一張購(gòu)物券所購(gòu)買的物品總價(jià)格，必須精確地等于這張購(gòu)物券的面額。怎樣才能順利地買回這N件禮物送給蘋(píng)果呢？本題的任務(wù)就是幫助多多確定是否存在一個(gè)購(gòu)買方案。已知其中一張購(gòu)物券的面額以及所有商品的價(jià)格，只需要確定能否找到一種方案使得選出來(lái)的物品的價(jià)格總和正好是這張購(gòu)物券的面額即可。輸入格式：有多組測(cè)試數(shù)據(jù)。每組數(shù)據(jù)的第一行為兩個(gè)整數(shù)N和M，分別表示多多一共挑選了N個(gè)物品送給蘋(píng)果以及多多的一張購(gòu)物券的面額為M。接下來(lái)的一行有N個(gè)用空格隔開(kāi)的正整數(shù)，第i個(gè)數(shù)表示第i個(gè)物品的價(jià)格。輸出格式：包含若干行，每行一個(gè)單詞“YES”或者“NO”，分別代表存在一個(gè)購(gòu)買方案或不存在一個(gè)購(gòu)買方案。輸入樣例：102000100010020030040050070060090080010229010001002