追忆似水流年

N coins lay linear. Two men are taking them in turn. They can take one coin or adjacent two per time.

1. The one who takes the last coin is winner. Please analyze the strategy.

Partitioning invariant
move from left to find an element that is not less
move from right to find an element that is not greater
stop if pointers have crossed
exchange
if left element equal, exchange to left end
if right element equal, exchange to right end
Partitioning invariant
Swap equals to center after partition
KEY FEATURES
always uses N-1 (three-way) compares
no extra overhead if no equal keys
only one “extra” exchange per equal

suppose there is an array A[N] of N numbers. We have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1].

Solve it without division operator and in O(n).

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++


In C#:

    static int[] array_multiplier( int[] inp)
    {
        int[] x = new int[inp.Length];
        
        x[0] = 1;
        for (int i = 1; i < x.Length; ++i) {
            x[i] = x[i-1] * inp[i-1];
        }
        
        int[] y = new int[inp.Length];
        
        y[y.Length-1] = 1;
        for (int i = y.Length-2; i >= 0; --i) {
            y[i] = y[i+1] * inp[i+1];
        }
        
        int[] output = new int[inp.Length];
        for (int i = 0; i < output.Length; ++i) {
            output[i] = x[i] * y[i];
        }
        
        return output;
    }

我是一工薪族，以下是本人多年装b的一些肤浅经验，我把它们写出来与工薪阶层的其他装b爱好者们分享，希望通过此文起到抛砖引玉的作用，以便与大家互通有无彼此借鉴取长补短，在今后的工作和生活中更加求真务实勤学苦练，创造性地装b。白领、富豪之流的生活离我很远，我不知道人家的b怎么装，即便知道我也装不象，毕竟经济基础决定上层建筑，没有超越常人的智慧不要试图跨越式装b，以免装b不成反被x。 　　一．音乐 　　说到装b咋能不谈音乐捏，这可是装b的重要道具啊！ 　　音乐在装b工作中我认为有两个要点需要掌握：1.对于过分流行、红得发紫的音乐不听、不唱、不评论、装没听说过；2.不轻易在人前暴露自己喜欢什么样的音乐，以免被x。 　　对于第一条，我们以前一段红得发紫的《老鼠爱大米》为例说明：我感觉喜欢《老鼠爱大米》的人——我说的是喜欢它的人，一听就讨厌的人不在讨论范围——可分4个境界： 　　①最低，听人推荐后下载了这首歌，狂喜欢，并疯狂地向身边的朋友推荐，推荐过程中自尊心间或遭到打击，被骂“土鳖”、“俗人”次数若干； 　　②听人推荐或自己发现并下载了这首歌，喜欢，但知道这首歌已经臭了街了，已经是上不了台面的东西了，不复再听，更不与人对此探讨交流，当有最低境界者①试图与自己交流对《老鼠爱大米》的感受时嗤之以鼻：“行了行了，歇菜吧你个土鳖，啥破歌啊你还听，我从来不听这种破玩意儿，俗得要命！要不怎么都说国人素质亟待提高呢……”打击①中主人公的便是此人； 　　③听人推荐或自己发现后下载了这首歌，一听之下，喜欢，结合此歌的流行程度，怕被打击或鄙视，将其删除，某场合有人提及此歌时，佯作不知：“没听过，好听吗？”如果碰巧有mp3或手机能放这首歌，作恍然大悟状：“噢，这歌啊，听过听过，想不听都不行，马路上但凡能闹点动静的喇叭都在放！”作为自身修养的体现，到此赶紧打住，点到为止，别再穷追猛打了，我一向认为②中主人公的那种贬低别人品位的行为并不能有效地提升自身形象，反倒暴露了自己的低素质，一个一味试图提升自身形象而不懂得尊重别人的人不可能是一个成功的装b犯。 　　④最高，听人推荐或自己发现并下载了这首歌，一听之下，一般喜欢，不考虑此歌的流行程度，按照自己的喜欢程度决定是否将它在自己的mp3里拷入或删除，在与人聊天时也能平静客观地探讨这首歌的创作得失，不考虑听它、谈论它在别人心目中的形象是时尚还是庸俗，同时本能地不向与自己讨论《老鼠爱大米》的人介绍自己家里收藏的古典音乐cd或打口cd。 　　以上四个境界不知你是哪个，我想大多数人能做到③的境界已然不错，看看猫扑音乐论坛中那些对《老鼠爱大米》、《两只蝴蝶》、《求佛》、《狼爱上羊》的流行现象痛心疾首的网友多属于②的境界——惟恐别人不知道自己的品位超凡脱俗，对听烂歌的“群众”哀其不幸、怒其不争、深表同情，以提高全民族音乐欣赏水平和唤醒愚昧民众于庸俗音乐之中为己任，一派卓尔不群睥睨众生的优越感。其实他们也就从①那里找那么点可怜的优越感罢了，在我心目中，率性而为天真淳朴的①倒更可爱些。 　　真正能象第④类人那样低调内敛、宠辱不惊的人毕竟是少数，他们之所以受我崇拜，不是胜在品位超越于我，而是胜在那颗海纳百川的宽容的心和视旁人鄙夷目光如无物的超脱（主要来自②）。曾见过一帖子探讨“你是否仍有勇气听卡带随身听？”有人说：“如果在地铁里有一位衣着整齐男士众目睽睽之下从容不迫地从自己的包包里取出随身听、开仓、将磁带手动反面、关仓、按下play……我感觉，走出地铁，此人必能羽化成仙！”不怕您笑话，我也曾经试图做第④类人，但是每当我发现自己又在与②争执时，我赫然惊醒：我又失败了，我的境界还差得很远！这也是我讲第二个要点的原因：不要轻易在人前表述自己喜欢什么样的音乐，以免被第②类人x，在你忍不住反x之时，你已耽误了自己的装b大业。 　　（写完了《装b指南之音乐篇》，我暗自叫苦，写的太长了，一些原本打算写入结尾的东西都忍不住写在音乐篇里了，典型的没城府，被窝里捂不住个热p！于是这篇东西难免虎头蛇尾） 　　二．文学 　　文学和音乐异曲同工，只是在文学方面装b要尽量避免主动跟人家谈文学，要知道早在十几年前文学青年已经约等于sb青年了。 　　另外，最好能硬着头皮看一两本一般人没耐心看完的书，以体现装b爱好者的不凡追求，那就是：“不听是个人就听的音乐，不看是个人就看的书；要听就听那不是人听的音乐，要看就看那不是人看的书！”比如《生命中不能承受之轻》、《源氏物语》、《一生》、《酒吧长谈》、《尤利西斯》什么的，不为从中寻求什么阅读的乐趣——当然也不可能有什么乐趣——只为聊作谈资，以备不时只需。当然说起这些作品来，也要有个客观的态度，你只需装作不经意地暗示对方你曾经通读过这样的书就可以了，足以令一部分初级装b选手刮目相看，千万别提什么从阅读中悟出人生真谛或文学技巧之类的东东——过了！ 　　本计划写写电影方面，不过和文学音乐太相似了，了无新意，不写也罢，有兴趣者参照前两节即可。 　　三．电视 　　别跟人家谈论电视节目，除了科教类节目如今的电视节目从小燕子到大肠紧，从智慧树到夕阳红，从新闻联播到东方时空，无一例外地都是些上不了台面的狗肉包子。如今在一些沿海的能代表先进文化前进方向的城市里，连四十五岁以上的家庭主妇都开始在网上看《越狱》和《豪斯医生》了，您还好意思噙着泪花跟人家探讨大长今的命运么？ 　　四．香烟 　　如果你抽烟，收起你的zippo吧，十几年前在中国大陆用zippo那是真牛b，但，此一时彼一时，十几年过去了，当年的牛b道具今天已然臭了街。如今的民工兄弟都开始用zippo点烟了，还能跟你讲上一段zippo的历史，而且人家的电油也和你一样只去zippo专卖店买。 　　如果忍不住想与众不同而且又豁得出去钱，去买个几千块钱的督彭或登喜路吧；如果实在舍不得自己那血汗钱，就用气体打火机或者火柴算了，总好过zippo；还有一种既够拽又省银子的好办法——钻木取火——不过技术含量太高了。 　　也许某天的饭局上有不长眼的当着你的面卖弄自己的zippo，只需将火机拿过来看看底座上的生产年代，十有八九是2000年以后出厂的，然后玩上几个让他目瞪口呆的动作，把火机还给他，淡淡地说："这个是02年出的啊，我的第一个zippo是1993年的，跟了我十年，最后还是让一个朋友帮我弄丢了，家里还有几个特别喜欢的，怕丢，不随身带了。"只消这几句，够了。 　　四．上网 　　现在很少有人不上网了，但是“你有qq吗？你qq号多少？”这句话最好别乱问，尤其是别问看上去比较拽的新朋友的qq号，以免自取其x。经过去年爆发的关于qq与msn的大论战，使得许多梦想装b但不得其门而入的装b爱好者找到了装b的流行风向标：“哦，原来qq是小毛孩和三陪小姐用的，有文化的白领都在用msn啊。”恍然大悟之下，但凡有不长眼的问及自己的qq号，总会很漠然地说：“哦，qq号啊，我倒是有一个，几乎没用过，号码也不记得了，回头我给你查查吧，你可以记一下我的msn，是#$—%*#$@%……” 　　不过这样一来可苦了那些一直在用msn的精英们：“msn队伍中混进了这么多闲杂人员，往后可叫俺怎么脱离群众捏～～～” 　　五．手机 　　这东西没必要用太好的，都咱这把年纪的人了，还赶什么时髦，费力不讨好。我有个北京同学，在我们哥们里也算有俩糟钱的，几年不见，那日同学小聚掏出来的手机赫然是诺基亚的1100,其旧无比，屏幕也花了，按键全都看不清了，举座皆惊呢。如果你也有这份勇气，不妨效仿。当别人用不解的语气问你的时候，你可以端详着自己的1100说：“嗨，手机这东西，打个电话而已！它倾听了我太多的秘密，舍不得换呢～～～”如果说这句话的你碰巧有皮尔斯·布鲁斯南的外形和dr·dre的嗓音的话，用这个片段当诺基亚的广告，绝对对得住那帮芬兰兄弟。 　　 　　 　　估计看完我的帖子，肯定会有人说：你这么着活得累不累啊！那我还告诉你，你也甭跟我装b，要说探讨人生真谛我可比你拿手，两眼一翻两腿一蹬奔赴黄泉是最轻松的人生，也没见谁这么干啊？活着不就图个累劲吗？就像咱们小时候写的学雷锋作文结尾那样：“虽然我很累，但我心里很高兴！”

此乃一转载文章。"MM不是那么容易得到的。本局名叫《丹凤朝阳》，是象棋江湖排局中“八大名局”之一。引用水木象棋版的解释： 这是象棋中的“江湖排局”，已有数百年历史。所谓“江湖排局”，封建社会时期就有人在路边摆棋摊赢钱维持生计。排局就是编排出来的局的意思，这类棋大多是一些热衷于欣赏象棋环环相扣的精彩杀法的一些人精心编排出来的，有些经典局例需要多次修改，最终成型。江湖排局一般最终结局是和棋，但是中间过程很复杂，双方都有一些陷阱。象棋初级爱好者者极其容易坠入陷阱。" "解此局的关键在于 - 这个mm摆局的意图就是告诉你： 别急着打炮 要挺帅 要送车 她也会送你一个孩子（卒）"

Give a interger array of size n, how to find a contiguous subarray whose

sum is equal to k.if there is, return 1, else 0.

e.g.  array[n]={1, 3, -4, 8, -1}    k=10
because 3+8-1=10, then return 1;

What is the best time complexity??

sort the array...