#
Astar隊成立已經一個多月了，還記得我們集體參加的第一場比賽是8.8號南航的官方練習賽，由于正值暑假期間，各大OJ都沒有正式的比賽，所以這個比賽吸引了眾多的大牛參加。我認為這次比賽對于我們隊的意義倒不是比賽的結果，而是通過這場比賽我們有了初步的磨合，隊員與隊員之間開始達成默契。最后通過幾個小時的努力，我們AC了6題，排名大概在15左右。這是我們隊參加的第一次正式比賽^_^。
當時是計劃暑假至少參加兩次練習比賽的，第二次的比賽本來想選擇天大，后來聽說8.23號有北大的月賽，于是便堅定地再戰POJ了.比賽前我們分好了題，開始的時候先各自看了一會題，我時不時盯一下board,比賽開始不久我發現A題已經有人過了，于是大家一起商量了下，決定dfs暴力這道題，并且由沸騰來寫這個題，其它人看別的題，過了沒多久，A題AC了。我們開的第二道題是一道概率題，求安全通過不踩到雷的概率，我初步分析了下，這道題可以轉化成一個遞推數列的問題，我直接敲了一個遞歸的算法，交上去，TLE了，于是不得不考慮其他的算法。其實這道題可以用差分方程直接算出來，這樣可以跳過中間的遞推，大家商量后，由張俊華推公式，開始Wa了1，2次，最終AC了，由于有公式，代碼非常短。這道題也提醒了我差分方程的重要性，尤其在對數列方面的題上。最終我們隊AC了兩題，大致排在前100位左右，比賽完后很以外的看到了“another crazy man"隊 ，神奇的是，和我們隊貼在一起了 呵呵。
再來看網絡賽的情況，第一場合肥網絡賽。題目比較“友好”，和平時做的題目，銜接度比較大，但是也有所創新，我覺得說它完全是陳題是不恰當的。分好題之后，大家各自開始看題，我首先看到了上升子序列那道題，和阿義商量了一下，很熟悉，不過暫時沒有想法，所以直接跳過看別的題，于是看到了那道計算幾何，由于暑假在家里做了計算幾何的專題，這樣的題目做了很多，主要是叉積的運用，不過由于早已總結出模板，直接套用模板，處理了一下輸入輸出就過了。等過了第一題，貌似開始覺得有希望的題已經被別的隊做出來了，只好開始看另外的題。這時候注意到了已經有很多人過的A題，壓力比較大，剛開始的時候大家都沒有什么想法，后來我想到了背包問題，大家一起討論，阿義突然說他有想法，貌似是他見過的一道題，航電上面的，當時聽到很多隊說它們用N^3的算法超時了，阿義說他用的是N^2的算法，敲好了之后處理了一下模除，順利AC.這時剩下的只有兩道同構的題目還有一道通過率為0的題目，由于同構的題目以前從來沒有接觸，圖的同構更是NP問題，幾乎沒有什么想法，只能上網搜索資料，后來聽說竇煜峰組過了，問了一下，原來用充分條件巧妙地AC了那道題，思路并不復雜，數據比較弱而已。這次比賽給我們的啟示主要出自同構的那兩道題，其實有的時候并不需要使用標準算法，比賽亦有技巧可用的。像圖的同構本為NP問題，既然標程都不可能使用絕對正確的算法，那么這題肯定可以使用做題技巧來解的。
接下來，第二場網絡賽，剛開始的時候非常郁悶，網絡不是很好，等真正拿到題目開始做題，幾乎半個小時過去了，然后看到了那道通過率比較高的hello,world,看到題目我的第一反應是匯編，不過顯然不可能，后來看到每一行代表一個字符，每一行有5個16進制數，而每一個字符由5個豎行表示，應該是一個16進制數代表一列的信息，數進制轉換無疑。不過正準備敲的時候，有同學發消息說這題已經過了，于是只好放棄看其他的題目。之后的1個小時，大家在看題，互通每道題目的意思，前兩個小時大致弄明白了沒道題目的意思，這一點我們做得很好。沸騰說題目難的話就做一道模擬題，于是他著手做了A題，我和阿義兩個人同時寫一道點線關系的題目。
關于那道計算幾何題，我們使用的是掃描+hash，可惜一直TLE，優化了很多次，還是TLE，直到比賽結束。賽后問了下中山大學的ACMer，它們用的也是hash判重的方法，過了，不過為什么我們的一直TLE？至于沸騰的那道題，應該是很有希望過的，不過由于時間原因，最后沒有寫完，略微有些遺憾。
哈爾濱網絡賽，寫總結之前，忽然聽說了現場賽要推遲的消息，原因是為了控制流感疫情，哈爾濱的幾所大學要采取應急措施，取消近期一切室內活動。不知道比賽究竟會被推到哪天進行。。。BTW，比賽開始以后，還是按照慣例，先分好題，阿義看的是后面，發現很快就有人AC了J題，我們想會不會是一個模擬題呢？于是我首先去模擬這個題，用了數組模擬然后優化，可惜TLE了，后來聯想到樹，不過好像已經被其他組過掉了，只好放棄，做別的題目。等大家把題目都看的差不多了，我們開了一道數列的題，我們很直觀的想到了差分方程求解數列的通項公式，然后再求位數。張俊華負責推出公式，可是后來我發現發現這個想法無法實現，因為計算中會出現小數，大數模板沒法處理小數。。。一時陷入了僵局。最終我們決定放棄這道題，不過時間已經所剩無多。賽后有人說這道題可以用模擬科學計算器的方法來做，這才恍然大悟。這次網絡賽對大家的啟示在于對題目的靈活轉換上面，有的問題并不是你不能，而是你沒有意識到。 愛因斯坦說的對，想象力比知識更重要。
總結就到這里，所說的一切只屬于過去，我相信，我們還會繼續不斷地向前走，不斷地超越自我，我們的集訓隊也會變得更加強大。
5個16進制數代表一個符號，這個符號用5個豎行來表示，顯然一個數字代表一豎行的信息，將那個十六進制數轉換為2進制后會有8位，取前7位在適當的位置輸出'#'即可！這題也可以算作一道密碼破譯題。
#include<iostream>
using namespace std;
char s[100][500];
char t[10];
void trans(int n)
{
int p=0;
memset(t,'0',sizeof(t));
while(n!=0)
{
p++;
if(n%2==1)
t[p]='1';
n/=2;
}
}
int main()
{
int testcase;
int i,j;
int k;
int n;
scanf("%d",&testcase);
for(i=1;i<=testcase;i++)
{
memset(s,' ',sizeof(s));
scanf("%d",&n);
for(j=1;j<=n;j++)
{
for(k=1;k<=5;k++)
{
int num;
scanf("%x",&num);
trans(num);
int l;
for(l=1;l<=7;l++)
{
if(t[l]=='1')
s[8-l][(j-1)*6+k]='#';
}
}
}
printf("Case %d:\n\n",i);
for(j=7;j>=1;j--)
{
for(k=1;k<=6*n-1;k++)
{
printf("%c",s[j][k]);
}
printf("\n");
}
printf("\n");
}
return 0;
}
今天終于將后綴數組總結完了，開個貼慶祝一下，順便總結一下字符串的相關問題，字符串問題按做法分大概可以是以下幾類：
1.暴力brute force ,這個沒什么可說的，一般正規的比賽這種方法必然超時。。。（山寨比賽似乎可以考慮。。。）
2.字典樹問題，通常和多個字符串的前綴有關。能寫出模板基本上就沒問題了，比賽的時候稍微改改，套上去就能用。
3.KMP問題，單串匹配，求一個字符串在另一個字符串中的匹配情況，可重復，不可重復均可。Next函數擴展問題，這個我已經總結過。
4.后綴數組問題，重點之所在，結合羅穗騫同學的論文，總結了使用后綴數組的13中重要情況，幾乎可以覆蓋所有的字符串問題。
5.AC自動機 這個多串匹配，模板很重要。
２．２．２子串的個數
例5：不相同的子串的個數（spoj694,spoj705）
給定一個字符串，求不相同的子串的個數。
算法分析：
每個子串一定是某個后綴的前綴，那么原問題等價于求所有后綴之間的不相
同的前綴的個數。如果所有的后綴按照suffix(sa[1]), suffix(sa[2]),
suffix(sa[3]), …… ,suffix(sa[n])的順序計算，
不難發現，對于每一次新加
進來的后綴suffix(sa[k]),它將產生n-sa[k]+1 個新的前綴。但是其中有
height[k]個是和前面的字符串的前綴是相同的。所以suffix(sa[k])將“貢獻”
出n-sa[k]+1- height[k]個不同的子串。累加后便是原問題的答案。這個做法
的時間復雜度為O(n)。
看的時候怎么都沒看懂為什么要加一，從他論文里給出的模板來看，sa[i]的取值應該從0 to n-1,帶了一下1111這個數據，顯然加一是錯誤的。后來用模板做了下spoj 694，加1WA,反之AC，證明了我的想法，看來羅同學的表達有些前后不一致了。
另外，羅同學在給出的標程中并沒有使用他給出的解法，而是轉了個彎，等差數列求和算出所有后綴長度的總和，然后在減去height[i](i from 1 to n),
這個做法比直接累加要好些。
記得以前讀過蘇軾的《范增論》，原文的第一段是：
漢用陳平計，間疏楚君臣，項
羽疑范增與漢有私，稍奪其權。增大怒曰：“天下事大定矣，君王自為之，愿賜骸骨，歸卒伍。”未至彭城，疽發背死。
一直好奇陳平用的是什么計策，呵呵，今天在現代生物導論上看了陳丞相世家，才豁然開朗。
上大學以后就一直在抽時間看《史記》，畢竟是史家之絕唱，無韻之離騷嘛，以前看的人物雖然戰功累累，但是論智謀卻只能算平平。也許因為我也屬于智慧型，所以對陳平頗為看好吧，尤其是他的智謀^_^
陳丞相平者，陽武戶牖鄉人也。這是第一段的收獲，個人感覺看完史記至少得記住這人的封號還有籍貫 呵呵。
原來他還屬于倒插門類型的，他家里很窮，但是他娶了一個富人的女兒張氏，記得李白也屬于這種類型，難道有才之人都有這共通之處嗎？呵呵
第三段對我來說印象較為深刻，“里中灶，平為宰，分肉食甚均。父老曰：“善，陳孺子之為宰！”平曰：“嗟乎，使平得宰天下，亦如是肉矣！”聰明的你一定看出來了吧，陳平一句“使平得宰天下，亦如是肉矣”道出了陳平的雄心壯志，宰肉算什么，要宰，就宰天下！
事實上，他做到了。
我覺得陳平最過人之處就是他的智謀，這從他使金離間項羽和亞父范增中體現的淋漓盡致。“陳平既多以金縱反間于楚軍，宣言諸將鐘離昧等為項王將，功多矣，然而終不得裂地而王，欲與漢為一，以滅項式而分王其地。項羽果意不信鐘離昧等。”接著劉邦與平一唱一和，“吾以為亞父使，乃項王使”復持去，更以惡草具進楚使。這招可夠聰明的，既散播謠言，動搖項羽內心，又區別對待楚使，這讓項羽不得不信他的將領懷有二心。中國的政治斗爭中，要想取勝，最重要的一點就是互相信任，一旦互相猜忌，后果就不堪設想。在想想戰場上，忠心耿耿的岳飛吧，為了保衛國家，將生死置之度外，但是他最終沒有死在敵人的利刃下，而是死在同朝幕僚的讒言中，不亦哀乎！。。。。。。防人之口，甚于防川啊。
再看陳平所獻之第二計：誘捕韓信。韓信這個人，太傲氣，功高蓋主，竟自立為齊王。難道他沒有像樣一點的謀士嗎？難道他不知道鳥盡弓藏，兔死狗烹,卸磨殺驢嗎？稍微懂點歷史的人都知道，在平定天下之后，功高蓋主的必然是帝王的首要鏟除對象。哎，韓信的下場大家都知道了，我只是可惜，因為我也很喜歡韓信的。閑話不多說，還是說陳平吧，當韓信自立為齊王后，各種各樣有關他要謀反的謠言就自然而然地傳到劉邦的耳朵里，問問武官,怎么辦？武官們說，打！再問陳平，平曰“人之上書直言信反，有知之者乎？”曰：“未有。”曰:“信知之乎？”曰：“不知。”陳平曰：“陛下精兵孰與楚？”上曰：“不能過”。正由于陳平一番話，把問題的實質給揭露出來，既然打不過，這樣做不是自取滅亡嗎？況且出師無名，又如何取信于天下？韓信獻計：不如來個天子南游，等群諸侯來謁之時，因而擒之，不過幾個力士的事罷了？又何必動用軍隊？^_^
再看陳平做人，拿捏有度，不自矜其能，不功高蓋主，為人謙讓，這才是真正的做人之道啊!再看看你身邊的那些人吧，一旦有了點權利就自高自傲，目空一切，殊不知這是在為自己買棺材呢。俞敏洪上次來演講的時候還這樣說，天上有座云做的沙發，位置很高，但是你敢做嗎？座上去，還不摔死你？絳侯勃，為右丞相時，平為左丞相，首先必須知道，古代尚右。又一次孝文帝問：天下一年有多少刑事案件啊？勃不知，又問國家一年有多少錢谷收入呀？勃又不知，天子有些不高興了。陳平這時顯得很聰明，他沒有落井下石，而是幫勃下臺，說這些事情自有專門的人處理，左右丞相只不過是幫天子您管理好您的臣子罷了，我們的職責是“主臣！”這讓勃自愧不如，只能自愿地將右丞相的位置拱手送給陳平。這不是很高明嗎？個人認為陳平的做人是很值得我們學習的
呵呵 司馬遷對他的評價也很高，說其“常出奇計，救紛糾之難，振國家之患。及呂后時，事多故矣，然平竟自脫，定宗廟，以榮名終，稱賢相，豈不善始善終哉！非智謀孰能當此者乎？”縱觀歷史風云，最后得善始善終的寥寥無幾，陳平這個人做到了，又豈能說是歷史的偶然呢？
毛澤東二十歲左右的時候也讀過史記,據聞他很喜歡做批注，不知道他對陳平的評價如何，是否英雄所見略同呢？
摘要: POJ 2485 Highways 標準的prim模板題，只是輸出的不是最小生成樹的總權值，而是MST中的最長邊。
#include<iostream>#include<cmath>#include<cstdio>using namespace std;#define MAX 501int n;int ...
閱讀全文
摘要: 北京賽區的經典題目，最優比率生成樹，傳說中樓哥1A的G題。。。什么是最優比率生成樹呢？說白了很簡單，已知一個完全圖，每條邊有兩個參數（b和c），求一棵生成樹，使(∑xi×ci)/(∑xi×bi)最小，其中xi當第i條邊包含在生成樹中時為1，否則為0。其實也可以看成一個0，1的整數規劃問題。我的做法是LRJ《算法藝術與信息學競賽》中介紹的二分，詳細的證明請看書，這里只是簡單的介紹...
閱讀全文
二分圖最小覆蓋的Konig定理及其證明
二分圖：
頂點可以分類兩個集合X和Y，所有的邊關聯在兩個頂點中，恰好一個屬于集合Ｘ，另一個屬于集合Ｙ。
最小覆蓋：
最小覆蓋要求用最少的點（Ｘ集合或Ｙ集合的都行）讓每條邊都至少和其中一個點關聯?？梢宰C明：最少的點（即覆蓋數）＝最大匹配數
Konig定理：
二分圖的最小頂點覆蓋數等于最大匹配數。
證明：
為主便敘述，假設G分為左邊X和右邊Y兩個互不相交的點集。。。。。。
假設G經過匈牙利算法后找到一個最大匹配M，則可知G中再也找不到一條增廣路徑。
標記右邊未匹配邊的頂點，并從右邊未匹配邊的頂點出發，按照邊：未匹配->匹配->未匹配...，的原則標記途中經過的頂點，則最后一條經過的邊必定為匹配邊。重復上述過程，直到右邊不再含有未匹配邊的點。
記得到的左邊已標記的點和右邊未標記的點為S， 以下證明S即為所求的最小頂點集。
1。| S | == M
顯然，左邊標記的點全都為匹配邊的頂點，右邊未標記的點也為匹配邊的頂點。因此，我們得到的點與匹配邊一一對應。
2。S能覆蓋G中所有的邊。
上途S中點所得到的邊有以下幾種情況：
（1）左右均標記；
（2）左右均無標記；
（3）左邊標記，右邊未標記；
若存在一條邊e不屬于S所覆蓋的邊集，則e 左邊未標記右邊標記。
如果e不屬于匹配邊，那么左端點就可以通過這條邊到達（從而得到標記）；如果e屬于匹配邊，那么右端點不可能是一條路徑的起點，于是它的標記只能是從這條邊的左端點過來的左端點就應該有標記。
3。S是最小的覆蓋。
因為要覆蓋這M條匹配邊至少就需要M個點。
轉自:http://yejingx.ycool.com/post.2801156.html#
在一個ＰＸＰ的有向圖中，路徑覆蓋就是在圖中找一些路經，使之覆蓋了圖中的所有頂點，且任何一個頂點有且只有一條路徑與之關聯；（如果把這些路徑中的每條路徑從它的起始點走到它的終點，那么恰好可以經過圖中的每個頂點一次且僅一次）；如果不考慮圖中存在回路，那么每每條路徑就是一個弱連通子集．
由上面可以得出：
１.一個單獨的頂點是一條路徑；
２．如果存在一路徑p1,p2,......pk，其中p1 為起點，pk為終點，那么在覆蓋圖中，頂點p1,p2,......pk不再與其它的頂點之間存在有向邊．
最小路徑覆蓋就是找出最小的路徑條數，使之成為Ｐ的一個路徑覆蓋．
路徑覆蓋與二分圖匹配的關系：
最小路徑覆蓋＝｜Ｐ｜－最大匹配數；
其中最大匹配數的求法是把Ｐ中的每個頂點pi分成兩個頂點pi'與pi''，如果在p中存在一條pi到pj的邊，那么在二分圖Ｐ＇中就有一條連接pi'與pj''的無向邊；這里pi' 就是p中pi的出邊，pj''就是p中pj 的一條入邊；
對于公式：最小路徑覆蓋＝｜Ｐ｜－最大匹配數；可以這么來理解；
如果匹配數為零，那么Ｐ中不存在有向邊，于是顯然有：
最小路徑覆蓋＝｜Ｐ｜－最大匹配數＝｜Ｐ｜－０＝｜Ｐ｜；即Ｐ的最小路徑覆蓋數為｜Ｐ｜；
Ｐ＇中不在于匹配邊時，路徑覆蓋數為｜Ｐ｜；
如果在Ｐ＇中增加一條匹配邊pi'－－＞pj''，那么在圖P的路徑覆蓋中就存在一條由pi連接pj的邊，也就是說pi與pj 在一條路徑上，于是路徑覆蓋數就可以減少一個；
如此繼續增加匹配邊，每增加一條，路徑覆蓋數就減少一條；直到匹配邊不能繼續增加時，路徑覆蓋數也不能再減少了，此時就有了前面的公式；但是這里只 是說話了每條匹配邊對應于路徑覆蓋中的一條路徑上的一條連接兩個點之間的有向邊；下面來說明一個路徑覆蓋中的每條連接兩個頂點之間的有向邊對應于一條匹配 邊；
與前面類似，對于路徑覆蓋中的每條連接兩個頂點之間的每條有向邊pi--->pj，我們可以在匹配圖中對應做一條連接pi'與pj''的邊， 顯然這樣做出來圖的是一個匹配圖（這一點用反證法很容易證明，如果得到的圖不是一個匹配圖，那么這個圖中必定存在這樣兩條邊 pi'---pj'' 及 pi' ----pk''，（j!=k），那么在路徑覆蓋圖中就存在了兩條邊pi-->pj, pi--->pk ，那邊從pi出發的路徑就不止一條了，這與路徑覆蓋圖是矛盾的；還有另外一種情況就是存在pi'---pj'',pk'---pj''，這種情況也類似可證）；
至此，就說明了匹配邊與路徑覆蓋圖中連接兩頂點之間邊的一一對應關系，那么也就說明了前面的公式成立！
轉自:http://hi.baidu.com/cjhh314/blog/item/ded8d31f15d7510c304e1591.html
摘要: 最長上升子序列問題是各類信息學競賽中的常見題型，也常常用來做介紹動態規劃算法的引例，筆者接下來將會對POJ上出現過的這類題目做一個總結，并介紹解決LIS問題的兩個常用算法(n^2)和(nlogn).問題描述:給出一個序列a1,a2,a3,a4,a5,a6,a7....an,求它的一個子序列（設為s1,s2,...sn），使得這個子序列滿足這樣的性質，s1<s2<s3<...<...
閱讀全文
想想去年7月份的時候，我才剛剛開始接觸ACM，短短一年的時間，就到400題了，雖然過程曲折回環，但終究還是走了過來，特留此貼紀念。
昨天有位同學幫我重新溫習了下稼軒先生的 賀新郎，想了想，詞中的千古名句，我見青山多嫵媚，料青山見我應如是放在此處，當是很貼切吧。只不過，我的心境和稼軒先生的略有不同，稼軒先生的兩句詩，與其說是真正的樂觀，還不如說是不得志時，聊以療傷的借口！今天，我借稼軒先生的兩句詩，以我的心境，賦給它全新的含義：自古英雄多磨難，但是只要擁有樂觀的姿態，又有什么做不到的呢？我見青山多嫵媚，料青山兄見我也應當如此吧。呵呵^_^
50，100，200，300，400
幾個尋常的數字，卻藏著一段難忘的人生經歷。
從水題，到基本貪心，動態規劃等算法，再到最短路生成樹，再到網絡流，匹配，線段樹，后綴樹，后綴數組，差分約束，計算幾何，組合數學，從一無所知，到寫出模板并熟練的運用模板解題，幾乎完全自學，從不可能到可能，now ,you should believe, everything is possible~
今后的日子，當然還要繼續努力，亞洲區預賽馬上就要到了，我要全力以赴，so please trust me , yes we can~
最后，我要感謝在ACM道路上幫助過我的教練，學長和我的同學們，謝謝你們對我的鼓勵和幫助。