糯米

TI DaVinci, gstreamer, ffmpeg
随笔 - 167, 文章 - 0, 评论 - 47, 引用 - 0
数据加载中……

[转]Stairway to Heaven 歌词分析

今天在练这首歌,突然想看下歌词。
歌词如下:

      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 

是不是觉得很难看懂呢。
下面是中文版:

      天堂之梯 - 齐柏林飞船合唱团 
   
  有一位女士,她相信 
  凡是闪闪发亮的都是黄金 
  她想买一座通往天堂之梯 
  当她到了那儿,她会明白 
  如果所有的商店都已打烊 
  她所能想到的字眼来说明她所为何来 
  她想买一座通往天堂之梯 
   
  墙上有则告示 
  但她想要确定 
  因为有时候一句话会有两种涵义 
  小溪旁的一棵树上 
  有只鸟儿在歌唱着 
  有时候我们的想法不免会受到质疑 
   
  噢!那不禁使我怀疑 
  噢!那不禁使我怀疑 
   
  向西方望去,一种感觉油然而生 
  我的灵魂哭喊着要离去 
  在我的思绪中,我看见了 
  树林中烟雾袅绕 
  以及那些观望者的心声 
   
  噢!那不禁使我怀疑 
  噢!那不禁使我怀疑 
   
  它低语着,当我们呼唤那曲调 
  吹笛人将带领我们回归理性 
  新的一天即将破晓,为那些伫立许久的人们 
  树林里将回荡着笑语 
   
  如果树篱里忙忙碌碌 
  别拉起警报 
  那是春天在为五月皇后清扫 
  是的,你有两条路可以走 
  在长跑中 
  你还有时间可以更换路线 
   
  那使我心生怀疑 
   
  你的脑子里嗡嗡作响,挥之不去 
  因为你不明白 
  那是吹笛人在召唤你加入他的行列 
   
  亲爱的女士,你听见风吹的声音吗? 
  你可曾知道 
  你的天堂之梯架在低语的风中 
   
  当我们在路上迂回前进 
  影子高过我们的灵魂 
  我们都认识的女士在前面走着 
  她绽放出白光,告诉我们 
  每样东西仍会变为黄金 
  如果你认真倾听 
  那曲调最后一定会找上你 
  当万物合一,一即为万物 
  成为一块石头,却不会滚动 
   
  她想买一座通往天堂之梯 



是不是还是很难看懂呢。
下面是转载的分析:

