学生时光

KMP

Posted on by snoopy

直接抄的武大李春葆老师的数据结构上的改进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

Posted on by snoopy

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

2006校赛总结

Posted on by snoopy

本来校赛结束前想把这个总结的第一句话来一句粗口的,因为实在是做很多事情太累了,knuthocean和littleken他们比我还要累,但是现在已经释然了.

首先要说一个为自己开脱责任的事情,校赛我是组织也是参赛选手,所以状态没那么好.并校赛前大约3个星期根本没碰题,校赛前一个星期去了一次上海,4天,预选赛还是队友做的.校赛做成这个样子,让很多人很失望,特别外校的,希望不要因为的的问题而让KMXS在大家的心目中地位下降…我只是KMXS最弱的一个人,还以这种状态参赛.

开始说校赛.练习赛的题都很简单,很easy的过了.不过有个小问题,因为做OJ的时候我一直在,然后知道在OJ上最后一行的空行往往被忽略的,并且前面knuthocean也说了比赛的时候Judge很人性化,不会卡空行,所以写Y的时候看中间空行就所有Case都加了个空行,所以还WA了一次.X是个判断直角三角形的问题,很多人想排序,我还是直接写了三个条件用||加上就AC了,事实证明我还是很有思维BT性的(小臭美一下 :P)

决赛当天早上6点多就起来了,和去年的两次区域赛一样,去简单吃早餐,在机房门口等开门.有一个小宣誓还是让小紧张了一下.很快比赛开始了,注意了一个细节是黄院长宣布比赛开始比9点要早一点,所以结束不是2点正,很多人有提到这个,都说是表慢了,其实不是.

在外面等的时候说了一下策略,我看后面三个,HongYi看前三个,ooeyusea看中间的.因为考虑到校赛,可能题目难度分布要照顾一下水平相对弱一点的,事实证明这个策略是对的.

进去后我一看I,好像以前做过的,然后敲,不过中间卡了一下,想证明那个距离是相加还是怎么,其实是取dx和dy的最大值,交后直接Yes,开局不错.

这时候全场就我们一个I的气球,别人都是A的,看了一下Ranklist,发现别人都过的A,然后看HongYi,她说她也是看的后三个,ft,估计赛前交流错了.然后马上看A,发现是个过于简单的题,然后上去敲,用qsort,发现无效,稍微停了10来秒决定直接用冒泡,反正才1000的数据,写好后交,Yes.

然后就开始随便看题,很多人的策略都是从前到后,我们过两个的时候很多人也是两个,不过一般是A和G.跟HongYi看G,说了一下意思,就是一个DP数塔,还是我上去写,测了一下Sample,没错,交,居然Wrong了…这下就有点急了,因为这个DP是高中就学过了,没道理WA啊,估计后面N多裁判都开始骂我了…都是看我一路过来的师兄.打印出代码,开始查错,看了看一个可能出错的地方,改了后还是WA.

到这个时候节奏已经比较乱了,因为本来我想的是我们不跟别人做题,要按自己的节奏来,这下就出问题了.跟HongYi说好意思她说她去,但是code速度比较慢,看她一直在处理3个数的最大值那个地方.我想到了可能是我的边界处理有问题,然后改了一下对边界的判断,交,继续WA.HongYi回来接着看她写的G,我在看其他题的时候一直想这个题目没道理有陷阱啊,难道是long long?不过参赛手册写清楚了啊.后来看了看我最后的判断,原来改边界判断后最后的判断没改正,修改后Yes了.

