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

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

 

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

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

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

這里有個小技巧，就是標記當前狀態(tài)是否已經(jīng)在隊列中，防止隊列中出現(xiàn)重復(fù)狀態(tài)。具體實現(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

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

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

1.在做多邊形切割時，常常先加一個框，框不宜加的過大，比如eps=1e-8，那么框最大不要超過1e7，保證他們的精度之和能夠保證在15位之內(nèi)。這樣可以防止在運算過程中出現(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

題意：給你一個斜面，再給一個凸多邊形的石頭，讓石頭從高出放下，沿著斜面滾動，問石頭重心最后的位置。因為摩擦力很大，石頭不能滑動，只能轉(zhuǎn)動。（還有很多細節(jié)，具體見原題）

      首先，這里要確定什么時候石頭算穩(wěn)定了，可以找到石頭和斜面相交的兩個點，一個是相對石頭的最左點A，一個是相對石頭的最右點B，這樣如果石頭要向左轉(zhuǎn)動，必是繞著A轉(zhuǎn)；要向右轉(zhuǎn)動，必是繞著B轉(zhuǎn)。這里有個問題，如果A，B的橫坐標相同，那么A取最低的那個，B取最高的那個。
     
      找到A,B兩點之后，如果重心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再次碰到斜面。我們要求出這個theta的值。這里可以采用二分theta的方法來解決，對于某個確定的角度theta1，直接模擬轉(zhuǎn)動theta1角度。看是否超出斜面的范圍，如果是，說明theta1大了，否則說明theta1小了。

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

1. 在檢查的時候，要檢查石頭上是否存在一點是否在斜面的下側(cè)，這里很容易忽視那個支點，如果把支點也一并去檢查，很可能因為精度的關(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)的判定如果在斜面下方，實際上是角度小了，盡管絕對值是大了。還有一種寫法是枚舉［0，PI］，在check函數(shù)里再判斷是向左轉(zhuǎn)，還是向右轉(zhuǎn)。這樣不容易寫錯。

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