以前的国内外文章, 都把歌词里面讲的Piper, 解释成我们童话里可能很多人读过的, 有个城市老鼠为患, 引老鼠出城那位”吹笛者”, 认为歌词写的就是对世俗的失落感, 希望跟着吹笛者的引导到乌托邦国度去 
   
  然而很多人认为这些摇滚乐团, 都是吸毒淫乱又大多功课学业最后一名, Led Zeppelin也不例外, 怎么可能有什么高深思想, 顶多是克药在幻觉中乱写, 或像很多编词者讲的, 就是当时生活发生什么事就写下来, 事后也不解释让大家去随便诠释, 就像Hotel California也是一样, 有各种解释, 但Eagles从不去正面回答歌词在讲什么? 我以前解释过Smoke on the Water, 只是Deep Purple当时住旅馆发生火灾, 歌词只是把那几天的生活经历写下来而已 
   
  前几年有一个高科技研究人员, 做了很多学术研究论文, 但他很喜欢Stairway to heaven这首歌, 有一天他就想到, 用我研究学术的精神, 追根究底去研究出这首歌倒底在讲什么? 为什么会写出那样的句子和段落, 于是他就去搜集各种相关资料, 并透过关系接触到当年在Led Zeppelin身边的人, 并且去拜访当时写这首歌时, Led Zeppelin住在团长吉他手Jimmy Page乡下古堡的那边村人, 下面就是他研究后的歌词意义: 
   
  英籍的Led Zeppelin成名后, 当然有钱了就开始生活挥豪淫乱吸毒(大家都读过嘻皮时代很多乐团这样), 吉他手Jimmy Page很喜欢中古世纪的东西, 所以跑去英国北部威尔斯乡下, 找到一间中古世纪古堡将他买下, 并请团员, 工作人员, 疯狂女歌迷等都去那边住, 并且订做了很多维多利亚时期的服装, 每天就在里面Home Party做乐幻想是在过中古时代生活, 在当地变的恶名昭彰! Jimmy Page称那古堡顶端就是Heaven, 在上面可以嘹望整个当地乡间风光 
   
  歌词中的Lady, 其实是当时当地的一位刚离婚的妇人Erma, 为了生活她开始了包工程生意, Jimmy Page想在古堡外面建一个木造楼梯直通顶上, 就不用让人在古堡绕来绕去迷路, 这古堡的前主人是一个英国电视名星, 认识这Erma女士, 就把她介绍给Jimmy Page 
   
  但这女人跟她的工人, 在搬运木头材料很粗鲁, 在古堡内撞坏了很多有价值的古物, Jimmy气的要死, 写这首歌的主唱Robert Plant, 认为她是看到这些古物外表旧旧烂烂的, 她根本不识货, 可能认为只有外表闪亮发光东西才有价值, 所以歌词开始写: 
   
  There’s a lady who’s sure all that glitters is gold 
  And she’s buying a stairway to heaven 
   
  但要开始建造木梯时, Erma跟Jimmy说当地唯一的一家五金行老板跑去郊游不开店, 害她都买不到钉子无法开工, Jimmy买这古堡在当地变名人, 跟当地议员就认识了, 他就请议员对那五金行老板威胁, 叫他马上开店让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的工人为了要从这房间的窗户伸手向外做事, 当然就进去了, Jimmy当时在前院树上乘凉唱歌(Robert戏称他是songbird), 看到很气大吼大叫, 一定是气她没看到那个Sign吗? 是否文字有时有两种意义看成可以进去吗? 还是我写的造成误导? 所以下段歌词就是在讲这事: 
   
  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. 
   
  在古堡的西边有一做烧煤发电厂, 烟囱发出浓烟圈有碍健康, 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外他也写了很多通俗流行歌, 网友们爸爸妈妈那代有首名曲”吾爱吾师(To sir with love, 也是同名电影主题曲)就他写的, 他会各种乐器也会吹笛, 所以Robert都叫他Piper 
   
  John Paul Jones其实也觉得古堡生活很无聊, 就把跟他们过来的女歌迷们叫过来, 叫她们组个三部合唱团, 他来教她们唱合唱, 并请当地村民来听, 结果这些女孩都五音不全, 唱到村民们看的哄堂大笑, 所以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, 会引导她们唱到能听) 
  And a new day will dawn for those who stand long (那些女孩没耐心, John希望大家有毅力练久些, 能看到美好的明天 
  And the forest will echo with laughter(村民大嘲笑) 
   
  May-Queen是欧美知名电器品牌Maytag, 在当年生产的一种大型洗衣机, 通常只有洗衣店, 旅馆会买, Jimmy由于如前述订做了很多中古世纪服装叫大家穿, 所以要买这种洗衣机, 但当地村民常看到衣服连篱围上都有乱丢, 想必里面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很龟毛, 说花这么多钱万一不好用怎么办? 厂家说如果不满意, 在一个时间内可以全额退钱, 所以歌词是说Jimmy有两条路可走, 继续用或退钱, 而且期限还没到, 还有时间让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 
   
  他们走之前, 当地来了一阵龙卷风, 结果把那Erma建的木梯吹倒了, 所以歌词写到: 
   
  Dear lady can you hear the wind blow. 
  And did you know 
  your stairway lies on the whispering wind 
   
  这Erma由于工程品质太差, 马上倒店做不下去, 她就想去伦敦找其它事做, 她就在路边摇着一支手电筒想要搭便车, 看谁愿意让她当顺风车去伦敦, 不巧正好被开车要回伦敦的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还在继续吹牛说她赚了很多钱, 其实Robert和John心里有数, 所以歌词写: 
   
  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 
   
   
  ===================================================== 
  但这篇”论文”发表后, 当然很多媒体会去问Robert正不正确, 全世界艺人都讨厌八卦, Robert Plant当然不会承认那荒唐岁月, 尤其是英国很多成就非凡的老摇滚乐手像Paul McCartney, Elton John等都被女皇策封爵士, 所以年纪大了都很爱面子不愿承认过去的荒唐, Robert Plant也一样, 说有些部份是对的, 但荒唐的那些都不对 
   
  所以如果上面歌词研究是正确的, 也就跟大多的摇滚名曲一样, 只是当时他们的生活中, 看到什么就写下来, 别人不了解他们生活的, 根本就不懂乱解释一通 

看完之后我深刻的体会到,不要试图去深究这些歌词到底在说什么。。

posted @ 2011-01-23 18:30 糯米 阅读(1882) | 评论 (1)编辑 收藏

[小程序]给出一个圆,上面有数个点,任取4个点组成四边形,使得此四边形面积最大

这个问题源于POJ 2500。由于看错了题目,我把题意理解成“给出一个圆,上面有数个点,任取4个点组成四边形,使得此四边形面积最大”。
标程给出的方法是O(N^2),是对于点之间距离固定的情况。
我也想出了一个O(N^2)的算法用于解决任意位置的点的情况。

将点按照顺时针排序
假设四边形的四个点A, B, C, D。按照顺时针方向排序。
按顺序枚举A
   按顺序枚举C
      B取最接近弧AC中心的点,D同理

在纸上画画就可以看出,如果C是递增的,则BD也是递增的。
因此C扫了一圈,BD加起来最多也扫两圈。
枚举A是O(N),枚举C是O(N),BD均摊下来也是O(N)
所以总复杂度是O(N^2)

虽然说复杂度跟标程一样,但还是TLE了,哥很久没写C代码了,现在比较挫。

posted @ 2011-01-15 11:07 糯米 阅读(793) | 评论 (0)编辑 收藏

[转] Floyd 算法原理

    floyd算法是一个经典的动态规划算法。用通俗的语言来描述的话,首先我们的目标是寻找从点i到点j的最短路径。从动态规划的角度看问题,我们需要为这个目标重新做一个诠释(这个诠释正是动态规划最富创造力的精华所在),floyd算法加入了这个概念

    Ak(i,j):表示从i到j中途不经过索引比k大的点的最短路径

    这个限制的重要之处在于,它将最短路径的概念做了限制,使得该限制有机会满足迭代关系,这个迭代关系就在于研究:假设Ak(i,j)已知,是否可以借此推导出Ak-1(i,j)。

    假设我现在要得到Ak(i,j),而此时Ak(i,j)已知,那么我可以分两种情况来看待问题:1. Ak(i,j)沿途经过点k;2. Ak(i,j)不经过点k。如果经过点k,那么很显然,Ak(i,j) = Ak-1(i,k) + Ak-1(k,j),为什么是Ak-1呢?因为对(i,k)和(k,j),由于k本身就是源点(或者说终点),加上我们求的是Ak(i,j),所以满足不经过比k大的点的条件限制,且已经不会经过点k,故得出了Ak-1这个值。那么遇到第二种情况,Ak(i,j)不经过点k时,由于没有经过点k,所以根据概念,可以得出Ak(i,j)=Ak-1(i,j)。现在,我们确信有且只有这两种情况---不是经过点k,就是不经过点k,没有第三种情况了,条件很完整,那么是选择哪一个呢?很简单,求的是最短路径,当然是哪个最短,求取哪个,故得出式子:

    Ak(i,j) = min( Ak-1(i,j), Ak-1(i,k) + Ak-1(k,j) )


因此floyd的最外层循环:
for (k = 0; k < n; k++) ...
就是分别求出 A0(i,j), A1(i,j), ..., An(i,j)
我屡次写错floyd的程序,今天又写错一次。。尽管它很短,但原理真的很牛比。
只要知道了原理,就不会再写错了!

posted @ 2011-01-15 10:56 糯米 阅读(5061) | 评论 (0)编辑 收藏

在Linux下使用BridgeWan代理

BridgeWan是淘宝上最便宜的教育网VPN。只有Windows的客户端。

首先,在Windows下抓包得到了一点信息。
发现用的是PPTP协议。CHAP验证方式。用户名是一样的。
但是在linux试一下直接连接,发现密码错误,也就是说密码改了。
在PPTP连接之前,它还发起了几个HTTP的请求。
除了获取程序界面上显示的网页之外,还有可能是请求了一些特别的东西,用来生成密码。
总之它密码改了就对了。

试图用Wine运行,结果报了几个错,就是说有的函数没实现。
注意到了RasDial这个函数,Wine没有实现。
去msdn查了一下,是PPTP拨号相关的函数,而且它的参数里,包含了密码!

这下好办!首先把Wine的源码下载下来,然后查找到RasDialA函数。
加一句话把密码打印出来。编译运行。

本来想着它动态生成密码,每次都不一样。
但是发现每次都一样的。。这样就更省事拉!

我用的是kvpnc这个客户端,配置蛮方便的。
注意:验证方式选择MSCHAP,取消MPPE。

posted @ 2011-01-07 19:56 糯米 阅读(601) | 评论 (1)编辑 收藏

小程序:消除方块游戏

有一个这样的小游戏:

多个不同颜色的方块位于一列,你每次可以消除一片连续的相同颜色的方块,并获得得分{连续方块的个数^2}。
消除完后右边的方块移动过来。
问,怎样玩才能使得分最高?

这是一道黑书上面的题目。我想了n久想不出来。。
黑书的解法是动态规划,时间复杂度为O(N^4),空间复杂度为O(N^3)。
觉得挺有意思的,就把它的方法实现了一下。

# 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)

        

posted @ 2010-11-23 16:32 糯米 阅读(862) | 评论 (0)编辑 收藏

小程序:给出n个数,如何找出三个数,它们的和等于k

通常的思路是O(N^3)
但可以有小小优化:
一。先排序
二。枚举i, j, k的时候,固定i的时候,j和k分别从左从右扫描数组,直到两个碰到为止。
三。对于每个i,k从右扫描的开始位置是递减的。

然后就有了下面的小程序:

#include <stdio.h>
#include 
<iostream>
#include 
<algorithm>

using namespace std;

int N = 10;
int K = 5;
int arr[] = {12545102351};

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;
}


