POJ 2348 Euclid's Game 博弈問題

首先結(jié)果不可能有二義性，即必須是某個確定的人獲勝(W)。

如果誰先獲得選擇權(quán)那么他就能決定在子結(jié)構(gòu)中是先手還是后手。有的時候要選擇先手，有時后手，誰先具有選擇權(quán)，誰就能得到他想要的順序(O).

如果沒有一個人能獲得選擇權(quán)，比如說大數(shù)始終不是小數(shù)的2倍或以上，那么只能看天意了(F).

so the function is:
wisdom + option + fortune = success 

PS:做完之后的確覺得簡單，但是要能想到它卻不容易。關(guān)于博弈問題，目前還處在做一題會一題的狀態(tài)，希望再做幾題能觸類旁通吧。

posted @ 2010-03-08 16:40 abilitytao 閱讀(460) | 評論 (0) | 編輯 收藏

POJ 1463 Strategic game 第二個樹形DP

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>hash[1500];
int n;
int s[1500];
int dp[1500][2];
int root;
void dfs(int x)
{
    int i,j;
    int len=hash[x].size();
    for(i=0;i<len;i++)
        dfs(hash[x][i]);
    if(len==0){dp[x][0]=0;dp[x][1]=1;}
    else
    {
        for(i=0;i<len;i++)
        {
            dp[x][0]+=dp[hash[x][i]][1];
            dp[x][1]+=min(dp[hash[x][i]][0],dp[hash[x][i]][1]);
        }
        dp[x][1]++;
    }
}
int main()
{
    int v,t,num;
    int i,j;
    while(scanf("%d",&n)!=EOF)
    {
        memset(dp,0,sizeof(dp));
        memset(s,0,sizeof(s));
        for(i=0;i<n;i++)
            hash[i].clear();
        for(i=1;i<=n;i++)
        {

            scanf("%d:(%d)",&v,&num);
            for(j=1;j<=num;j++)
            {
                scanf("%d",&t);
                hash[v].push_back(t);
                s[t]=1;
            }
        }
        for(i=0;i<n;i++)
            if(s[i]==0){root=i;break;}
        dfs(root);

        printf("%d\n",min(dp[root][0],dp[root][1]));
    }
    return 0;
}

posted @ 2010-03-08 00:38 abilitytao 閱讀(1670) | 評論 (0) | 編輯 收藏

POJ 1947 Rebuilding Roads 第一個樹形DP

#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define INF 999999999
#define MAX 151
vector<int> hash[MAX];
int dp[MAX][MAX];
int n,p;

void dfs(int x)//x代表當(dāng)前訪問結(jié)點
{
    int i,j,k;
    int len=hash[x].size();
    for(i=0;i<len;i++)
        dfs(hash[x][i]);
    /**///////////////////////////////////////////////////////////////////////////
    //后序遍歷，從葉子往上逐層遞推
    if(x==1)    dp[x][1]=hash[x].size();
    else dp[x][1]=hash[x].size()+1;
    for(k=0;k<len;k++)
    {
        for(i=p-1;i>=1;i--)
        {
            if(dp[x][i]!=INF)
            {
                for(j=1;i+j<=p;j++)
                {
                    if(dp[hash[x][k]][j]!=INF)
                        dp[x][i+j]=min(dp[x][i+j],dp[x][i]+dp[hash[x][k]][j]-2);
                }
            }
        }
    }
}



int main()
{
    scanf("%d%d",&n,&p);
    int i,j;
    int t1,t2;
    for(i=1;i<=n-1;i++)
    {
        scanf("%d%d",&t1,&t2);
        hash[t1].push_back(t2);
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=p;j++)
            dp[i][j]=INF;
    dfs(1);
    int ans=INF;
    for(i=1;i<=n;i++)
    {
        if(dp[i][p]<ans)
            ans=dp[i][p];
    }
    printf("%d\n",ans);
    return 0;
    
    


}

posted @ 2010-03-07 23:36 abilitytao 閱讀(1260) | 評論 (0) | 編輯 收藏

再品蘇軾

