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