|
|
今天在練這首歌，突然想看下歌詞。
歌詞如下：
There’s a lady who’s sure
All that glitters is gold
And she’s buying a stairway to heaven
When she gets there she know
If the stores are all closed
With a word she can get what she came for
Ooh, ooh and she’s buying a stairway to heaven
There’s a sign on the wall
But she wants to be sure
Cause you know sometimes words have two meanings
In a tree by the brook
There’s a songbird who sings
Sometimes all of our thoughts are misgiven
Ooh, it makes me wonder
Ooh, it makes me wonder
There’s a feeling I get when I look to the west
And my spirit is crying for leaving
In my thought I have seen
Rings of smoke through the trees
And the voices of those who stand looking
Ooh, it makes me wonder
Ooh, it makes me wonder
And it’s whispered that soon if we all call the tune
That the piper will lead us to reason
And a new day will dawn for those who stand long
And the forest will echo with laughter
If there’s a bustle in your hedgerow
Don’t be alarmed now
It’s just a spring clean for the May queen
Yes, there are two paths you can go by
But in the long run
There’s still time to change the road you’re on
And it makes me wonder
Your head is humming and it won’t go
In case you don’t know
The piper’s calling you to join him
Dear lady, can you hear the wind blow
And did you know
Your stairway lies on the whispering wind
And as we wind on down the road
Our shadows taller than our soul
There walks a lady we all know
Who shines white light and wants to show
How everything still turns to gold
And if you listen very hard
The tune will come to you at last
When all are one and one is all
To be a rock and not to roll
And she’s buying a stairway to heaven
是不是覺得很難看懂呢。
下面是中文版：
天堂之梯 - 齊柏林飛船合唱團
有一位女士，她相信
凡是閃閃發(fā)亮的都是黃金
她想買一座通往天堂之梯
當(dāng)她到了那兒，她會明白
如果所有的商店都已打烊
她所能想到的字眼來說明她所為何來
她想買一座通往天堂之梯
墻上有則告示
但她想要確定
因為有時候一句話會有兩種涵義
小溪旁的一棵樹上
有只鳥兒在歌唱著
有時候我們的想法不免會受到質(zhì)疑
噢！那不禁使我懷疑
噢！那不禁使我懷疑
向西方望去，一種感覺油然而生
我的靈魂哭喊著要離去
在我的思緒中，我看見了
樹林中煙霧裊繞
以及那些觀望者的心聲
噢！那不禁使我懷疑
噢！那不禁使我懷疑
它低語著，當(dāng)我們呼喚那曲調(diào)
吹笛人將帶領(lǐng)我們回歸理性
新的一天即將破曉，為那些佇立許久的人們
樹林里將回蕩著笑語
如果樹籬里忙忙碌碌
別拉起警報
那是春天在為五月皇后清掃
是的，你有兩條路可以走
在長跑中
你還有時間可以更換路線
那使我心生懷疑
你的腦子里嗡嗡作響，揮之不去
因為你不明白
那是吹笛人在召喚你加入他的行列
親愛的女士，你聽見風(fēng)吹的聲音嗎？
你可曾知道
你的天堂之梯架在低語的風(fēng)中
當(dāng)我們在路上迂回前進
影子高過我們的靈魂
我們都認識的女士在前面走著
她綻放出白光，告訴我們
每樣?xùn)|西仍會變?yōu)辄S金
如果你認真傾聽
那曲調(diào)最后一定會找上你
當(dāng)萬物合一，一即為萬物
成為一塊石頭，卻不會滾動
她想買一座通往天堂之梯
是不是還是很難看懂呢。
下面是轉(zhuǎn)載的分析：
以前的國內(nèi)外文章, 都把歌詞里面講的Piper, 解釋成我們童話里可能很多人讀過的, 有個城市老鼠為患, 引老鼠出城那位”吹笛者”, 認為歌詞寫的就是對世俗的失落感, 希望跟著吹笛者的引導(dǎo)到烏托邦國度去
然而很多人認為這些搖滾樂團, 都是吸毒淫亂又大多功課學(xué)業(yè)最后一名, Led Zeppelin也不例外, 怎么可能有什么高深思想, 頂多是克藥在幻覺中亂寫, 或像很多編詞者講的, 就是當(dāng)時生活發(fā)生什么事就寫下來, 事后也不解釋讓大家去隨便詮釋, 就像Hotel California也是一樣, 有各種解釋, 但Eagles從不去正面回答歌詞在講什么? 我以前解釋過Smoke on the Water, 只是Deep Purple當(dāng)時住旅館發(fā)生火災(zāi), 歌詞只是把那幾天的生活經(jīng)歷寫下來而已
前幾年有一個高科技研究人員, 做了很多學(xué)術(shù)研究論文, 但他很喜歡Stairway to heaven這首歌, 有一天他就想到, 用我研究學(xué)術(shù)的精神, 追根究底去研究出這首歌倒底在講什么? 為什么會寫出那樣的句子和段落, 于是他就去搜集各種相關(guān)資料, 并透過關(guān)系接觸到當(dāng)年在Led Zeppelin身邊的人, 并且去拜訪當(dāng)時寫這首歌時, Led Zeppelin住在團長吉他手Jimmy Page鄉(xiāng)下古堡的那邊村人, 下面就是他研究后的歌詞意義:
英籍的Led Zeppelin成名后, 當(dāng)然有錢了就開始生活揮豪淫亂吸毒(大家都讀過嘻皮時代很多樂團這樣), 吉他手Jimmy Page很喜歡中古世紀的東西, 所以跑去英國北部威爾斯鄉(xiāng)下, 找到一間中古世紀古堡將他買下, 并請團員, 工作人員, 瘋狂女歌迷等都去那邊住, 并且訂做了很多維多利亞時期的服裝, 每天就在里面Home Party做樂幻想是在過中古時代生活, 在當(dāng)?shù)刈兊膼好颜? Jimmy Page稱那古堡頂端就是Heaven, 在上面可以嘹望整個當(dāng)?shù)剜l(xiāng)間風(fēng)光
歌詞中的Lady, 其實是當(dāng)時當(dāng)?shù)氐囊晃粍傠x婚的婦人Erma, 為了生活她開始了包工程生意, Jimmy Page想在古堡外面建一個木造樓梯直通頂上, 就不用讓人在古堡繞來繞去迷路, 這古堡的前主人是一個英國電視名星, 認識這Erma女士, 就把她介紹給Jimmy Page
但這女人跟她的工人, 在搬運木頭材料很粗魯, 在古堡內(nèi)撞壞了很多有價值的古物, Jimmy氣的要死, 寫這首歌的主唱Robert Plant, 認為她是看到這些古物外表舊舊爛爛的, 她根本不識貨, 可能認為只有外表閃亮發(fā)光東西才有價值, 所以歌詞開始寫:
There’s a lady who’s sure all that glitters is gold
And she’s buying a stairway to heaven
但要開始建造木梯時, Erma跟Jimmy說當(dāng)?shù)匚ㄒ坏囊患椅褰鹦欣习迮苋ソ加尾婚_店, 害她都買不到釘子無法開工, Jimmy買這古堡在當(dāng)?shù)刈兠? 跟當(dāng)?shù)刈h員就認識了, 他就請議員對那五金行老板威脅, 叫他馬上開店讓Erma買東西, 所以Robert 歌詞紀錄:
And when she gets there she knows
if the stores are closed.
With a word she can get what she came for. (word意味議員去講的威脅話)
在古堡樓上有個Jimmy的吉他房, 他不喜歡閑雜人進入, 所以在門口貼一個Sign寫: Keep the **** Off”, 但Erma的工人為了要從這房間的窗戶伸手向外做事, 當(dāng)然就進去了, Jimmy當(dāng)時在前院樹上乘涼唱歌(Robert戲稱他是songbird), 看到很氣大吼大叫, 一定是氣她沒看到那個Sign嗎? 是否文字有時有兩種意義看成可以進去嗎? 還是我寫的造成誤導(dǎo)? 所以下段歌詞就是在講這事:
There’s a sign on the wall
but she wants to be sure.
Cause you know sometimes
words have two meanings
In a tree by the brook, there’s a songbird who sings
Sometimes all of our thoughts are misgiven.
在古堡的西邊有一做燒煤發(fā)電廠, 煙囪發(fā)出濃煙圈有礙健康, Robert的肺不好覺得吸的空氣很難過, 所以想離開回倫敦, 所以歌詞寫:
There’s a feeling I get when
I look to the west.
And my spirit is crying for leaving.
In my thoughts I have seen
rings of smoke through the trees
Bass手Johh Paul Jones, 是一個音樂多才多藝的人, 除了跟Led Zeppelin外他也寫了很多通俗流行歌, 網(wǎng)友們爸爸媽媽那代有首名曲”吾愛吾師(To sir with love, 也是同名電影主題曲)就他寫的, 他會各種樂器也會吹笛, 所以Robert都叫他Piper
John Paul Jones其實也覺得古堡生活很無聊, 就把跟他們過來的女歌迷們叫過來, 叫她們組個三部合唱團, 他來教她們唱合唱, 并請當(dāng)?shù)卮迕駚砺? 結(jié)果這些女孩都五音不全, 唱到村民們看的哄堂大笑, 所以Robert 寫:
And the voices of those who stand looking (指女孩們站著看John指揮來唱歌)
And it’s whispered that soon
if we all call the tune. (在說女還都唱不準無法in tune)
Then the piper will lead us to reason (說Piper, 也就是John, 會引導(dǎo)她們唱到能聽)
And a new day will dawn for those who stand long (那些女孩沒耐心, John希望大家有毅力練久些, 能看到美好的明天
And the forest will echo with laughter(村民大嘲笑)
May-Queen是歐美知名電器品牌Maytag, 在當(dāng)年生產(chǎn)的一種大型洗衣機, 通常只有洗衣店, 旅館會買, Jimmy由于如前述訂做了很多中古世紀服裝叫大家穿, 所以要買這種洗衣機, 但當(dāng)?shù)卮迕癯？吹揭路B籬圍上都有亂丟, 想必里面Party的很淫亂, Jimmy的管家對外解釋是他用那臺May-Queen洗太多衣服沒地方掛, 所以才亂掛, 請大家不要驚慌亂猜測, 歌詞就寫到:
If there’s a bustle in your hedgerow
don’t be alarmed now
It’s just a spring clean for the May-Queen.
買這臺大洗衣機時, Jimmy很龜毛, 說花這么多錢萬一不好用怎么辦? 廠家說如果不滿意, 在一個時間內(nèi)可以全額退錢, 所以歌詞是說Jimmy有兩條路可走, 繼續(xù)用或退錢, 而且期限還沒到, 還有時間讓Jimmy換走另一條路, 歌詞就寫:
Yes there are two paths you can go by.
But in the long run.
There’s still time to change the road you’re on
最后Robert Plant和John Paul Jones都住到生活亂七八糟覺得沒意思, 頭嗡嗡作響, John (也就是piper)向Robert提議跟他一起回倫敦, 所以歌詞寫:
Your head is humming and it won’t go- in case you don’t know
The piper’s calling you to join him
他們走之前, 當(dāng)?shù)貋砹艘魂圐埦盹L(fēng), 結(jié)果把那Erma建的木梯吹倒了, 所以歌詞寫到:
Dear lady can you hear the wind blow.
And did you know
your stairway lies on the whispering wind
這Erma由于工程品質(zhì)太差, 馬上倒店做不下去, 她就想去倫敦找其它事做, 她就在路邊搖著一支手電筒想要搭便車, 看誰愿意讓她當(dāng)順風(fēng)車去倫敦, 不巧正好被開車要回倫敦的John和Robert遇到, 就讓她搭上了車, 歌詞就是:
And as we wind on down the road.
Our shadows taller than our soul.
There walks a lady we all know.
Who shines white light
在車上, 愛面子的Erma還在繼續(xù)吹牛說她賺了很多錢, 其實Robert和John心里有數(shù), 所以歌詞寫:
and wants to show.
How everything still turns gold (炫耀她如何點石成金賺到大錢)
下面這句Robert又在車上聊天時大力嘲笑John教那些五音不全的女孩唱歌, 說妳們只要用力仔細聽好, 最后音準就會有, 然后整個合唱才會一體, 歌詞寫:
And if you listen very hard
the tune will come to you at last.
When all are one and one is all (指合唱才會聽起來整齊一體)
最后Robert他到家了, 覺得還是自己家最好, 而且去古堡荒唐的很累了, 所以想要像一顆大石頭一樣坐在家中不想動了, 歌詞就是:
To be a rock and not to roll
=====================================================
但這篇”論文”發(fā)表后, 當(dāng)然很多媒體會去問Robert正不正確, 全世界藝人都討厭八卦, Robert Plant當(dāng)然不會承認那荒唐歲月, 尤其是英國很多成就非凡的老搖滾樂手像Paul McCartney, Elton John等都被女皇策封爵士, 所以年紀大了都很愛面子不愿承認過去的荒唐, Robert Plant也一樣, 說有些部份是對的, 但荒唐的那些都不對
所以如果上面歌詞研究是正確的, 也就跟大多的搖滾名曲一樣, 只是當(dāng)時他們的生活中, 看到什么就寫下來, 別人不了解他們生活的, 根本就不懂亂解釋一通
看完之后我深刻的體會到，不要試圖去深究這些歌詞到底在說什么。。
這個問題源于POJ 2500。由于看錯了題目，我把題意理解成“給出一個圓，上面有數(shù)個點，任取4個點組成四邊形，使得此四邊形面積最大”。
標程給出的方法是O(N^2)，是對于點之間距離固定的情況。
我也想出了一個O(N^2)的算法用于解決任意位置的點的情況。
將點按照順時針排序
假設(shè)四邊形的四個點A, B, C, D。按照順時針方向排序。
按順序枚舉A
按順序枚舉C
B取最接近弧AC中心的點，D同理
在紙上畫畫就可以看出，如果C是遞增的，則BD也是遞增的。
因此C掃了一圈，BD加起來最多也掃兩圈。
枚舉A是O(N)，枚舉C是O(N)，BD均攤下來也是O(N)
所以總復(fù)雜度是O(N^2)
雖然說復(fù)雜度跟標程一樣，但還是TLE了，哥很久沒寫C代碼了，現(xiàn)在比較挫。
floyd算法是一個經(jīng)典的動態(tài)規(guī)劃算法。用通俗的語言來描述的話，首先我們的目標是尋找從點i到點j的最短路徑。從動態(tài)規(guī)劃的角度看問題，我們需要為這個目標重新做一個詮釋（這個詮釋正是動態(tài)規(guī)劃最富創(chuàng)造力的精華所在），floyd算法加入了這個概念
Ak(i,j)：表示從i到j(luò)中途不經(jīng)過索引比k大的點的最短路徑。
這個限制的重要之處在于，它將最短路徑的概念做了限制，使得該限制有機會滿足迭代關(guān)系，這個迭代關(guān)系就在于研究：假設(shè)Ak(i,j)已知，是否可以借此推導(dǎo)出Ak-1(i,j)。
假設(shè)我現(xiàn)在要得到Ak(i,j)，而此時Ak(i,j)已知，那么我可以分兩種情況來看待問題：1. Ak(i,j)沿途經(jīng)過點k；2. Ak(i,j)不經(jīng)過點k。如果經(jīng)過點k，那么很顯然，Ak(i,j) = Ak-1(i,k) + Ak-1(k,j)，為什么是Ak-1呢？因為對(i,k)和(k,j)，由于k本身就是源點（或者說終點），加上我們求的是Ak(i,j)，所以滿足不經(jīng)過比k大的點的條件限制，且已經(jīng)不會經(jīng)過點k，故得出了Ak-1這個值。那么遇到第二種情況，Ak(i,j)不經(jīng)過點k時，由于沒有經(jīng)過點k，所以根據(jù)概念，可以得出Ak(i,j)=Ak-1(i,j)。現(xiàn)在，我們確信有且只有這兩種情況---不是經(jīng)過點k，就是不經(jīng)過點k，沒有第三種情況了，條件很完整，那么是選擇哪一個呢？很簡單，求的是最短路徑，當(dāng)然是哪個最短，求取哪個，故得出式子：
Ak(i,j) = min( Ak-1(i,j), Ak-1(i,k) + Ak-1(k,j) )
因此floyd的最外層循環(huán)： for (k = 0; k < n; k++) ... 就是分別求出 A0(i,j), A1(i,j), ..., An(i,j) 我屢次寫錯floyd的程序，今天又寫錯一次。。盡管它很短，但原理真的很牛比。 只要知道了原理，就不會再寫錯了！
BridgeWan是淘寶上最便宜的教育網(wǎng)VPN。只有Windows的客戶端。
首先，在Windows下抓包得到了一點信息。
發(fā)現(xiàn)用的是PPTP協(xié)議。CHAP驗證方式。用戶名是一樣的。
但是在linux試一下直接連接，發(fā)現(xiàn)密碼錯誤，也就是說密碼改了。
在PPTP連接之前，它還發(fā)起了幾個HTTP的請求。
除了獲取程序界面上顯示的網(wǎng)頁之外，還有可能是請求了一些特別的東西，用來生成密碼。
總之它密碼改了就對了。
試圖用Wine運行，結(jié)果報了幾個錯，就是說有的函數(shù)沒實現(xiàn)。
注意到了RasDial這個函數(shù)，Wine沒有實現(xiàn)。
去msdn查了一下，是PPTP撥號相關(guān)的函數(shù)，而且它的參數(shù)里，包含了密碼！
這下好辦！首先把Wine的源碼下載下來，然后查找到RasDialA函數(shù)。
加一句話把密碼打印出來。編譯運行。
本來想著它動態(tài)生成密碼，每次都不一樣。
但是發(fā)現(xiàn)每次都一樣的。。這樣就更省事拉！
我用的是kvpnc這個客戶端，配置蠻方便的。
注意：驗證方式選擇MSCHAP，取消MPPE。
有一個這樣的小游戲： 多個不同顏色的方塊位于一列，你每次可以消除一片連續(xù)的相同顏色的方塊，并獲得得分｛連續(xù)方塊的個數(shù)^2｝。 消除完后右邊的方塊移動過來。 問，怎樣玩才能使得分最高？ 這是一道黑書上面的題目。我想了n久想不出來。。 黑書的解法是動態(tài)規(guī)劃，時間復(fù)雜度為O(N^4)，空間復(fù)雜度為O(N^3)。 覺得挺有意思的，就把它的方法實現(xiàn)了一下。
# Block Game
blocks = [(1,2), (2,4), (3,5), (1,2), (3,6), (1,9), (2,10)]
best = {}
choose = {}
def sqr(x):
return x*x
def dfs(i, j, k):
if j < i:
return 0
if (i, j, k) in best:
return best[(i, j, k)]
m = [(sqr(k + blocks[j][1]) + dfs(i, j - 1, 0), j)]
for p in range(i, j):
if blocks[p][0] == blocks[j][0]:
m += [(dfs(i, p, k + blocks[j][1]) + dfs(p + 1, j - 1, 0), p)]
best[(i, j, k)], choose[(i, j, k)] = max(m)
return best[(i, j, k)]
def show(i, j, k, s):
if j < i:
return
#print 'show', i, j, k, blocks
c = choose[(i, j, k)]
if c == j:
s += sqr(blocks[c][1])
print blocks, 'remove', c, ':', blocks[c], 'score', s
del blocks[c]
show(i, j - 1, 0, s)
else:
show(c + 1, j - 1, 0, s)
v = blocks[c + 1][1]
blocks[c] = (blocks[c][0], blocks[c][1] + v)
del blocks[c + 1]
show(i, c, v, s)
dfs(0, len(blocks) - 1, 0)
show(0, len(blocks) - 1, 0, 0)
通常的思路是O(N^3) 但可以有小小優(yōu)化： 一。先排序 二。枚舉i, j, k的時候，固定i的時候，j和k分別從左從右掃描數(shù)組，直到兩個碰到為止。 三。對于每個i，k從右掃描的開始位置是遞減的。 然后就有了下面的小程序：
 #include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