卻對酒杯疑是夢，
試拈詩筆已如神。
此災(zāi)何必深追咎，
竊祿從來豈有因。

和子由澠池懷舊 賞析
蘇軾
人生到處知何似？應(yīng)似飛鴻踏雪泥。
泥上偶然留爪印，鴻毛那復(fù)計東西。
老僧已死成新塔，壞壁無由見舊題。
往日崎嶇君記否；路長人困蹇驢嘶。


蝶戀花
年代：宋 作者：蘇軾

花褪殘紅青杏小。燕子飛時，綠水人家繞。枝上柳綿吹又少，天涯何處無芳草？
 墻里秋千墻外道。墻外行人，墻里佳人笑。笑漸不聞聲漸悄，多情卻被無情惱。

雪后書北臺壁二首
年代：宋 作者：蘇軾

黃昏猶作雨纖纖，夜靜無風(fēng)勢轉(zhuǎn)嚴(yán)。
但覺衾裯如潑水，不知庭院已堆鹽。
五更曉色來書幌，半夜寒聲落畫檐。
試掃北臺看馬耳，未隨埋沒有雙尖。
城頭初日始翻鴉，陌上晴泥已沒車。
凍合玉樓寒起粟，光搖銀海眼生花。
遺蝗入地應(yīng)千尺，宿麥連云有幾家。
老病自嗟詩力退，空吟冰柱憶劉叉。

史記：劉叉《冰柱》詩歌鑒賞 翻譯 原文

