Year: 2006

KMP

直接抄的武大李春葆老师的数据结构上的改进KMP

// return the first matching string2 in the string1
#include <stdio.h>
#include <string.h>
#define MaxSize 1000

typedef struct
{
    char ch[MaxSize];
    int len;
} SqString;

void GetNextval(SqString t,int nextval[])
{
    int j=0,k=-1;
    nextval[0]=-1;
    while(j<t.len)
    {
        if((k==-1)||(t.ch[j]==t.ch[k]))
        {
            j++;
            k++;
            if(t.ch[j]!=t.ch[k]) nextval[j]=k;
            else nextval[j]=nextval[k];
        }
        else k=nextval[k];
    }
}

int KMP(SqString s,SqString t)
{
    int nextval[MaxSize],i=0,j=0,v;
    GetNextval(t,nextval);
    while((i<s.len)&&(j<t.len))
    {
        if((j==-1)||(s.ch[i]==t.ch[j]))
        {
            i++;
            j++;
        }
        else j=nextval[j];
    }
    if(j>=t.len) v=i-t.len;
    else v=-1;
    return(v);
}

int main()
{
//    freopen("kmp.in","r",stdin);
//    freopen("kmp.out","w",stdout);

    SqString str1,str2;
    gets(str1.ch);
    str1.len=strlen(str1.ch);
    gets(str2.ch);
    str2.len=strlen(str2.ch);
    printf("%dn",KMP(str1,str2));
    return(0);
}

RMQ

whummd的blog上copy来的,加了点自己的修改,正在看,集训加油

// StandCode for RMQ, return the smallest number in array s[i..j]
#include <iostream>
#include <cmath>
using namespace std;
#define MAXN 1000000
int f2[30];
int s[MAXN];
int r[MAXN][22];

void make_f2(int n)
{
    int i;
    for(i=0;i<=n;i++)
        f2[i]=1<<i;
    return;
}

void make_RMQ(int n)
{
    int i,j;
    for(i=1;i<=n;i++)
        r[i][0]=s[i];
    for(j=1;j<=log(n)/log(2);j++)
        for(i=1;i<=n;i++)
            r[i][j]=min(r[i][j-1],r[i+f2[j-1]][j-1]);
    return;
}

int RMQ(int i,int j)
{
    int k=int(log(j-i+1)/log(2));
    return(min(r[i][k],r[j-f2[k]+1][k]));
}

int main()
{
    freopen("rmp.in","r",stdin);
    freopen("rmp.out","w",stdout);

    int n,i,start,end;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&s[i]);
    make_f2(20);
    make_RMQ(n);
    while(scanf("%d%d",&start,&end)!=EOF)
        printf("%dn",RMQ(start,end));
    return 0;
}

关于Baidu的一些思考 – 不要争执那些没意义的东西

昨天看的Baidu的一本更多意义是宣传的书,虽然有广告的肉麻嫌疑,不过还是有很多值得慢慢讨论一下的.说一些书里的内容,说一些自己的体会.

1st,不要争论那些与己无关的东西,除非你是在大专辩论赛上.
这是一个很重要的命题,以前的自己,总是花了太多时间在跟别人争吵,或者自己一厢情愿的认为那是一种辩论,是一种人生观价值观的体现,其实是一种很无聊的东西,有什么意义呢?毫无意义,只是在没有价值的浪费自己的时间.以前的自己,总喜欢对很多东西发表评论,自以为是,以为看明白了世间的种种,其实也不过是井底之蛙,并且,智者的重要表现之一,就是学会保持沉默.往往,沉默是金,因为过分的争执和自大,会失去很多朋友,同时,过度的自我膨胀会遮挡自己的眼睛,从而不能看清楚很多东西.往往,真正的智者都是一语中的,没有丝毫的拖泥带水.

2nd,在没看明白自己面对的问题前,不要轻易评论,哪怕是在心里.
这个是我自己加入的,以前的自己就经常是这样,别人话说到一半,或者一个事情的背景完全不明白的情况下,就在大放厥词,往往,在贬低了自己的同时也让其他人看轻了自己.现在起要好好的观察,学习,这就够了,关于谁是谁非,那是后来的无聊人做的事情.

3rd,少说多做,努力,努力.
俞军每周工作100个小时,以至现在的搜索引擎泰斗,不知道书里对这个有没有夸大其词,不过,至少那个态度还是在那里的,回头看看自己,每周真正投入在学习中的有多少?更多的时间自己都用来干吗了?今天看了很多题,结果都是自己不会的算法,虽然一个敏感度能告诉自己应该如何去做,但是无法实现,什么都不算,一个白日梦而已.

