Lcs 改用 Lis 的作法

取自http://chieh-min.blogspot.com/2009/01/lcs-lis.html
把他轉成LIS 是因為要追求O(nlogn)的速度

作法：
設有序列A，B。
記序列A中各個元素在B 中的位子(降序排列)
然後按在A中的位置依序列出
出按後求A的最長遞增子序列

例如：有A={a,b,a,c,x}，B={b,a,a,b,c,a}
則有 a = {6,3,2} , b = {4,1} , c = {5} , x = / ;（注意降序排列）
然後按A中的次序排出
{ a(6,3,2) , b(4,1) , a(6,3,2) , c(5) , x( ) } = { 6,3,2,4,1,6,3,2,5 }；
對此序列求最長遞增子序列即可~~

各位acmer學累的時候不妨來看看

從大陸的某個論壇引用的，所以有一些不太一樣的詞請見諒。
1.題庫與網站資源
題庫－在線提交系統（Online Judge）簡介
下面是幾個比較大的在線提交系統（Online Judge）裡面有大量歷年的競賽題目，一般都是註冊一個ID，然後用自己熟悉的語言（如Pascal/C/C++/Java）寫好原始碼上傳即可，通常 網站會即時返回信息告訴你是否正確。 系統裡有一套標準的輸入輸出數據（對外保密，而且通常數據很多很怪），你的程式的輸出和標準輸出完全符合即可。
常見的返回信息有AC（Accepted，通過）、WA（Wrong Answer，輸出有錯誤）、TLE（Time Limit Exceeded，超時）、MLE（Memory Limit Exceeded，內存溢出）、RE（Runtime Error，發生實時錯誤）等，只有AC了才算做對一題。
這裡只是一個簡要介紹，請大家在做題時先看看各網站上的FAQ，Enjoy it!

北京大學Online Judge（POJ)
<http://acm.pku.edu.cn/JudgeOnline/>
建立較晚，但題目加得很快，現在題數和ZOJ不相上下，特點是舉行在線比賽比較多，數據比ZOJ上的要弱，有時候同樣的題同樣的程序，在ZOJ上WA，在 POJ上就能AC。 不過感覺比pku的題目要難很多。這個題庫的一大特點就是Online Judge功能強大，其實pku現在已經是中國最好的ACM網站。

浙江大學Online Judge（ZOJ）
<http://acm.zju.edu.cn>
國內最早也是最有名氣的OJ，有很多高手在上面做題。打開速度快。

西班牙Valladolid大學Online Judge（UVA）
<http://acm.uva.es/>
世界上最大最有名的OJ，題目巨多而且巨雜，數據也很刁鑽，全世界的頂尖高手都在上面。據說如果你能在UVA上AC一千道題以上，就儘管向IBM、微軟什麼的發簡歷吧，絕對不會讓你失望的。

俄羅斯Ural立大學Online Judge（URAL）
<http://acm.timus.ru/>
也是一個老牌的OJ，題目不多，但題題經典，我在高中的時候就在這上面做題的。

俄羅斯薩拉托夫國立大學(Saratov State University)(SGU)
<http://acm.sgu.ru/>
SGU 是俄羅斯薩拉托夫國立大學(Saratov State University)用於培養ACM選手的訓練網站。 這個網站的建成時期較晚，但隨著比賽的舉行以及新題目的加入，這個題庫的題目也日漸豐富。這個題庫的一大特點就是Online Judge功能強大，它不僅使你避開了多數據處理的繁瑣操作，還能告訴你程序錯在了第幾個數據。這一點雖然與ACM的Judge有些出入，但是卻方便了調 試程序。 與UVA相比，這裡的題目在時間空間上要求都比較嚴格，而且更多的考察選手對算法的掌握情況，所以特別推薦衝擊NOI的選手也來做一做。

UsacoGate Online Judge（USACO）
<http://ace.delos.com/usacogate>
全美計算機奧林匹克競賽（USACO）的訓練網站，特點是做完一關才能繼續往下做,與前面的OJ不同的是測試數據可以看到，並且做對後可以看標準解答，所 以如果大家剛開始的時候在上面那些OJ上總WA卻找不到原因的話，可以試著來這裡做做，看看測試數據一般是從什麼地方陰你的。

網站資源：
http://www.608088.com acm很不錯的網站（資料很多）,教育網也可以很快打開.

比如:
acm算法介紹算法模版 http://www.608088.com/category-5-1.html
各大OJ解題報告 http://www.608088.com/category-4-1.html

注意：還有一種非常重要的網站資源───用百度搜索你在oj上不懂的題目（例如：pku 1015），就可以看到了。也可以直接打「ACM」等等。有點看運氣，但是其實也有搜索技巧在裡面。

2 學習資料說明
入門其實有兩種方法：
1自己看競賽書，看別人的程序等等。
2上題庫（如：pku和zju）做題。
第一種可以較為系統的學到東西，但是時間久了就會無聊，而且長久實踐不足，編程能力永遠得不到真正的提高。
第二種雖然看著自己AC很興奮，看著自己的帳號排名提高很開心，但是學習不繫統，對較深的知識學習不足，總停留在做簡單題的份上。
最好的方法就是兩種方法相結合。作為入門者還是要以多看簡單競賽書多看題目和程序為主（例如：《信息奧賽輔導教材》、《基本算法稿》、《06暑假培訓》和 《基本算法C＋＋》，都在「初級入門學習」文件夾中），這個學習時間佔70％，同時也要有30％的時間上題庫做題。 畢竟理論學習要和實踐相結合。