劉叉 　　師干久不息，農(nóng)為兵兮民重嗟。 　　騷然縣宇，土崩水潰， 畹中無熟谷， 垅上無桑麻。 　　王春判序，百卉茁甲含葩。 　　有客避兵奔游僻，跋履險阨至三巴。 　　貂裘蒙茸已敝縷，鬢發(fā)蓬舥。 　　雀驚鼠伏，寧遑安處， 獨臥旅舍無好夢， 更堪走風(fēng)沙！ 　　天人一夜剪瑛琭，詰旦都成六出花。 　　南畝未盈尺，纖片亂舞空紛拏。 　　旋落旋逐朝暾化，檐間冰柱若削出交加。 　　或低或昂，小大瑩潔，隨勢無等差。 　　始疑玉龍下界來人世，齊向茅檐布爪牙。 　　又疑漢高帝，西方來斬蛇。 　　人不識，誰為當(dāng)風(fēng)杖莫邪。 　　鏗鏘冰有韻，的玉無暇。 　　不為四時雨，徒于道路成泥柤。 　　不為九江浪，徒為汩沒天之涯。 　　不為雙井水，滿甌泛泛烹春茶。 　　不為中山漿，清新馥鼻盈百車。 　　不為池與沼，養(yǎng)魚種芰成霪霪； 　　不為醴泉與甘露，使名異瑞世俗夸。 　　特稟朝沏氣，潔然自許靡間其邇遐。 　　森然氣結(jié)一千里，滴瀝聲沉十萬家。 　　明也雖小，暗之大不可遮。 　　勿被曲瓦，直下不能抑群邪。 　　奈何時逼，不得時在我夢中， 倏然漂去無余。 　　自是成毀任天理，天于此物豈宜有忒賒。 　　反令井蛙壁蟲變?nèi)菀?，背人縮首競呀呀。 　　我愿天子回造化，藏之韞櫝玩之生光華。　　 　　從唐德宗貞元末到憲宗元和時期，以韓愈為首的一派詩人，一反大歷以來圓熟浮麗的詩風(fēng)，走上險怪幽僻一路。如韓愈的《陸渾山火》和盧仝的《月蝕詩》等都足以代表這種詩風(fēng)。劉叉也是這一詩派的著名人物，以《冰柱》、《雪車》二詩為最有名，而《冰柱》詩尤奇譎奔放，寄托遙深，為后世所稱揚。 　　全詩可分為三段。 　　從首句到“更堪走風(fēng)沙”為第一段。在這一段里，詩人首先揭露了當(dāng)時的社會現(xiàn)實：干戈不息，民不聊生。安史亂后，接著出現(xiàn)藩鎮(zhèn)割據(jù)的局面，而吐蕃也多次出兵騷擾西南邊疆，詩里所說的“騷然縣宇，土崩水潰，畹中無熟谷，垅上無桑麻”，反映了當(dāng)時因戰(zhàn)禍連綿而造成的田園荒蕪景象。詩人為了躲避兵災(zāi)，逃向四川，而四川也非樂土。旅途是艱辛的，漫長的，而在兵荒馬亂中跋山涉川，不僅要忍受風(fēng)霜勞頓之苦，還要時時提防惡人的侵害。“貂裘蒙茸已敝縷，鬢發(fā)蓬舥，雀驚鼠伏”，寫出了旅途中的狼狽情景，為下文借寫冰柱抒發(fā)感喟作了鋪墊。 　　從“天人一夜剪瑛琭”到“直下不能抑群邪”為第二段。這一段是全詩的主要部分，描繪了冰柱的奇麗景色。在一夜大雪之后，房檐間的冰柱垂掛下來，大大小小，高高低低，一樣的晶瑩潔白，玉色瓊輝。它不是冰柱，而是天上玉龍的爪牙；它不是冰柱，而是漢高帝的斬蛇寶劍！這兩個奇特的比喻，不僅寫出了冰柱的風(fēng)神，還為下文寫它的不為世用張勢：它不能化為及時雨，使田禾滋壯；而只能化為泥漿，使道路艱難。它不能化為九江的波浪，奔向大海；而只能浸沒于峽谷，沉淪于天涯。它不能化為雙井名泉，煮茗煎茶；它不能化為中山美醞，芳香四溢。它不能蓄而為池，積而為沼，養(yǎng)魚種芰；它不能為甘泉，不能為飴露，使這特異的祥瑞征兆為世俗贊夸。它只能憑著它的清沏之氣，孤潔自賞，自凝自消。它的光彩雖不大，卻無法掩遮；它負(fù)著曲瓦，不能施展神鋒，鏟除奸邪。這一大段的描繪，句句是在寫冰柱，卻句句關(guān)合到詩人自己。詩人的懷才不遇的激憤之情，剛傲不羈的性格，全面地顯示了出來。 　　從“奈何時逼”到末句為第三段。這一段寫冰柱消失以后的感慨。天晴凍解，冰柱從夢中消失，杳無蹤跡。萬物的成與毀是天決定的，它對于冰柱不會特加恩澤，卻反而使那些井蛙壁蟲，順生易長，背著人，縮著頭，聒噪不休。希望天子能回造化之力，把冰柱珍藏在柜子里，使它永遠(yuǎn)放出光輝。這一段比上一段更深一層，拿容易消失的冰柱和最易繁衍的蛙蟲對比，揭示出當(dāng)時政治上的小人橫行、賢士在野的情況。最后詩人把理想寄托在皇帝身上，希望他能挽轉(zhuǎn)形勢，重用賢才。詩的最后兩句是畫龍點晴，點出了詩的主題，就是說只要皇帝能重用賢士，排斥奸邪，就能消弭戰(zhàn)禍，天下太平。 　　這首詩在藝術(shù)上很有特色，以冰柱入詩，題材新奇。更奇的是對冰柱的形象描寫，把冰柱擬人化，句句是寫冰柱，也是句句在表露自己的懷才不遇。他用玉龍的爪牙，劉邦的斬蛇寶劍來比喻冰柱，貼切而新鮮，為修辭手法創(chuàng)一特例。就詩體來說，這首詩是句子長短不一的雜言體，抒寫較自由，適宜于表現(xiàn)較復(fù)雜的思想感情。用這種詩體，不可避免的是多議論，散文化。劉叉的這首詩顯然是受《月蝕詩》的影響，而又加以發(fā)展，顯得更為奇譎奔放。使這首詩顯出它的最大特色的是在用韻方面。它用的是麻韻，麻韻字的音是響亮的，高亢的，但韻字卻比較少，因有“險韻”之稱。這首詩共二十七韻，全屬麻韻，中間的“舥”字，“柤”字很少有人用過。“邪”字用了兩次，前一個音“牙”，是劍名；后一個音“霞”，是奸邪之“邪”的另一讀，音義不同，故得同用。用麻韻寫古體詩，一韻到底的很罕見。本詩在抒寫中一氣貫下，縱橫自如，在描繪冰柱一段，連用了六個“不為”排句，氣勢浩蕩，郁結(jié)于胸中的不平之氣，噴薄而出，“特稟朝沏氣，潔然自許靡間其邇遐”兩句，拗折多姿；“森然氣結(jié)一千里，滴瀝聲沉十萬家”兩句，對仗整飭。這些句式的變化是和感情的起伏跌宕密切相連的，句子或長或短，或?qū)φ?，或散行，而最后都能很自然地落到韻腳上來，毫無生拼硬湊的毛病，用險韻而不覺其險，顯示出詩人的才華，為唐代詩壇增添了光彩。宋代蘇軾在《雪后書北臺壁二首》中用“尖”“叉”二韻，第二首的末兩句是：“老病自嗟詩力退，寒吟《冰柱》憶劉叉。”可以看出他對于劉叉的《冰柱》詩是很贊賞的。　?。ɡ钔⑾龋?/span>