这个时候基本上都是3个了,我们算很慢的,很多队已经4个,牛一点的已经有5个了.因为我的G的问题,现在已经没办法按自己的节奏来了,把所有的题目扫了一遍.B感觉像以前看过的一个题,应该是网络流方向的,放弃或最后赌一下,C应该是贪心或DP,不知道如何处理,先放下,D乍看像数学题,不过稍微分析一下感觉就是和图论或者DP有关了(事实上最后说标准算法是图论的最短路,DP也是对的),E遍历树,没想好那个树的数据结构怎么处理,算法也没眉目,F一看就知道是凸包,不过过了一年还是不会凸包,并且HongYi说计算几何一般都容易出问题,所以都放开了,我一直都不是做计算几何的,他们两个也不会.

H一开始我就看到了,不过题目看错了,以为蚂蚁速度不一样,然后就复杂了,应该是个超级大模拟.不过这个时候ooeyusea说速度是一样的,然后立马感觉是我以前在ZOJ上做过的那个非环的题.写了很少的代码然后通过Sample,因为这个时候对罚时都比较麻木,并且这个题目也没打算过,加上队友都比较相信我,因为以前集训队内还算相对比较稳的,很多时候还是可以跟knuthocean做的(继续臭美:P),交了后WA,然后发现蚂蚁还是要交换,不会是直接硬搞,又回到初步的设想了,不过感觉是模拟的可能也不大,应该还是有公式.最后flirly说果然还是公式+调整.