4th,我总是在进行所谓的思考,继续思考,直到发现思考的问题过时转而去思考下一个问题.
这很不好,那么多的时间为什么都要浪费在空想上,给自己一个目标,继而为之努力.从现在来说,重要的内容是考研和工作,今天想到的是能不能两者兼而有之.对自己的能力有充分的信心,虽然因为那个事情对自己的打击非常的大,但是自己还是非常的自信,这不是盲目的自大,而是自信,虽然现在的自己好像颓废的完全不成样子,只要振作起来,我还会是最好的.对过去的两年或者更久,浪费的时间已经无法挽回,自己需要的,只是从现在开始努力,做最好的自己,燃烧力量,给所有人证明自己的价值,最需要看到的,是自己.

以后要注意克制自己不要总把时间花在这种事情上,一段时间能安心下来想明白一件事情就好,不必要太过于探究.好好努力,好好加油,好好生活.

奇怪的生活方式

最近的睡眠时间越来越奇怪了,昨天晚上是从7点半睡到9点40北吵醒,然后实在吵的不行就索性爬了起来,然后准备1点睡的看一个好玩的东西看到3点.今天早上6点醒了一次,看表,太早,接着睡到萌萌7点20敲门.起来,过来机房干活.

生活还是挺有规律的,争取晚上能好好睡足至少7个小时,吃饭后休息一会先睡觉,然后起来玩到半夜继续睡到早上.

北京时间7月2日凌晨1:47,我的世界杯结束了

标  题: 北京时间7月2日凌晨1:47,我的世界杯结束了
发信站: 珞珈山水BBS站 (Sun Jul  2 14:21:02 2006), 转信

终于还是在这里轰然倒下,但是,走的没有一点遗憾,不是我不希望前进,是点球大战中,我不断祈祷的心只是在往下沉.

喜欢一个队,没有理由,同样,支持也是没理由的.看球,却总是快乐的时候少,难过的时候多,也许,我们认为快乐是应该的,必然的,所以我们没理由那么牢记.而失落,是会一直压在心头的痛.

02年,开始爱上England,理由是很奇怪的我玩FIFA WorldCup2002用最顺手的就是England,在班里所向披靡,最后导致联网玩这个游戏都被强制不准选England.

那一年世界杯我高一,小组赛一直到半决赛的时间我们都是在学校里偷偷跑外面去看,或者是在课桌里放上收音机听.期末前不久的周末补课,请假回家,一个多小时的车程后回家一打开电视机,是巴西的R10在上半场结束前得R11突破后的传球得分,1:1.那一场比赛,Owen很早进球,典型的Owen式进球,速度与灵活,加上对那些一瞬即逝的机会的把握,那个少年,依然如故.

下半场R11的任意球破门时,在惊艳于如此漂亮的弧线的时候,我觉得,我的2002世界杯就快要结束了,在结束后看见希曼的眼泪的时候,我只能无语,然后换台,等吃晚饭.

最后我看了3,4名决赛和决赛,因为我们放假了,德国的Ballack缺席决赛,让我觉得那场比赛的精彩程度大打折扣,R9的两个进球,也是感觉一般.

04年欧洲杯,对无视高考的人来说,是很开心的时刻,对法国的那场球,怕吵醒爸妈而设置的不那么响的闹钟没把我弄醒,醒来时已经快结束了,打开电视机的时候齐达内在进那场比赛法国队的第一个球,还没摆脱无奈,却看见了2:1的结果,很不能接受的看完了赛后的精彩瞬间,然后睡觉.第二天起来看重播,知道结果后是如此的无奈,看着Beckham把点球打飞,只能说,无奈.

对葡萄牙的那场比赛凌晨2:15开始.记得很清楚,因为我按时起来了,看完了全场.Owen那个追风少年还是一如既往的Owen式进球,但是还是很可惜被扳平,然后拖入加时.全场体力透支的22个人毫无章法的在银球制规则下居然在加时打成了2:2,点球决战.

Beckham罚丢了England的第一个球,也是他那次欧洲杯的第二个点球.5轮过后是4:4平,加一轮,继续平.Vassell的点球被光手的Ricardo扑出,然后Ricardo亲自打进最后一球后,看着外面泛白的天,欲哭无泪,抱着一个快被磨破的球就跑家旁边的小学操场上去对墙抽到脚再次知道痛.

