ZOJ 1141 簡(jiǎn)單的題目就用簡(jiǎn)單的代碼

前言

因?yàn)槲以谧鲱}目的過(guò)程中捏卓,WA了(最后發(fā)現(xiàn)是數(shù)組開(kāi)小了的緣故),我以為我方法錯(cuò)誤慈格。然后百度一下怠晴,滿(mǎn)屏的LCA在線(xiàn)/離線(xiàn)算法。加上長(zhǎng)篇代碼浴捆。為了拯救茫茫的ACMer蒜田,我決定吐槽一下在這題中使用LCA算法的人

附上 LCA算法的簡(jiǎn)介

題意

給出一顆樹(shù),給出若干個(gè)查詢(xún)选泻,每個(gè)查詢(xún)是樹(shù)的兩個(gè)節(jié)點(diǎn)冲粤,要求的是這兩個(gè)節(jié)點(diǎn)的最近公共祖先。最后總計(jì)每個(gè)數(shù)作為最近公共祖先出現(xiàn)的次數(shù)页眯。說(shuō)白了就是最近公共祖先問(wèn)題梯捕。

解析

的確,LCA是用于求最近公共祖先的一種有效算法窝撵,但是由于思想比較復(fù)雜(從根節(jié)點(diǎn)開(kāi)始搜索)且代碼量太大了(隨便找了一篇就是180行的長(zhǎng)度)傀顾,所以在這里并不推薦用。如果只是要A這道題碌奉,那大可以這樣

比如要查(3,4)最近公共祖先
3開(kāi)始往上走短曾,得到:[3,2,5]
4開(kāi)始往上走,得到:[4,5]
然后倒序遍歷赐劣,55相同嫉拐,繼續(xù)比較2424不同魁兼,則上一個(gè)公共祖先 5 就是最近的公共祖先

再比如要查(2,3)最近公共祖先
2開(kāi)始往上走椭岩,得到:[2,5]
3開(kāi)始往上走,得到[3,2,5]
然后倒序遍歷,55相同判哥,繼續(xù)比較22也相同献雅,繼續(xù)比較3X(X表示越界,比較失敗)塌计,則上一個(gè)公共祖先2就是最近的公共祖先

LCA算法在于從根節(jié)點(diǎn)開(kāi)始遍歷挺身,在深度優(yōu)先搜索的過(guò)程中對(duì)結(jié)點(diǎn)進(jìn)行“染色”操作。我覺(jué)得至少在這里锌仅,貌似簡(jiǎn)單的“白話(huà)文”(如上題解過(guò)程)更能讓人理解章钾,簡(jiǎn)單的題目,就用簡(jiǎn)單的理解+簡(jiǎn)單的代碼热芹,簡(jiǎn)單也是一種習(xí)慣

AC代碼

#include <iostream>
#include <stdio.h>
#include <string.h>
#define maxn 101000
using namespace std;
int dp1[maxn],dp2[maxn],dp[maxn],tree[maxn];
int main(int argc, const char * argv[]) {
    int n,m,p,d,len1,len2;
    char ch;
    while(cin>>n){
        memset(dp, 0, sizeof(dp));
        memset(tree, 0, sizeof(tree));
        while(n--){
            scanf("%d:(%d)",&p,&d);
            for(int i=0; i<d; i++){
                scanf("%d",&m);
                tree[m] = p;
            }
        }
        cin>>m;
        for(int j=0; j<m; j++){
            len1 = 0; len2 = 0;
            cin>>ws>>ch>>p>>ch>>d>>ch;
            while(p){
                dp1[len1++] = p;
                p = tree[p];
            }
            while(d){
                dp2[len2++] = d;
                d = tree[d];
            }
            while(dp1[--len1]==dp2[--len2]);
            dp[dp1[len1+1]]++;
        }
        for(int i=1; i<=1010; i++)
            if(dp[i]) cout<<i<<":"<<dp[i]<<endl;
    }
    return 0;
}
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末贱傀,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子伊脓,更是在濱河造成了極大的恐慌府寒,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,681評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件报腔,死亡現(xiàn)場(chǎng)離奇詭異株搔,居然都是意外死亡,警方通過(guò)查閱死者的電腦和手機(jī)纯蛾,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門(mén)纤房,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái),“玉大人翻诉,你說(shuō)我怎么就攤上這事炮姨。” “怎么了碰煌?”我有些...
    開(kāi)封第一講書(shū)人閱讀 169,421評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵舒岸,是天一觀(guān)的道長(zhǎng)。 經(jīng)常有香客問(wèn)我拄查,道長(zhǎng)枉阵,這世上最難降的妖魔是什么椅亚? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 60,114評(píng)論 1 300
  • 正文 為了忘掉前任耳胎,我火速辦了婚禮猾警,結(jié)果婚禮上淮腾,老公的妹妹穿的比我還像新娘铣减。我一直安慰自己呼伸,他們只是感情好墨技,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評(píng)論 6 398
  • 文/花漫 我一把揭開(kāi)白布役拴。 她就那樣靜靜地躺著糊探,像睡著了一般。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上科平,一...
    開(kāi)封第一講書(shū)人閱讀 52,713評(píng)論 1 312
  • 那天褥紫,我揣著相機(jī)與錄音,去河邊找鬼瞪慧。 笑死髓考,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的弃酌。 我是一名探鬼主播氨菇,決...
    沈念sama閱讀 41,170評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼妓湘!你這毒婦竟也來(lái)了查蓉?” 一聲冷哼從身側(cè)響起,我...
    開(kāi)封第一講書(shū)人閱讀 40,116評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤榜贴,失蹤者是張志新(化名)和其女友劉穎豌研,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體竣灌,經(jīng)...
    沈念sama閱讀 46,651評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡聂沙,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評(píng)論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了初嘹。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片及汉。...
    茶點(diǎn)故事閱讀 40,865評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖屯烦,靈堂內(nèi)的尸體忽然破棺而出坷随,到底是詐尸還是另有隱情,我是刑警寧澤驻龟,帶...
    沈念sama閱讀 36,527評(píng)論 5 351
  • 正文 年R本政府宣布温眉,位于F島的核電站,受9級(jí)特大地震影響翁狐,放射性物質(zhì)發(fā)生泄漏类溢。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評(píng)論 3 336
  • 文/蒙蒙 一露懒、第九天 我趴在偏房一處隱蔽的房頂上張望闯冷。 院中可真熱鬧,春花似錦懈词、人聲如沸蛇耀。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,699評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)纺涤。三九已至译暂,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間撩炊,已是汗流浹背外永。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,814評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留拧咳,地道東北人象迎。 一個(gè)月前我還...
    沈念sama閱讀 49,299評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像呛踊,于是被迫代替她去往敵國(guó)和親砾淌。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容