在前面看B题的时候HongYi提出了一个把所有1放每行左边的想法,这样只要调整列,不过她觉得这样可能不对,那个时候就没写.在这个时候我感觉这是可行的,虽然场上还没人过B,倒是过CDE的有,C居多,分析了一下时间复杂度,O(n^3),题目说n<100,可以搞.很快将想法实践然后交,WA. 这个时候决定跟人了,因为越来越多的队开始过C,我去重新仔细看题,费老大劲看完了C前面的,然后发现是吹水,感慨一下不要被以前那些看Sample而失误吓倒就好了.大概构造了一下虽然心里认为DP的成分居多,但是还是想用贪心硬搞,先按最小时间排序,然后调整,主要是看怎么调整,应该是一个O(n^2)的算法,只是系数比较大,不过既然knuthocean说了不卡系数,就开始构造模型. HongYi上去看我的B测了一下数据,然后发现在 2 4 2 2 2 0 1 1 的时候我输出 1 1 0 0 1 1 0 0 明显错了,去Debug了一下发现没按我的构造思路走,稍微看了一下发现把一个n写成了m...果然还是自己对行列的定义跟别人不太一样引起的,自己开始写之前都提醒过自己这点的,但是还是犯错.改了后问队友是否交,队友还是很新人的说你觉得对了就交吧,交了后AC,第四个气球,粉色的,全场第二个粉球.后来看了看也只是比kk和magicpig他们慢了1min,还算好. 这个时候问队友对D和E有想法没,看RankList上貌似是D过的人比C过的人要多一点,但是大家都在攻C,自己还是想去硬搞.发现自己越来越想成为跟Grope一样的NB硬搞流选手了,比赛的时候自己看所有题也是一句话:硬搞啊~ 一开始想直接排序,然后发现这样有问题,必须要两个同时参加排序,并且不是一般的简单排,开始考虑贪心调整.这个时候没考虑好所有情况就开始上去敲,为后面的4次才过埋下隐患了.刚好这个时候午餐来了,该死,自己早上没吃饱,感觉饿着比较有灵感,事实也是如此. 看队友很Happy的吃完后自己写好code过了Sample,然后自己随便出了些想到的数据,都能完成.队友都比较相信我的让我交了,然后去吃饭,咬了两口汉堡然后返回了WA.HongYi和ooeyusea开始帮忙想数据,很快发现了几个有问题的.让他们考虑完全后我再去改,因为这个时候是准备赌题目数的,不那么在乎时间了. 其实在吃饭的时候感觉自己已经进入疲劳状态了,一直在抱怨比赛应该是3个小时的.因为自己一直都被认为是2个半小时选手,自己也认可,一直以来单挑的时间居多,跟knuthocean和MasT组成KMXS原型KMS的时候我的code量比较少,很多时候都只是在想,比较舒服,而今天几乎所有的code都是我完成的.MasT和其他人过来巡场的时候还特意说了我一下,MasT叫我不要又是那种比较散伙的消极比赛,其实已经在开玩笑跟ooeyusea说早上应该带一份报纸过来的.这个时候自己的心态已经有点不正常了,不过还是一直在改code. 在队友为我构造C题数据的时候我还看了看E,感觉应该做减法而不是加法,应该是把所有边的权值乘2后然后减去不重复的.这个时候发现我C的错误,去改了后反倒以前的数据不对了,然后对贪心的排序修正,没完全重写,只是小的修补.后来证明这是明显的拆西墙补东墙的事情...交了后继续WA. 自己有点放弃的意思了,都打算看别人了,在不停的刷排名.把所有没开的题目重新看了一遍,讨论了一下后觉得还是应该先把这个开了的题目过了,其他的都还没什么好的思路呢,就是E可能在靠近正确答案.HongYi继续在构造C的数据,我也在构造大数据看错误,找到了一个bug后把贪心的排序部分重写了一下,然后考虑了一些边界值,通过自己的所有数据,交,WA. 这个时候已经近乎抓狂了,不过对外的表情还是比较坦然的,不想让队友也放弃.这个时候因为网络负担太重,网络打印已经垮了,让Staff拿U盘拷出去把代码打出来后慢慢看.考虑了一下那个贪心到底对哪里有问题,然后感觉还是会有问题.重新构造后再通过全部的Sample,抱着死猪不怕开水烫的心情交了一遍,然后开始考虑E的遍历. 开始得出E的算法,不过在疑惑那么大的数据如何处理,特别是边的关系,用容器自己还是不会,本来都准备看看STL的,结果都被其他事在拖住.直接DFS考虑特殊情况是30000的数据铁定堆栈溢出,没敢下手,一直在纸上画图分析情况.这个时候C的提交返回了Yes,第五个气球来了. 看Rank现在是第八还是多少吧,过C前Galaxy过了第五题,这时候刚好超过他们,没有被大一的给bs...和队友说已经算圆满了,这么久没做题能这样也还算好了. 最后看了看感觉F和H是没希望了,D让两个队友去看,我只是知道大概是方差,要么DP要么图论,绝对不会是简单的数学.E的思路已经清楚了,就是去找一个最长的单链,这个单链只要走一遍.本来算法出来了应该很容易写code了,偏偏对这个该死的题目感觉有些无从下手了,因为如何存储那个树,邻接表是绝对不行的,链表感觉也不是很好处理,最好的应该是用容器,又是该死的STL... 还有大概不到一个小时,自己感觉是没题可以做的了,看队友讨论D,我上去写E看能不能在写code的过程中突然爆灵感(YY啊...).写E的时候感觉是在等死,就是在不停的刷Rank,然后看别人过题...自己已经没体力继续了.看了看在我们前面的都是外校的区域赛队伍,后面我们学校的估计也都不行了,能这样不错了,看Galaxy还在攻B,在比较频繁的提交,跟队友说估计他们一件抓狂了,站起来看他们也的确差不多了,不过还是感觉他们应该能在最后一个小时搞定的,在希望他们能给武大留一点最后的面子的同时也希望我们该死的T13队名能给别人带来坏运气(这都什么思维啊...). 最后真的是在放弃,HongYi对D给出了一个大概的公式,然后说后面很多还没想清楚,我也没仔细看和帮忙想,说你觉得可以就上去敲吧.260min的时候Neptune过了D,以过题多从后面超了上去.排我们前面的由此确定了队伍,剩下的只是他们之间的交换.最后20min左右校内的Dolaamo过了C,一阵欢呼,HongYi说她们在跟我们做,现在回头看summary也的确是这样的,刷Rank的时候看到cowork也上来到5题了,然后说幸好他们还不是那么散伙,让别人对武大看轻.HongYi也在放弃继续想D,让ooeyusea去看的F他一直也不敢写,策略失误让我们最弱的队友一直在看难题,后来他看的题我们一个也没开...MasT在最后还多给了一份午餐,在最后几十分钟内无聊的时间内填饱了肚子. 在pc^2上刷到最后5min的时候在站起来看别人了,HappyFish宣布还剩下几分钟的时候看了看只剩下1min,索性都跑后面去看Judge那边判最后的疯狂提交. 比赛结束了,散场~跟出题的和外校的交换了一下对题目的理解,E果然是找最长单链,存储也是用链表或者STL,只是我怀疑DFS会堆栈溢出的那个部分没人跟我说一个比较清楚的思路,现在想来和Galaxy还是谁说的用BFS实现就可以了,队列只要开到30000,做两次.D出题的说是图论最短路(跟前一天晚上跟ZSU的吃饭时MagicPig说HUST上某题有差不多的出题意图),做出来的很多人说就是DP就好了,现在还没去好好想这个.F是凸包没错,但是很奇怪为什么全场也没人过这个,现在回头看最后summary前面的也就是Australis,fish and bear,Afflatus开了这个题,后面是cowork开了,真正一直在做的应该只是fish and bear.H也果然是本次比赛最BT的题,flirly说还是得找公式然后调整,O(n)或者O(nlogn)吧,我记不清了 :P 比赛结束了,和大家一样,也列一个感谢名单吧. 感谢众多兄弟院校过来捧场并给我们一场如此精彩的比赛,希望大家能一起加油进步,场上的对手场下会是非常好的朋友. 感谢knuthocean,littleken,flirly,MasT等人给我们提供了一套非常好的题,感谢技术Staff和Judge,那么多来帮忙的老队员,感谢协助组织比赛累的半死的KongHui,感谢武大计算机学院学生会组织部和实践部的各位同学帮忙打了接近1k个气球并布置好了如此pp的现场,感谢KongHui等pp的气球MM. p.s.1.总结over了,说一个小插曲,本来是打算周一晚上写完就发的,看时间不够想上BBS上说一下我可能今天晚上搞不定了的时候结果还是被无情的停电了,BBS上都没发出消息,幸亏我还没事ctrl+s了一下这个总结. p.s.2.今天早上写最后一点的时候ooeyusea过来说H只要找到第一只蚂蚁的最后位置就可以了,因为全体蚂蚁的相对位置是没变的,感觉这样就靠近或者是最后思路了,赞~