int N = 10;
int K = 5;
  int arr[] =  {1, 2, 5, 4, 5, 10, 2, 3, 5, 1};
int main()
{
 int a, b, c, i;
sort(arr, arr + N);
c = N - 1;
  for (a = 0; a < c; a++) {
for (b = a + 1; b < c; b++) {
while (c >= 0 && arr[a] + arr[b] + arr[c] > K)
c--;
for (i = c; b < i; b++) {
while (i >= 0 && arr[a] + arr[b] + arr[i] > K)
i--;
if (i >= 0 && arr[a] + arr[b] + arr[i] == K)
printf("%d %d %d\n", arr[a], arr[b], arr[i]);
 }
}
}
return 0;
 }
這題需要動動腦子，可以找到O(NM)的算法。 但是表述很麻煩，還是看代碼吧。。
#include <stdio.h>
#include <string.h>
int N, M;
int end[1024], sum[1024];
char mat[1024][1024];
int main()
{
int i, j, k, v, ans;
while (scanf("%d%d", &N, &M) != EOF) {
memset(end, 0, sizeof(end));
memset(sum, 0, sizeof(sum));
for (i = 0; i < N; i++)
scanf("%s", mat[i]);
ans = 0;
for (i = 0; i < N; i++) {
for (j = 0; j < M; j++) {
if (mat[i][j] == '1' && end[j] <= i) {
for (k = i; k < N && mat[k][j] == '1'; k++)
sum[k]++;
end[j] = k;
}
}
for (j = i; j < N && sum[j]; j++) {
v = (j - i + 1) * sum[j];
if (v > ans)
ans = v;
}
}
printf("%d\n", ans);
}
return 0;
}
這題用普通的寬搜可以解決。 關(guān)鍵問題在于由于是寬搜，隊列里面的元素的step字段必須是從前往后遞增的。 在碰到一大堆聯(lián)通的'X'之后，必須另外進行一次遍歷，同時的把這些'X'插入到隊列中，保持step字段的遞增。 這樣做復(fù)雜度并不改變。
#include <stdio.h>
#define NR 1024
struct node {
short x, y;
int s;
};
char map[NR][NR];
struct node Q[NR*NR];
int W, H;
int sx, sy, ex, ey;
int h, t, h2;
inline int inrange(short x, short y)
{
return x >= 0 && x < W && y >= 0 && y < H;
}
inline void push2(short x, short y, int s)
{
if (!inrange(x, y))
return ;
if (map[y][x] == 'X' || map[y][x] == '.') {
// printf("p2 %d %d %d\n", x, y, s);
Q[t].x = x;
Q[t].y = y;
if (map[y][x] == '.') {
map[y][x] = '#';
Q[t].s = s + 1;
} else {
map[y][x] = '$';
Q[t].s = s;
}
t++;
}
}
inline void bfs2(short x, short y, int s)
{
struct node n;
push2(x, y, s);
h2 = t - 1;
while (h2 != t) {
n = Q[h2++];
if (map[n.y][n.x] == '#')
continue;
push2(n.x - 1, n.y, n.s);
push2(n.x + 1, n.y, n.s);
push2(n.x, n.y - 1, n.s);
push2(n.x, n.y + 1, n.s);
}
}
inline void push(short x, short y, int s)
{
if (!inrange(x, y))
return ;
if (map[y][x] == '.') {
// printf("p %d %d %d\n", x, y, s);
Q[t].x = x;
Q[t].y = y;
Q[t].s = s + 1;
t++;
map[y][x] = '@';
} else if (map[y][x] == 'X')
bfs2(x, y, s);
}
inline int bfs()
{
struct node n;
t = h = 0;
push(sx, sy, 0);
while (t != h) {
n = Q[h++];
if (n.x == ex && n.y == ey)
return n.s;
if (map[n.y][n.x] == '$')
continue;
push(n.x - 1, n.y, n.s);
push(n.x + 1, n.y, n.s);
push(n.x, n.y - 1, n.s);
push(n.x, n.y + 1, n.s);
}
}
int main()
{
int i;
while (scanf("%d%d", &H, &W), H) {
for (i = 0; i < H; i++)
scanf("%s", map[i]);
scanf("%d%d%d%d", &sy, &sx, &ey, &ex);
sy--; sx--; ey--; ex--;
printf("%d\n", bfs());
}
return 0;
}
這題的目的是，通過一系列交換，讓矩陣中A[i, i] (1 <= i <= N)的值全為1。 首先要明確： 如果某行或者某列全是0。那怎么換都沒辦法的。 否則，一定能換出來。 這個動動腦子想一下可以明白的。 其次要明確：只交換行或者只交換列都是可以換出來的。 這個動動腦子想一下也可以明白的。 明確了這兩點，這問題就變成了二分圖的匹配問題。 二分圖左邊的節(jié)點為每一行的行號 二分圖右邊的節(jié)點為每一行中出現(xiàn)的“1”對應(yīng)的列號 這樣用匈牙利算法就可以匹配了。
#include <stdio.h>
#include <string.h>
#define NR 128
int N;
int mat[NR][NR];
int res[NR];
char vis[NR];
int dfs(int i)
{
int j;
for (j = 1; j <= N; j++) {
if (mat[i][j] && !vis[j]) {
vis[j] = 1;
if (!res[j] || dfs(res[j])) {
res[j] = i;
return 1;
}
}
}
return 0;
}
int solve()
{
int i, j, k, c, t, m;
static int a[NR], b[NR];
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
scanf("%d", &mat[i][j]);
memset(res, 0, sizeof(res));
for (i = 1; i <= N; i++) {
memset(vis, 0, sizeof(vis));
if (!dfs(i))
return 0;
}
c = 0;
for (j = 1; j <= N; j++) {
m = j;
for (k = j; k <= N; k++)
if (res[k] <= res[m])
m = k;
if (m != j) {
a[c] = m;
b[c] = j;
c++;
t = res[m];
res[m] = res[j];
res[j] = t;
}
}
printf("%d\n", c);
for (i = 0; i < c; i++)
printf("C %d %d\n", a[i], b[i]);
return 1;
}
int main()
{
while (scanf("%d", &N) != EOF)
if (!solve())
printf("-1\n");
return 0;
}
這題算是半道水題了。但代碼實現(xiàn)還是有點麻煩，所以還是值得一寫。 同一堆的方塊位于同一個集合。 每個方塊保存一個值：距離底部的高度 作為集合根部節(jié)點的方塊保存一個值：這堆方塊的高度 在并查集的合并以及查找過程中需要維護這兩個值。
#include <stdio.h>
#define N 65536
int P, parent[N], pos[N], top[N], stk[N];
int fs(int idx)
{
int i;
for (i = 0; parent[idx] != idx; i++) {
stk[i] = idx;
idx = parent[idx];
}
for (i--; i >= 0; i--) {
pos[stk[i]] += pos[parent[stk[i]]];
parent[stk[i]] = idx;
}
return idx;
}
int main()
{
char op[16];
int x, y, rx, ry;
for (x = 0; x < N; x++) {
top[x] = 1;
parent[x] = x;
}
scanf("%d", &P);
while (P--) {
scanf("%s", op);
if (*op == 'M') {
scanf("%d%d", &x, &y);
rx = fs(x);
ry = fs(y);
if (rx != ry) {
parent[rx] = ry;
pos[rx] = top[ry];
top[ry] += top[rx];
}
} else {
scanf("%d", &x);
fs(x);
printf("%d\n", pos[x]);
}
}
return 0;
}
|