posted @ 2010-03-06 23:02 abilitytao 閱讀(331) | 評論 (1) | 編輯 收藏

航電3月月賽

#include<iostream>
using namespace std;


int mm[200][200];

int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m))
    {
        memset(mm,0,sizeof(mm));
        int flag=0;
        if(n==0)
            break;
        int i,j;
        for(i=1;i<=m;i++)
        {

            int t1,t2;
            scanf("%d%d",&t1,&t2);
            mm[t1][t2]=1;

        }
        int k;
        for(k=0;k<n;k++)
        {

            for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                {

                    if(mm[i][k]==1&&mm[k][j]==1)
                        mm[i][j]=1;
                }
        }
        for(i=0;i<n;i++)
        {
            for(j=i+1;j<n;j++)
            {
                if(mm[i][j]==1&&mm[j][i]==1)
                {
                    flag=1;
                    break;
                }
            }
            if(flag)
                break;
        }
        if(flag)
            printf("NO\n");
        else
            printf("YES\n");
    }
    return 0;
}

#include<iostream>
using namespace std;
char str[200010];
int next[200010];
int dp[200010];

inline void calnext(char s[],int next[])
{
    int i;
    int j;
    int len=strlen(s);
    next[0]=-1;
    j=-1;
    for(i=1;i<len;i++)
    {
        while(j>=0&&s[i]!=s[j+1])
            j=next[j];
        if(s[j+1]==s[i])//上一個循環(huán)可能因為j=-1而不做，此時不能知道s[i]與s[j+1]的關(guān)系。故此需要此條件。
            j++;
        next[i]=j;
    }
}

int main()
{

    int n;
    int t;
    scanf("%d",&t);
    int i,j;
    int sum;
    for(i=1;i<=t;i++)
    {
        
        scanf("%d",&n);
        scanf("%s",str);
        calnext(str,next);
        dp[0]=1;
        sum=1;
        for(j=1;j<n;j++)
        {
            if(next[j]==-1)
            {
                dp[j]=1;
                sum++;
                sum%=10007;
            }
            else
            {
                dp[j]=dp[next[j]]+1;
                sum+=dp[j];
                sum%=10007;
            }

            
        } 
        printf("%d\n",sum);

    }
    return 0;
}

posted @ 2010-03-06 17:15 abilitytao 閱讀(1218) | 評論 (0) | 編輯 收藏

POJ 2836 Rectangular Covering

posted @ 2010-03-06 00:01 abilitytao 閱讀(1187) | 評論 (0) | 編輯 收藏

Topcoder 463 Div 2 1000

{5, 8}

Returns: 40.0

{1.5, 1.8}

Returns: 3.3

{8.26, 7.54, 3.2567}

Returns: 202.82857868

{1.5, 1.7, 1.6, 1.5}

