求兩個(gè)正規(guī)式之間的編輯距離

正規(guī)式與編輯距離都是常見(jiàn)知識(shí)，如果不熟悉請(qǐng)見(jiàn)原題^[1]

 

兩個(gè)字符串之間的編輯距離的經(jīng)典解法是動(dòng)態(tài)規(guī)劃。然而正規(guī)式可能包含無(wú)窮多個(gè)字符串。 不好將它轉(zhuǎn)化到兩字符串的編輯距離上。另外一個(gè)問(wèn)題，首先要有一種能夠識(shí)別正規(guī)式的方法，就像進(jìn)行表達(dá)式計(jì)算時(shí)，用遞歸下降方法來(lái)識(shí)別就很順手。

一時(shí)之間想不起用什么來(lái)表示正規(guī)式，后來(lái)看到解題報(bào)告 ^[2] 才有恍然大悟的感覺(jué)，用一個(gè)NFA^[3]來(lái)表示正規(guī)式（編譯原理課上學(xué)過(guò)的，還是重點(diǎn)）。這樣狀態(tài)非常的清晰。

首先將正規(guī)式轉(zhuǎn)換成NFA的形式，這樣兩個(gè)正規(guī)式，就變成了兩個(gè)NFA。設(shè)<x , y>表示當(dāng)前匹配到第一個(gè)NFA的x狀態(tài)，第二個(gè)NFA的y狀態(tài)所消耗的當(dāng)前最少代價(jià)。對(duì)于當(dāng)前的狀態(tài)<s1, s2>尋找他所有的后繼<t1, t2>，如果發(fā)現(xiàn)能夠更新后繼<t1, t2>,那么更新它，并且將它入隊(duì)，用于更新其他的狀態(tài)。當(dāng)隊(duì)列里空了時(shí)候，那么就求到了最小編輯距離。

這里有個(gè)小技巧，就是標(biāo)記當(dāng)前狀態(tài)是否已經(jīng)在隊(duì)列中，防止隊(duì)列中出現(xiàn)重復(fù)狀態(tài)。具體實(shí)現(xiàn)可以參考UESTC_Melody的代碼^[4]，寫(xiě)的非常優(yōu)美。

 

引用

[1]http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=5109

[2] http://icpc.amrita.ac.in/2010/images/solution_logic.pdf

[3] http://en.wikipedia.org/wiki/Nondeterministic_finite_state_machine

[4] http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=56951

OpenMP官方推薦的一本教程。
下載地址為http://www.ppurl.com/2008/12/using-openmp-portable-shared-memory-parallel-programming.html

看這本書(shū)的目的是想了解如何寫(xiě)一個(gè)并行程序。只有300來(lái)頁(yè)，給自己一個(gè)星期大概瀏覽一遍，對(duì)于這種語(yǔ)言類(lèi)的書(shū)一個(gè)星期就夠了。一天50頁(yè)。

     摘要: 福州賽區(qū)總結(jié)  閱讀全文

1.在做多邊形切割時(shí)，常常先加一個(gè)框，框不宜加的過(guò)大，比如eps=1e-8，那么框最大不要超過(guò)1e7，保證他們的精度之和能夠保證在15位之內(nèi)。這樣可以防止在運(yùn)算過(guò)程中出現(xiàn)舍入誤差。

2 double的范圍是 -1.7*10^(-308) ~ 1.7 * 10^308。超過(guò)此范圍，可以通過(guò)儲(chǔ)存他們的指數(shù)來(lái)保證精度。

旋轉(zhuǎn)

http://acm.pku.edu.cn/JudgeOnline/problem?id=1259
the picnic

POJ2823

hdu3401

http://202.120.80.191/state.php?problemid=1016
best cow fence

Deformed Wheel

題意：給你一個(gè)斜面，再給一個(gè)凸多邊形的石頭，讓石頭從高出放下，沿著斜面滾動(dòng)，問(wèn)石頭重心最后的位置。因?yàn)槟Σ亮艽螅^不能滑動(dòng)，只能轉(zhuǎn)動(dòng)。（還有很多細(xì)節(jié)，具體見(jiàn)原題）

      首先，這里要確定什么時(shí)候石頭算穩(wěn)定了，可以找到石頭和斜面相交的兩個(gè)點(diǎn)，一個(gè)是相對(duì)石頭的最左點(diǎn)A，一個(gè)是相對(duì)石頭的最右點(diǎn)B，這樣如果石頭要向左轉(zhuǎn)動(dòng)，必是繞著A轉(zhuǎn)；要向右轉(zhuǎn)動(dòng)，必是繞著B(niǎo)轉(zhuǎn)。這里有個(gè)問(wèn)題，如果A，B的橫坐標(biāo)相同，那么A取最低的那個(gè)，B取最高的那個(gè)。
     
      找到A,B兩點(diǎn)之后，如果重心G 有 A.x<=G.x <= B.x 那么他是穩(wěn)定的，如果G.x < A.x 那么他是向左轉(zhuǎn)，如果G.x > B.x那么他是向右轉(zhuǎn)。
     
      其次，要知道石頭如果開(kāi)始轉(zhuǎn)動(dòng)，不論向左向右，轉(zhuǎn)動(dòng)多少角度會(huì)再次碰到斜面。假設(shè)轉(zhuǎn)動(dòng)theta再次碰到斜面。我們要求出這個(gè)theta的值。這里可以采用二分theta的方法來(lái)解決，對(duì)于某個(gè)確定的角度theta1，直接模擬轉(zhuǎn)動(dòng)theta1角度。看是否超出斜面的范圍，如果是，說(shuō)明theta1大了，否則說(shuō)明theta1小了。

      二分的實(shí)現(xiàn)上我覺(jué)得還是有很多trick的，比如

1. 在檢查的時(shí)候，要檢查石頭上是否存在一點(diǎn)是否在斜面的下側(cè)，這里很容易忽視那個(gè)支點(diǎn)，如果把支點(diǎn)也一并去檢查，很可能因?yàn)榫鹊年P(guān)系判他在斜面的下方，結(jié)果check函數(shù)一直都是不合法。
2. 向左轉(zhuǎn)和向右轉(zhuǎn)的處理上，向左轉(zhuǎn)我采用的是二分［0，PI］轉(zhuǎn)角，向右轉(zhuǎn)我則是二分［-PI， 0］轉(zhuǎn)角，結(jié)果寫(xiě)在一起就出問(wèn)題了，向左轉(zhuǎn)的判定如果在斜面下方，那么是角度大了，向右轉(zhuǎn)的判定如果在斜面下方，實(shí)際上是角度小了，盡管絕對(duì)值是大了。還有一種寫(xiě)法是枚舉［0，PI］，在check函數(shù)里再判斷是向左轉(zhuǎn)，還是向右轉(zhuǎn)。這樣不容易寫(xiě)錯(cuò)。

http://acm.pku.edu.cn/JudgeOnline/problem?id=2064