今年的世界杯,我们在期末考,但是依然会看球到至少1点,1/4决赛的第一天,就是一场点球大战,德国式的男人Ballack带领德国继续前进,让我还在憧憬自己喜欢的3个球队能一起进入四强.等England的复仇,赛前的八卦新闻什么都有,我希望的是英格兰能90分钟内干净利落结束比赛,不要在拖到点球了.

比赛开始后也没觉得什么了,都在闷战,都有机会,有射门,有扑救,有门柱,有飞机,拼抢上,也都很激烈.但是,Beckham的受伤意外离场,Rooney的暴力行径被红牌罚下,让我只能祈祷,偷袭得手或者拖入点球以曾经失败的方式结束失败.这一次双方在加时赛的体力还能保持没出现大的动作变形,除了那个越位在先的球,一切都波澜不惊.

点球开始前同学就在说有不好的预感,England的Owen,Beckham,Rooney都不在,能罚点球的,悬.当看到第一个是Lampard的时候,同学说预感要坏事,结果就被这个乌鸦嘴给说中了,我的心如同电视画面上的Gerrard一样的难过,他都要哭出来了.葡萄牙连续两个自己打出去加上Hargreaves的进球,让阴暗的天重新露出了阳光.但是,Gerrard这个我一直坚持是个阳光男孩在点球点上罚出的球再次被扑出,让我只能掩面祈祷.第四轮,葡萄牙进球,Carragher居然还罚球违例的弄进去了,重罚,心理上的压力让那个球很舒服的被Ricardo给拿到,在心里,我已经快要接受England要回家的事实,但是,还是在期待奇迹的出现.

C.Ronaldo在点球点前把那个球放了很久,然后在鸣哨后结束了我的2006世界杯,这一次,段喧也没有发飙.

坐在隔壁的电脑前蒙了一会,然后放下掩面的手,接受这个事实,于是回宿舍一口气喝完了一瓶1L的矿泉水,当时的感觉,心碎.然后站在在淋浴下,看从头浇到脚的水流过眼前,希望自己看不见自己的眼泪,宁愿相信是被虫子迷了眼睛.

想起一句很经典的话,曾经是给相爱的人的,曾经也有很多阿根廷球迷在引用,现在,在02WC和04Euro后再次拿出来写给自己:

爱是等待
爱是忍耐
爱是接受她的一切错误并笑对命运的安排

希望能快点看到不再等待的那一天…


※ 来源:·珞珈山水BBS站 bbs.whu.edu.cn·[FROM: 222.20.237.*]

德国,继续高歌~再见柏林

德国赢了,进了4强,下一场对意大利.

虽然可能这个方式并不是那么华丽漂亮,虽然很多阿根廷的铁杆球迷会准备砍我,但是我还是要说,德国赢了,这就够了,并且也赢得很光彩.那些批评德国得到裁判的优势的人可以考虑一下自己如果是在场上视野范围内能看到多少犯规,能看清楚多少假摔,同时可以注意一下阿根廷人手上有多少不干不净的动作.点球大战中莱曼是一个神,4个点球丢判断对了方向并作出了正确的扑救动作,第一个和第三个实在是无能为力.

阿根廷,再见,希望那些高歌阿根廷,不要为我哭泣的球迷不要再说输的如何冤,德国现在的脚下不比其他人差多少,并且,德国还有全面的身体优势.

柏林,再见,下一场,多特蒙德见,丑陋的意大利会屈服于坚强的德意志战车.

柏林,再见,德国时间7月9号晚上希望看到你们再次回到柏林和巴西或者英格兰的精彩表演.

新四级考试报告…

发信人: iBook (笨狗dd~/偶像Party CTO), 信区: EnglishTest
标  题: 新四级考试报告…
发信站: 珞珈山水BBS站 (Sat Jun 24 14:21:19 2006), 转信

上面居然有人说等我的.本来就想来说一下 :)

新四级改了很多地方,跟我们一直以来的风格不一样.首先,顺序改了,作文移到最开始,然后是一篇1k2的快速阅读,接下来是35%的听力,卷面写的是35分钟,但是今天实考估计有至少40分钟,然后是一篇短文填空,不是完形,是15个词填10个空,再是2篇传统的阅读理解,接下来是所谓的4选2,不过好像其实是3选2,完形填空/改错(2选1,卷面是什么就做什么),今年是完形,最后是5个翻译,汉译英题型改了,原来的4篇阅读理解现在还是4篇,有一篇提前到作文后听力前,15分钟的快速阅读,大纲上写的是1k-1k2的词汇量,然后是7个Y/N/NG的选择+3个简单回答问题,另一篇是听力之后,有两种形式(我看到的预测卷上的),一个是短文填空,给15个词填10个空,有点类似完形填空,不过又不是一样的,15个词往往大部分不认识…还有一种是阅读后简短回答5个问题.在这个后面就是2篇传统阅读了.