3 一些話
真的很不確定這些資料可以起到多大的作用，但是唯一確定的就是自己當年如果有這些東西，那將是多麼～～～事實上這些資料確實對過去新加入的ACMer有很大的幫助。願它對每個看到這份資料的人都能充分起到作用！
ACM是什麼，ACM學習過程中會有什麼感觸。得到不同結果的人會說不同的話。但是唯一一樣的就是：無悔！
關於ACM的介紹還有入門的東西可以在「初級入門學習」文件夾中的「ACM入門進階.rar」找到部分的答案，在百度和google搜索也可以。這裡就 不在多說。大學中可以學的東西很多很廣，計算機專業包括的東西也一樣。具體怎麼樣，大家只要走進西門兩家書店便一目瞭然。如果說程序語言是計算機專業的基 礎，那麼ACM充當這個基礎的角色一點都不過份。ACM中可以學到的是對程序設計語言的深入理解和應用，同時培養出來的是建模和轉化模型的能力，也是解決 問題的能力。這些是優秀計算機人應有的基本。

有人說：「如果再來一次大學，我會在大一大二瘋狂搞ACM，參加省賽，參加區賽，參加世界賽，然後大三開始做項目～～」問題是你參加了世界賽就算 不拿獎你也有資格可以去微軟和google了。ACM是大學生四大競賽之首，沒有水分，完全考平時做題思考積累的實力拚搏。 這幾年國內ACM的發展太快，難度增大，牛人更牛更多，競爭更加悲慘。華師在兩年前參加ACM的人不到10個，現在不下200人。 華師的發展只是全國其他高校延後了幾年時間的一個縮影。但是這是社會進步帶來的我們不得不面對的結果。 例如前面幾屆的師範專業老師就會有到了學校要面對比他厲害十倍的學生的尷尬場面。非師專業也有面試網易騰訊等公司時因為寫不出算法而與高新offer無緣 的情況。這裡更想說的是ACM的好處，而不是讓大家在壓力下不得不學它，要知道許許多多的計算機領域幾乎與ACM無關（例如網頁製作，flash等）以上 這些話是回答那些說ACM沒用的人的，不包括對其充滿熱情的人。
其實ACM的公平不但體現在競賽現場上（通過測試數據就算贏，不管你程序怎麼寫），而且還體現在學習的過程上。這點需要詳細說明一下。
1：學習的方法幾乎一樣入了門之後大家都是在題庫上拚命做題。 全世界沒有一個人例外。
2：自學是唯一的方法。 ACM不是看懂的，也不是聽懂的，而是練懂的。 懂的唯一方法就是要多練多寫。 在賽場上無數悔恨的根源就是平時訓練做題時對沒有完全理解的知識抱有幻想。 台上一分鍾台下十年功！
3：大家平時的生活都是：
<http://acm.pku.edu.cn/JudgeOnline/> 、 <http://acm.zju.edu.cn/>、
<http://acm.uva.es/>。

Fd: Why do you want to give up?

今天我和老師在討論說要去3月資訊奧林匹亞初試的名單
老師說可能就依照這次馬拉松的成績來選
然後我和家齊基本上是保障名額
然後帶一個一年級的去 至於人選就由我來挑選
不過 我看家齊這次比賽感覺很不認真 都沒在用心
所以就騙他說 老師說「你這次考太差了 說不定不給你去比了」
沒想到他居然說「我本來就不想再去比了」
我「....為什麼........」
家齊「每次去都解不大出來...」
難道是之前學科能力競賽沒得名讓你喪失動力？
其實說真的 我一開始寫程式的動力 就是因為不想輸給你
每次看到你ACM的題數追了上來 就更賣力的練習和解題目
去年校內馬拉松 也是不想輸給你才奮力解完20題（去年20題對我來說還算是一個不小的挑戰）
而在過程中 我也越寫越有心得 越寫越有興趣
真的是找到了我自己的興趣
之前 學科能力競賽彰雲嘉區的第一名 對我自己是一個相當大的激勵
而到了全國賽和NPSC的慘敗 更讓我瞭解到應該加強的目標在哪
而你 或許沒有經歷到這些 因為得不到肯定而有點灰心
但 我相信寫程式應該不只是為了比賽吧
更重要的是 自己的執著
不好 可以再努力
怕題目解不出來
那就繼續學 繼續練
或許就被我們不小心矇進了選訓營也說不定阿
就算可能進不了 那我們也看到了全國頂尖的高手是如何解題的阿
而且 不去試試看怎麼知道能不能成功呢？
總之 如果你對寫程式沒什麼興趣了 那我也沒什麼話好說了
反之 我還是希望你能繼續當我的對手
督促我們一起進步.....OK?
可惡...早知道第四題就讓你慢慢去想= =

老實說 我在聽到他不想去的時候
還蠻震驚的
可是 淞任居然沒進 有一點點失望

作啥事都要有人一起競爭
才做的快
想當初 你們兩個跟我說你們有先看時
我就在暗中觀察
你們之間的競爭應該算是我把你們湊成一對的
可是 從注意到你們的差距越來越明顯時
我已經無法介入了
他心中或許已經有了無法彌平的自卑吧
我想 你可以去找一些你們兩個人都沒解過的題目
印下來一起討論 像當初奇怪的河內塔
和這一次的旋轉矩形
你們不應該悶著各自解

你們不像我
當初沒有人可以跟我討論
所以我現在注意一年級學弟時
也刻意弄了一個小團體
就是 皓銓 淞任 豪傑
希望他們遇到題目時可以一起討論
所以我通常都是一起教過來敎

你在跟家齊討論題目時
耐心要多一點 就算你已經想通了
你也要把他引導到懂
就像當初
你上來5樓問我旋轉矩形的時候一樣
我已經懂了 可是我還是會說到讓你懂為止

話說回來
你難得上來問我題目時
心中難得的感動一下
只不過你平常時對我的那一種敷衍
就真的讓我受不了了