责任,义务

Posted on by snoopy

很多事情,接手了就没办法轻易放下了.

上个星期去了一次上海,ACM/ICPC亚洲区中国大陆春季论坛,很多国内的知名领队都介绍了经验.感触很多.

说他们是领队而不是教练的原因是其实大家都知道,玩ICPC老师的作用主要不是在辅导队员,而是如何有威信的领导整个团队,并处理好团队和校方的关系,同时保证整个团队积极有效的运转.领队的作用是跟校方处理好关系,宣传好ACM/ICPC,使参赛被认为是一个快乐并且是有***的一个游戏,选手在学校应该是属于受欢迎的偶像,教练是一个有回报并且能看到自己努力成果的岗位.

教练这个职位只能是老队员或者选手自己,在有老队员资源的情况下不用真的是浪费,其实很多人退役的时候都是还有很大提升空间只是因为时间的原因而不得不告别赛场.这些人是对ACM/ICPC有最深感情的人,也是校内最有了解的人,他们对ACM/ICPC的感情是纯真的,完全发自内心的热爱.他们会对比赛进行最细致的剖析,对题目进行解释,对算法进行讲解,对最影响最后成绩的选手心态进行调整.

自己,现在究竟是什么身份呢?协会会长?参赛选手?集训队队长?抑或管理者?很杂,感觉武大从来都不应该是这样的,04年的Dragonflywww和Grope就是因为管事和参赛同时进行,并且应该在心态上有些问题,才以那么好的实力输的那么不甘.

