【正文】 t:=meml[$40:$6C]t。 out。 sort(1,a)。 begin t:=meml[$40:$6C]。 close(fin)。 procedure out。 end。 for i:=1 to b do begin read(fin,x)。 begin read(fin,b)。 if (da[p]=x)or(da[e]=x)or(da[mid]=x) then member:=true else member:=false。 end。 end else begin p:=mid。 if xda[mid] then begin e:=mid。 exit。 mid:=(p+e) div 2。 begin p:=1。 function member(x:longint):boolean。 procedure main。 end。 sort(m,p)。 end。 end。 end else begin if Ij then locate:=j else locate:=j1。 da[i]:=da[j]。 until da[j]=value。 until da[i]=value。 j:=n+1。 begin value:=da[(m+n) div 2]。 function locate:longint。 procedure sort(m,n:longint)。 for i:=1 to a do read(fin,da[i])。 reset(fin)。39。 var i:longint。 t:real。 da:array[1..max]of longint。 const max=16101。 writeln(t/:0:8)。 end。 main。 begin t:=meml[$40:$6C]。 close(fin)。 procedure out。 end。 for i:=1 to b do begin read(fin,shu)。 begin read(fin,b)。 procedure main。 end。 for i:=1 to a do begin read(fin,shu)。 fillchar(index,sizeof(index),0)。 rewrite(fout)。)。 assign(fout,39。39。 var shu,i:longint。 end。 function member(t:longint):boolean。 begin index[locate(t)]:=t。 end。 while (index[tmp]0)and(index[tmp]t) do tmp:=(tmp+1) mod max。 var tmp:longint。 t:real。 a,b,s,j:longint。 const max=15889。其中只有 SGOI8 Flowers 的程序是網(wǎng)上提供的標(biāo)程，其余的都是我自己寫的，并且已經(jīng)通過所有測試數(shù)據(jù)。 5. 總結(jié) 本文介紹了有關(guān)哈希表方面的內(nèi)容，分析了它的特點和優(yōu)點，指出了應(yīng)用需要注意的問題，并且重點舉了幾個例子來說明它在競賽中的應(yīng)用 。雖然都只是很小的變化，但是卻給問題的解決帶來了不小的方便。所以，不論題目的表面看起來如何，只要本質(zhì)是需要 高效的數(shù)據(jù)檢索，哈希表通常就是最好的選擇！ 另外，這兩個例子都在原來哈希表的基礎(chǔ)上作了一些變化。 當(dāng)然肯定會有更好的哈希函數(shù)的。其實讓 r[b],r[c],r[d] 組成 n 進(jìn)制數(shù)就完全能夠達(dá)到目的了，加入了素數(shù)不僅是小規(guī)模數(shù)據(jù)計算浪費時間，對大數(shù)據(jù)最后結(jié)果的分布平均也沒有起到比 n 進(jìn)制數(shù)更多的作用。 end。 while (e[a,(t+i)mod p,1]0)and(e[a,(t+i)mod p,1]r[b]) do if (e[a,(t+i)mod p,2]r[c])or(e[a,(t+i)mod p,3]r[d]) then inc(i)。 {用 3 堵墻的值任意乘大素數(shù)相加再取余數(shù)，使得結(jié)果分布比較隨機，也就比較均勻 } t:=t mod p。 i:integer。如果有多個節(jié)點都是相同的，擇取其中最大的（這一點不需要特殊的操作，只要在處理節(jié)點的時候注意就行了） } 至于哈希函數(shù)，最開始我是隨意的寫了一個（因為越是隨意的，就越是隨機的?。?，定位函數(shù)是這樣的： function locate(var a,b,c,d:longint):longint。 {0..2 代表共有 3 種顏色， 0..p1 是哈希函數(shù)的值域，而 1..4 中的 1..3 表示三堵墻連接到那個房間， 4 表示這個單元存儲的是哪個節(jié)點 } r:array[1..maxn]of longint。然而，這里面需要對哈希表作更大的改進(jìn)：首先每個房間只能是 3 種顏色之一，因此針對每種顏色分別建立哈希表，可以使哈希函數(shù)的自變量減少一個；其次還需要紀(jì)錄每個不重復(fù)的房間每 堵墻都通向哪個房間，還有哪些房間是重復(fù)的。 所以，我們只需要記錄下每個房間的情況和已經(jīng)被確定相同的房間，然后挨個比較即可。通過對樣例的分析，可以看出 這樣的房間是重復(fù)的：如果兩個房間 i 和 j （ 1=i,j =n1），他們的顏色相同，而且第 k (k=1,2,3) 堵墻通向的房間或者相同、或者重復(fù)。 分析： 題目的意思是給出這個迷宮的地圖，去掉重復(fù)出現(xiàn)的房間，找出這個迷宮的最少房間數(shù)目。字母代表了房間的顏色（ C紅， Z綠， N藍(lán)），第 i(i=1,2,3)個數(shù)是第 i 個井通往的房間號。接下的 n1 行描述迷宮的房間（除了龍宮）和井。 輸入： 第一行有一個整數(shù) n,2=n=6000，房間數(shù)（包括龍宮）。這一列數(shù)稱為一個旅行計劃。迷宮中的所有通路走向坐落在最底部的龍宮。從一個房間到另一間只有一種方式：從上面房間的井里跳到（不一定豎直地）井底的房間。兩個相同顏色的房間看起來相似而不可區(qū)分。迷宮的入口在山頂。 {僅僅這一條語句，就可以記錄下來 S 出現(xiàn)了幾次 } end。 e[posi,1]:=x。 var posi:longint。 Var e:array[0..max1,1..2]of longint。至于哈希函數(shù)不是問題，還是把 S 的值作為關(guān)鍵字使用除余法即可。想到了這里，問題就是如何迅速的找到某個 S 是否曾經(jīng)出現(xiàn)過，以及出現(xiàn)過了多少次，于是又變成了 某 個元素是否在給定集合中 這個問題。這就啟示我們能否僅僅通過枚舉 3 個未知數(shù)的值來找到答案呢？如果這樣，前一半式子的值 S 可以確定，這時只要枚舉后 3 個數(shù)的值，檢查他們的和是否等于 S 即可。因此我們需要尋找更好的方法，自然想到能否縮小枚舉的范圍呢？但 是發(fā)現(xiàn)這樣也有很大的困難。這樣就不能利用數(shù)學(xué)方法直接求出解的個數(shù)，而且注意到解的范圍最多 150 個數(shù)，因此恐怕只能使用枚舉法了。 這個是 NOI 2020 的第二試中的《方程的解數(shù)》。 約束條件 1≤ n≤ 6； 1≤ M≤ 150； 方程的整數(shù)解的個數(shù)小于 。且方程中的所有數(shù)均為整數(shù)。下面我們看兩個需要在哈希表基礎(chǔ)上作一些變化的例子。至于廣度優(yōu)先搜索中的判重更是直接利用了哈希表的特點。 小結(jié) 從這兩個例子可以發(fā)現(xiàn)，對于字符串的查找，哈希表雖然不是最好的方法，但是每個字符都有 天生 的 ASCII 碼，在設(shè)計哈希函數(shù)的時候可以直接利用。那么這個哈希函數(shù)如何設(shè)計呢？注意到 19 個格子組成 6 邊形是有順序的，而且每一個格子只有 3種可能情況，那么用 3 進(jìn)制 19 位數(shù)最大 3^201=3486784400 用 Cardinal 完全可以承受。正 6 邊形共有 19 個格子可以用來放花，而且根據(jù)最后一句限定條件，至多只能存在 C(2,19) * C(5,17) = 1058148 種狀態(tài)，用搜索完全可行。限定一個花壇里擺放的不同種類的花不超過 3種，對于任意兩種花，數(shù)量多的花的盆數(shù)至少是數(shù)量少的花的 2 倍 。來看下面的例子： 轉(zhuǎn)花盆 題意描述 : 給定兩個正 6 邊形的花壇，要求求出從第一個變化到第二個的最小操作次數(shù)以及操作方式。 在廣度優(yōu)先搜索中應(yīng)用的例子 在廣度優(yōu)先搜索中，一個通用而且有效的剪枝就是在拓展節(jié)點之前先判重。 end。 {取第一位和后兩位 } end else for i:=1 to 3 do tmp:=tmp*27+ord(s[1])64。 {用來記錄 27 進(jìn)制數(shù)的值 } if length(s)1 then begin tmp:=tmp*27+ord(s[1])64。 var i,tmp:longint。這樣哈希函數(shù)就設(shè)計出來了！ 不過，由于可能出現(xiàn)只有 1 位的字符串，在寫函數(shù)代碼的時候需要特殊考慮；大素數(shù)選取 13883 。由于給定的字符串的長度從 112 都有可能，為了容易實現(xiàn)，選取最開始的 1 個字符，和最末尾的 2 個字符。所以這個問題需要的還是 某個元素是否在已知集合中？ 由于給出的 姓名 都是字符串，因此我們可以利用字符的 ASCII 碼。（這個是 USACO Training Gate 的一道題。其中為每個字符串編寫密碼，編寫的方式是對于 n 位字符串，給定一個 n 位數(shù)，大寫字母與數(shù)字的對應(yīng)方式按照電話鍵盤的方式： 2: A,B,C 5: J,K,L 8: T,U,V 3: D,E,F 6: M,N,O 9: W,X,Y 4: G,H,I 7: P,R,S 題目給出一個 112 位的數(shù)，找出在字典中出現(xiàn)且密碼是這個數(shù)的所有字符串。下面，我們看幾個例子，看看這些原則是如何體現(xiàn)的。往往一些簡單的改進(jìn)就 可以帶來巨大的方便。 另外，使用哈希表并不是記住了前面的基本操作就能以不變應(yīng)萬變的。 綜上所述，設(shè)計一個好的哈希函數(shù)是很關(guān)鍵的。然而，這樣做顯然不值得，因為這樣的函數(shù)設(shè)計很浪費時間而且編碼一定很復(fù)雜，與其花費這么大的精力去設(shè)計函數(shù)，還不如用一個雖然沖突多一些但是編