posted @ 2010-11-21 23:10 糯米 阅读(391) | 评论 (0)编辑 收藏

HDU 2830 Matrix Swapping II 动态规划

这题需要动动脑子,可以找到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, 
0sizeof(end));
        memset(sum, 
0sizeof(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;
}

posted @ 2010-10-25 22:19 糯米 阅读(269) | 评论 (0)编辑 收藏

HDU 2822 Dogs 宽搜

这题用普通的宽搜可以解决。
关键问题在于由于是宽搜,队列里面的元素的step字段必须是从前往后递增的。
在碰到一大堆联通的'X'之后,必须另外进行一次遍历,同时的把这些'X'插入到队列中,保持step字段的递增。
这样做复杂度并不改变。

#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;
}

posted @ 2010-10-25 22:06 糯米 阅读(257) | 评论 (0)编辑 收藏

HDU 2819 Swap 二分图的最大匹配

这题的目的是,通过一系列交换,让矩阵中A[i, i] (1 <= i <= N)的值全为1。
首先要明确:
如果某行或者某列全是0。那怎么换都没办法的。
否则,一定能换出来。
这个动动脑子想一下可以明白的。

其次要明确:只交换行或者只交换列都是可以换出来的。
这个动动脑子想一下也可以明白的。

明确了这两点,这问题就变成了二分图的匹配问题。
二分图左边的节点为每一行的行号
二分图右边的节点为每一行中出现的“1”对应的列号
这样用匈牙利算法就可以匹配了。

#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, 
0sizeof(res));
    
for (i = 1; i <= N; i++{
        memset(vis, 
0sizeof(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;
}

posted @ 2010-10-25 22:01 糯米 阅读(902) | 评论 (1)编辑 收藏

HDU 2818 Building Block 并查集

这题算是半道水题了。但代码实现还是有点麻烦,所以还是值得一写。
同一堆的方块位于同一个集合。
每个方块保存一个值:距离底部的高度
作为集合根部节点的方块保存一个值:这堆方块的高度
在并查集的合并以及查找过程中需要维护这两个值。

#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;
}

posted @ 2010-10-25 21:50 糯米 阅读(530) | 评论 (0)编辑 收藏

仅列出标题
共17页: 1 2 3 4 5 6 7 8 9 Last