其他的.听力改动上,原来的10个小对话现在成了8个小对话+2个长对话,前面8个问题,后面是3+4或者4+3个问题,这里多了5个选择.后面的3段对话没变,还是10个选择.然后是新加的第三部分,一篇短文,抠出8个单词(前面),3个句子(后面),然后听写补充完整,这个短文会读3遍,其中第二遍会稍微慢那么一点,要听写的句子后面有一个比较长的停顿,其他2遍都是一气读过去的.

阅读后面是4选2.具体上面有解释了.

以上是感觉.下面说我觉得应该的应考.

词汇是第一的,有词汇了就可以什么都不怕.平时做点练习熟悉题型就好了.

考试时的风格:9:00发卷,填完考号后可以看到能做的有作文,翻译和听力的PartIII,可以先看作文题目,打个腹稿,或者把翻译先心里搞定.30分钟的作文时间是不让拆试卷的,我觉得都拿来写作文太浪费,我今天是20min以内搞定作文然后搞定了翻译,把听力PartIII先过了一遍,对文章大意有理解.

30min的时候开试卷,快速阅读,真的是快…先看好问题然后去看文章,后面问题都是前面的原文,或者是一句话改了个顺序如此的,问题都是有顺序的,要么10个都有顺序,要么Y/N/NG有顺序且问答有顺序,两个顺序有重叠的.看到一个问题划出来然后搞定之.快点填完,因为只有15分钟,开考后45分钟收答题卡I,就是上面两个部分.

听力没什么好说的.平时多听一下有感觉就好.先把答案看一遍,听的时候有选择性一点,建议前面能快点搞定然后把所有问题都过一遍,因为虽然听力三个Part前都有一段罗索,但是每个Part内部是不停的.比如第一部分两个长对话和第二部分3个短文之间都是问题完了就直接听下一个的. 说一下第三部分,先把文章大意读懂是很重要的,有些空都可以不听也能写出来,听的时候,第一遍单词基本都能出来,顺手写试卷上吧,句子时间来不及就写个大意,第二遍就可以补充完整了,听力好的可以一字不差,当然这里考试要求只要意思对了也是给分的.

那个15填10的真的是bt…就说那个单词,15个我一般是10个以上的不认识(当然本来我词汇量就小…),除了这个,就跟一般的完形填空是一个道理了,读一遍然后填,然后再读一遍验证(做3遍要速度很快,不然还是2遍好了),据说这里可能是回答问题,但是我有那个预测卷但是没做,保持沉默.普通阅读理解没什么好说的.

完形填空.这个不说了…改错,我做的卷子都没有,然后我差点以为没改错的时候有n个人找到了有改错的卷子…也没什么好说的,要提醒的是10个都是错,没一个对的.幸亏今天上天保佑,卷子上是我会做的完形填空…

翻译,一个句子,砍掉一半,给出你没有的一半的中文解释然后翻译成英文,没什么好说的.

这里特别强调一个时间,时间很紧迫啊(虽然我是拿了至少15分钟出来玩),推荐翻译和作文一起搞定算了,不然后面都没时间,听力说是35分钟,但是事实上远不止35分钟,加上涂答题卡的时间,我花了43分钟,慢的有花50多分钟的,这也就是说还有3篇阅读(25分钟),1篇完形填空(15分钟),5个翻译(5分钟)要在30多分钟内搞定,所以翻译能占有作文的时间做也就这样,最好还能把听力PartIII给过一遍.今天我写完还有10多分钟,但是交卷的时候很多人还在做那个15选10,很多人都在乱选了…时间啊,时间


>>最希望的阵容>>           Owen
█████████                         Rooney
█████████  >我爱世界杯<     J.Cole     Lampard   Beckham
█████████  >我爱英格兰<   A.Cole    Gerrard       G.Neville
█████████                        Terry  Ferdinand
█████████                           Robinson
※ 来源:·珞珈山水BBS站 bbs.whu.edu.cn·[FROM: 202.114.121.*]