很多事情自己已经接手过来了,并且现在自己对那些事情都是一种责任和义务,自己能享有的权利,都没怎么想过.太多的责任,自己都不知道怎么揽过来的,那么多的事情,应该是别人去操心的.自己应该好好做好一个队员,给自己一份最美丽的礼物,一个期盼多年的礼物,同时,希望这份礼物也是给武大最好的礼物.

太多的事情,是我不能左右的

Posted on by snoopy

连续在实验室呆了两天了,晚上都没吃饭,刚吃完去楼下买的面包.

花了一个星期,从零开始看HTML并几乎用纯手工代码完成了http://acm.whu.edu.cn/的内容,这个星期虽然还是有很多的时间在玩,但是更多的时间还是在不分时间的在敲代码,终于在一个星期内还是搞定了主页以及相关页面的内容.

尽力对校赛做了一切自己能做的事情,对外校的联系,本校队伍的通知,在得知需要推迟后做的道歉,为网络预赛及现场决赛做的前期准备,跟ACM/ICPC官方的联络.最后,却被告知太多的事情不仅不能按照我的要求到位,而且,更多的事情陆续都在超乎我的心理底线.

先是服务器在最后的心理底线3.15报名截至前没能到,并且在被无限延迟中.然后是外校的邀请函未能发出任何有效信息,现在还在纯手工单线联系确认每个队伍的完整信息.现在是几乎连校赛决赛的场地和设备都无法保证,oh my god~

现在,校赛的网络预赛被无条件推迟一个星期,并且还不敢说一定能挂在自己的OJ上,想想真的是非常不甘啊,老杨他们做了1个多月的结果就是这样的…

其实自己真的不用这样生气,很多事情,都不是自己所能决定的.并且,武大的办事风格,自己也不是没有体会过.自己已经尽力了,并且是在很多自己完全没必要去做的地方都尽力了,并且这个事情如果不能做好,丢脸也不会是自己的,别人只会说,武大如何如何挫,与己无关.但是,我真的想为自己的学校做一点事情,让自己以学校为荣耀的同时,也能让某些人在想起武大的时候能说,武大的某事某人做的很好.

最近几天的心情一直不好,说话都暴躁了很多.也许这样也好,人,要活得有自己的风格一点,毕竟,我还是不希望自己太乖,从而使得N多见到我的人都在叫我师兄,从研一到任何比我低的年级.

今天在cici的Q-zone上看到一句话,被狠狠的刺痛了一下,回想一下,整个2005的后半年自己不都是活在这句话的阴影中?

当你只能看比赛的时候，就会知道能够参加比赛有多么快乐．

这个世界,总有太多无奈

Posted on by snoopy

很遗憾的事情,我写的那个想法还是被批的体无完肤.其中牵涉到太多人的面子和利益关系,有太多我们只能遵循的规则在里面主使.

本来自己的05-06赛季到这里就算完了,现在就是两件事情.身为协会主席,就是想怎么能扩大影响,帮忙WHU冲出去了.可惜,自己只能是一个傀儡,什么也不能做,空有一腔想法和抱负.作为队员,现在就是要好好训练,争取在明年的校赛和3+3中杀入一队.可惜,按照官方的意思,貌似明年我就会是一队的了,就像今年的xxx.

这个世界有太多的无奈,有太多我们无法改变的东西,有太多的利益关系,有太多的人一腔热血最后饮恨而终.很久了,有很多想法被压抑了很久,我不知道我到底应该选择我自己还是选择无奈的去遵循这个社会,很多事情,并不是我所能决定的.

在自己的BLOG上,终于能畅所欲言了吧,希望自己能不要这么堕落下去,好好训练,明年以实力出去说话.其他的事情,不想过多评论,都到这个地步了.