Returns: 9.920000000000002

{10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
                                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
                                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
                                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
                                    10, 10, 10, 10, 10, 10, 10, 10, 10, 10}

Returns: 1.0E50

發(fā)現(xiàn)偶還是太水了。。。

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;



class Nisoku
{
public:
    double theMax(vector<double>cards)
    {    
        int i,j;
        sort(cards.begin(),cards.end());
        double ans=0;
        for(i=0;i<=cards.size();i+=2)
        {
            double p=1;
            for(j=0;j<i/2;j++)
                p*=(cards[j]+cards[i-1-j]);
            for(j=i;j<cards.size();j++)
                p*=cards[j];
            ans=max(ans,p);
        }
        return ans;
    }
};

誰能證明下這份代碼的正確性？

posted @ 2010-03-02 22:27 abilitytao 閱讀(1075) | 評論 (0) | 編輯 收藏

動態(tài)規(guī)劃——思想者的游戲

posted @ 2010-02-23 21:21 abilitytao 閱讀(292) | 評論 (0) | 編輯 收藏

北京之行

1.各火車站到新東方總部的乘車路線

北京站—總部（新東方大廈）：乘地鐵2號線到西直門下車，步行至西直門外換乘808、運通105、運通106、運通205等到海淀黃莊北下車。下車后經(jīng)過街天橋到路西側(cè)，沿中關(guān)村廣場步行街走到頭即是新東方總部。
北京西站—總部（新東方大廈）：
 乘320、特6路到海淀黃莊北下車。下車后經(jīng)過街天橋到路西側(cè)，沿中關(guān)村廣場步行街走到頭即是新東方總部。

北京南站—總部（新東方大廈）：
 乘特5路到甘家口北下車，換乘320、特6路到海淀黃莊北下車。下車后經(jīng)過街天橋到路西側(cè)，沿中關(guān)村廣場步行街走到頭即是新東方總部。
北京北站—總部（新東方大廈）：
 步行至西直門外，乘運通205、運通106、運通105、808等到海淀黃莊北下車。下車后經(jīng)過街天橋到路西側(cè)，沿中關(guān)村廣場步行街走到頭即是新東方總部。機(jī)場—總部（新東方大廈）：乘機(jī)場地鐵線到三元橋下車換乘地鐵10號線到海淀黃莊下車。A2出口出,出來后馬路對面沿步行街直走,走到頭.家樂福超市西側(cè)，鼎好電子城西南側(cè)。咨詢電話：010-82611818轉(zhuǎn)0。

2.新東方總部
 新東方大廈（總部）（周一至周日8：00-18：30）：海淀中街6號金融中心B座 3層，可乘坐特6、特4、307、355、726、365、 801、302、826、731、814、320等到中關(guān)村或海淀黃莊下車；地鐵4號線到中關(guān)村站從D口出來。地鐵10號線到海淀黃莊站下A2出口出,出來后馬路對面沿步行街直走,走到頭即是.位于家樂福超市西側(cè)，鼎好電子城西南側(cè)。咨詢電話：010-82611818轉(zhuǎn)0。

3.北京永正商務(wù)酒店　電話：010-62565550

4.萬通驛站　蘇州街店　電話:010 52719998

5.圖書城

　　地址：海淀區(qū)西大街39號

　　乘車路線：運通118、26、394、運通119、944支、運通110、運通114 北京地震局下車。運通113、740 外環(huán)、751、913、982、983 支海淀橋西下車，往回走過海淀橋路東見昊海樓。732、808、332、333 內(nèi)環(huán)、394、運通106、運通114、718，海淀橋北下車。913、641、944 支、982、983 支、718、808、運通110、運通113、運通109，中關(guān)村西站下車。

posted @ 2010-02-14 21:56 abilitytao 閱讀(331) | 評論 (0) | 編輯 收藏

除夕之夜的動態(tài)規(guī)劃　POJ 1015 Jury Compromise

posted @ 2010-02-13 19:03 abilitytao 閱讀(1990) | 評論 (0) | 編輯 收藏