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

正規(guī)式與編輯距離都是常見知識，如果不熟悉請見原題^[1]

 

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

一時(shí)之間想不起用什么來表示正規(guī)式，后來看到解題報(bào)告 ^[2] 才有恍然大悟的感覺，用一個(gè)NFA^[3]來表示正規(guī)式（編譯原理課上學(xué)過的，還是重點(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à)。對于當(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]，寫的非常優(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

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

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

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

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

旋轉(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è)凸多邊形的石頭，讓石頭從高出放下，沿著斜面滾動，問石頭重心最后的位置。因?yàn)槟Σ亮艽螅^不能滑動，只能轉(zhuǎn)動。（還有很多細(xì)節(jié)，具體見原題）

      首先，這里要確定什么時(shí)候石頭算穩(wěn)定了，可以找到石頭和斜面相交的兩個(gè)點(diǎn)，一個(gè)是相對石頭的最左點(diǎn)A，一個(gè)是相對石頭的最右點(diǎn)B，這樣如果石頭要向左轉(zhuǎn)動，必是繞著A轉(zhuǎn)；要向右轉(zhuǎn)動，必是繞著B轉(zhuǎn)。這里有個(gè)問題，如果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)。
     
      其次，要知道石頭如果開始轉(zhuǎn)動，不論向左向右，轉(zhuǎn)動多少角度會再次碰到斜面。假設(shè)轉(zhuǎn)動theta再次碰到斜面。我們要求出這個(gè)theta的值。這里可以采用二分theta的方法來解決，對于某個(gè)確定的角度theta1，直接模擬轉(zhuǎn)動theta1角度。看是否超出斜面的范圍，如果是，說明theta1大了，否則說明theta1小了。

      二分的實(shí)現(xiàn)上我覺得還是有很多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é)果寫在一起就出問題了，向左轉(zhuǎn)的判定如果在斜面下方，那么是角度大了，向右轉(zhuǎn)的判定如果在斜面下方，實(shí)際上是角度小了，盡管絕對值是大了。還有一種寫法是枚舉［0，PI］，在check函數(shù)里再判斷是向左轉(zhuǎn)，還是向右轉(zhuǎn)。這樣不容易寫錯(cuò)。

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