SQYBI.com

沉寂了快一个月了,终于想为NOI写点什么.
主要是因为刚才看了alft的NOI照片,还听了某人的采访录音...然后视图拼命地在脑海里搜寻NOI的片段...二分了半天的结果也只是一些细小的碎片.
怕把这些碎片也丢失了,只好写一篇文章存起来.
也以此文献给所有参加NOI的朋友们.我们都是最棒的.

我承认这篇文章我是照着NOI的日程写的...因为我已经什么都记不住了.
估计肯定会有时间地点人物的错误,请知情人士积极提出...
另外欢迎补充各种事件.

准备过程

NOI前停课一个月,和jl,zch,Nxun,zmc,wr一起做题...我们的这个临时组织还被命名为Fight For Fun(我起的名字~).感觉还是有些效果的.很怀念大家一起做交互的日子(看懂了?请笑一笑~看不懂就忽略吧)...
出发前几天手机竟然坏掉了,很囧.临时买新手机,考虑了一晚上,决定了Nokia 6120c...虽然买到的价格比预想的高,不过真的是物超所值的手机.强力推荐.S60v3系统,处理器速度巨快无比...好吧我该打住了...希望知道详细资料的请自行查阅.
不过...6120c竟然和zch的手机撞了...意料之外...还好我的是黑的他的是白的.但在火车上竟然看到了一个用黑色6120c的人...唉...街机...比N73还街机...
走之前发了一件衣服,还有两个圆形的上面写着NOI天津队的可以贴在别的地方(比如衣服和行李箱)的东西...

2008.07.26 we are ready

26号,出发的日子.

本来说坐飞机,可因为Olympic的缘故,订飞机票出现了一点小麻烦...最后连软卧都没有...只有硬卧.

下午在火车站集合,当时找了半天没找到人,于是给jl同学打电话,得知他还没到.于是认为一个人都没到,就等啊等啊...突然看到了wr的身影...仔细一看好几个人都在进站口等着呢...
于是凑过去,发现自己到的还不是很晚.
过了一会儿caiych到了,不知怎么提起来的...和他打赌jl和zch谁先到(当时就剩他们俩没到了).我忘记了当时我赌的谁...反正无所谓了...因为这俩人同时到的...而且还不是一起来的,只是同时到...

然后进站(总打成进栈),潘老师不知怎么联系的...让我们没在候车室候车而是先上车了...挺爽.
然后发现竟然只有我和wdy分在了13车厢...其他人都在14(两个数字不一定准确...).然后厚着脸皮麻烦潘老师换票...
但是因为我们俩都是上铺...所以很难换到.
然后潘老师说换到了一张...我本来说两张都换了再过去,可潘老师执意让我们先都过去...于是我们俩都过去了...
换票的那个哥哥是一个外地人在天津上大学...大学生哥哥姐姐还都是很好心的哇^_^.很搞笑的是当时我想帮他把东西搬过去...然后不知怎么想的叫了人家几声"叔叔"...当人家知道我在叫他,回过头一脸迷惑的表情...
不过很惨的是wdy竟然到最后也没换到票...上铺果然不好...然后wdy发扬人道主义精神自己搬东西回去了(画外音:怎么不说你不人道...sqybi:我也让了他嘛...只不过他太人道了而已...啊...哪儿来的臭鸡蛋...)...

晚上的时候和wr,yh,zmc几个人打牌(有没有jl和caiych?记不得了...反正Nxun因为去了复旦培训所以没有跟我们一起走),用的是他们上次去NOI的方法...把被子搭在几个人腿上然后在被子上玩(画外音:不要邪恶...虽说几个人里有MM...还是cj一些好...)...我这个上次没去NOI的开眼界了...

本来以为能玩通宵的...后来发现大家都想睡觉...于是我也爬到上铺睡了...

发现在火车上睡觉好困难...一是因为火车撞击铁轨空隙的有节奏的声音,但更主要的是,上铺的空调太要命...盖着被子的地方出汗,不盖被子的地方冻得要死...
还好,最后还是睡着了.

2008.07.27 忙碌的报到日

上午到了上海,然后在上海火车站下车,坐轨道交通(就是地铁...)到了上海南站...
上海南站比上海站环境好得多...候车的时候也很舒服.

候车的时候竟然碰到了Nxun,外带(不是外带全家桶!)宇智波然,xc_bb,flyfox等一干大牛...只记得flyfox是最胖的...然牛是最高的...xc_bb牛是长得最正常的...
还有啊...当时张老师找我借书看...于是我就把黑书借给了她...没想到...我忘记了自己把几百块钱夹在了里面...

等从上海坐火车到绍兴,已经下午1,2点了...然后上汽车...不多久就到绍兴一中了.
在汽车上竟然看到了alft,囧.本来没准备好这么早就见到了,alft显然也没准备好...

进去之后等潘老师帮我们报到...然后领东西.
衣服竟然只有一个L的...被yh弄走了...剩下的都太小...

刚走到宿舍楼口就被雷到了...只见四个大字..."女生宿舍"!
似乎是女生和正式选手男生合住女生宿舍(只是在一个楼里...女生宿舍在楼上男生在楼下),然后夏令营男生住男生宿舍.于是我们这几天就没有男厕所可上了...

收拾收拾东西,发现只有一个插座.于是去买接线板,刚开始一群人浩浩荡荡出去,但外面的太阳实在太大,等走到校门口就剩下zch和Nxun了.
把接线板布置好,又把我带的路由器弄好,然后下去吃饭.

刚开始还真没想到是自助餐,不过自助真的很爽~心情好的时候吃很多,心情不好的时候也吃很多(=_=),不饿的时候吃很少...一切都自己掌握.而且还有各种饮料.
感觉这几天碰到的最好吃的东西就是饺子,做得很好...咬一口里面还有汁...怀念啊,可惜吃不到了.

对了,还把我们叫出去照相呢.然后照相之后才知道还有录像,让我们想一个口号.
本来想喊"没有蛀牙",可是这个比较无聊...和OI也没关系...zch这时提了一句,"天津OI,OI中的战斗OI,Oh yeah",我们就采用了...事实证明很雷人...很成功...

晚上也没什么事情,就睡觉了.
睡觉的床直接是一个木板,很硬...我比较懒懒得在下面垫被子,所以直到最后几天实在无聊了才动手垫上...然后感觉下面有被子那叫一个舒服...
第一天睡觉的时候就感觉空调很冷,不过yh和zch强烈反对关空调...于是只好开着睡觉了...后来得知jl他们那儿第一天空调忘了改温度,睡觉时竟然是18度(数字不准确)...囧死了.

2008.07.28 搞笑的开幕式

早饭过后去看开幕式,印象最深刻的是开场唱歌那个PLMM,还有最后主持人的那个口误...
"闭幕式到此结束!"
然后说完几秒钟还没反应过来...这时全场都笑翻了...

下午练习赛+笔试,没什么可说的...显然轻松地水过了.

晚上去打球,我去打的乒乓球...觉得自己对乒乓没感觉了都...还和蒙面人大牛打了几拍...
这一天都很无聊.不过碰到了一个北京的小盆友,就是最后团体赛的那个特邀主持人...说实话这人真的很令我赞扬,很放得开.

第二天晚上洗澡还是没有热水,终于知道这里只有凉水...这也正是为什么最后几天洗澡速率急剧下降...

2008.07.29 有惊无险的Day 1

上午比赛,坐在了前一半的最后一个位置(当时座位分成了朝着两个方向的两半,前一半指编号小的)...
比赛结束后感觉不是很好,不过问了几个人都说做的不好...稍微放心了些.

下午看成绩,比想象的好很多.不过当时我周围有两个人聊分数,都是140+,吓了我一跳.后来得知了大概的成绩分布才放心...

讲题大会也很搞笑,第三题(不一定准确)得分高的几个人竟然都没来讲题大会,包括gaoyihan大牛...然后两个50分(不到10个人50+,剩下的人都30-了)的竟然都是贪心...囧死了.

2008.07.30 不完整的旅游

上午去鲁迅故居旅游,还好比较有心情,但是实在是无聊.所以下午的黄酒博物馆,就没有心情了...
上午回来的时候和车上的导游同学聊了好久天津的文化...比如小吃,比如天津话...突然感觉自己的家乡是这么的优秀.

很感谢zmc的几条短信(不一定是30号发的...我忘记具体时间了).是你给了我希望,给了我感动.

这天基本没啥别的事情了.

2008.07.31 惊心动魄的Day 2

Day 2考试时状态不是很好,出来之后估分也不是很高.还好滕老师发来条短信,"捞的怎么样",大概有了底...Day 2的题目比Day 1简单不了太多.

下午开了一个团体赛的会,但是因为一些电脑(包括Nxun的)出现了无法安装系统的问题,所以拖了一段时间...然后最后也没解决问题,只好先上去看成绩了.看到了美女cici,yeah~

结果出来,的确如此.不过Day 2还是简单些的,意料之外的失误和得分都出现了.
两天基本还是发挥正常水平,没有超常发挥也没有失手...又一次确信,稳定发挥才是最重要的.在这里bless一下jl同学...希望以后rp++,不会再犯同样的错误...

讲题大会因为有事被叫出去了,不过还是听了一部分.网络流那道题让我眼前一亮...真的很神奇.
晚上招生会的事情略过.

回到宿舍,开始准备团体赛.没想到所有人竟然都过来了,5个正式选手,5个夏令营选手,一个参加另一项比赛被孙老师带过来的同学...11个人,7台电脑,开始了这一晚上的狂欢...
说实话以前从没有过通宵,这是第一次.当时的感觉无法用语言形容,除了写程序真的想不到别的事情可干.
刚开始其实我因为几个bug曾经放弃了写我的程序,但是看到yh的程序所向披靡的时候,我觉得是自己该出手的时候了!于是开始改进自己的程序.
刚开始几次连第一个块都没放下,不过从我能够完整的完成比赛,我的程序开始显出威力...两个我的程序成功的干掉了yh的...但致命的弱点是我的程序是随机化,所以很靠rp...而且我的一个程序也不能很好的抑制对手,两个合作才有效果...

能够11个人一起通宵写程序,真的很爽...觉得键盘的声音像音乐一样...这是真的...没有经历过的人真的无法有这种神奇的感觉.
yh的话没错,这是我们的翻身仗,我们最后的机会.以前天津的程序从来没有进入前几名...这次我们希望创造历史.
4点左右吧,程序基本调完,准备用yh,我和jl的程序上战场...但我知道这里面有所有人的汗水,所有人的期望.
迷迷糊糊趴在桌子上睡了一小会儿,起床吃饭.

2008.08.01 激情四射的团体赛

不得不承认,团体赛比Day 1 Day 2更加有激情.

刚开始四轮,我们就发现自己的程序有问题.因为yh的块放置顺序是确定的,所以当时的程序和yh的完全不同,一眼就可以看出来.于是四轮过后,我们去找举办方申诉.结果是重赛,全场报以热烈掌声.
有一个队伍(忘记是哪个了)的程序,刚开始几次都没有放下第二块就挂掉了...等到他们的程序终于把第二块放下的时候,全场掌声雷动...

当时的气氛很能够感染人.
每一次精彩的放置,每一次精彩的封杀,特别是那局"井字"(不记得的见我相册),都能引来掌声.

我们最后用了比较保险的yh的程序,而没有用我的那个.很可惜的是,他的程序有一个致命弱点:在第一个走的时候,这个程序很强悍,甚至不弱于前几名;但在最后一个走的时候,这个程序的威力就大大减弱了.我们的运气不太好,好几轮都是最后一个走,加上新疆队的强大的程序几次封杀...最后只拿到了第6名.更囧的是,一等奖两个,二等奖三个...我们只能三等奖了.不过也是历史性的突破,所有人都很满意.而且我们曾经一度打到第3名,当时我们都很兴奋.
另外让人印象深刻的就是那个特邀主持人...很尖锐的指出每个队伍的不足...我们当时认为肯定会有人上去揍他...还好大家都很理智^_^开个玩笑.

下午颁奖大会,倒觉得没什么意思了...这里膜拜一下第一名曹钦翔大牛.
十四龄童的表演把全场的气氛带到了高潮...
但对于后面的表演就没啥记忆了...

晚上和Nxun打篮球玩升级,没打完...走的时候我竟然还领先...

2008.08.02 back to home

回家.
路上的事情已经没什么可说的了.有趣的事情也有,比如张老师请客吃麦当劳,比如在动车组的候车室打牌(显然我们坐的不是动车组),比如我们惊奇的发现买到的车票都是下铺中铺而没有了上铺.不过这一切相比这几天的美妙记忆,已经黯然失色.
回到家里,才发现可以勾起记忆的东西已经丢了很多,不知道丢在哪里.现在只剩下了那个书包,还有这篇文章.
其实都无所谓.经历过就够了.

FINALE

你可以成功,你也可以失败;你可以选择退役,你也可以选择继续;你可以酣畅淋漓,你也可以痛哭流涕.但无论如何,请记住,你是一个OIer.永远没有退役,因为我们永远是朋友.

NOI,不说再见.

update:突然想起来 Day1和Day2中的某一天 我上机的密码条竟然有三位是SQY 囧死了 估计现在写出来没人看得到了吧 自己能看到就好了 以后别忘了

确定性有限状态自动机,又称确定型有穷自动机,Deterministic Finite Automaton,DFA.
这两天blogbus那个blog上有一个人找我要DFA的代码,这里干脆直接贴出来.加上了一些注释,还有DFA的简单介绍.写的很简略,也很难懂(=_=),请凑合看...

DFA的基本思想就是建立一棵Trie树,然后用BFS求出每个结点的前缀指针,再跑自动机...
我见过的用法,一个是多模式串匹配,另一个是自动机上的DP(见URAL 1158).这里只介绍多模式串匹配...

从最后开始说...假设我们构建了一个DFA,我们怎么跑呢?
首先了解前缀指针:假设有一个节点k,代表的单词(就是从根结点走到k结点经过的边上的字母连起来)是串s1.而k的前缀节点trie[k].pre代表的单词是s2,那么s2一定是trie树中存在能够作为s1后缀的单词中最长的一个...
跑自动机的时候,只要用母串在模式串建立的自动机里,每次对应母串的一个字母移动一格(如果移动不下去就移动到前缀指针并继续移动),然后移动到结点i之后,将i的所有前缀指针和前缀指针的前缀指针标为已访问.
最后只要模式串单词的结束结点被访问过,就说明这个模式串出现在母串中了.
可以发现,如果改成一个模式串,DFA和KMP是完全相同的.

关于Trie树的建立不说了,说一下前缀指针的建立:在Trie上BFS,一旦BFS到新的结点k,且k的父亲到k的边上字母为ch,那么这个结点的前缀指针这样来查找:首先记录i等于k的父亲的前缀指针,然后循环判断i有没有ch这条边指向自己的孩子.如果有,那么k的前缀指针就是i的这个孩子;否则i<-i的前缀指针.
可能这样说不是很清楚...但我想不出怎么在没有图的情况下说清楚...

然后DFA算法就这样...没什么太难的...几十行代码的事情...
还有个很好玩的事情...我一般用RK和DFA分别处理多维和多模式串匹配的问题...所以对于单维单模式串,我一般会从这两个里选一个(大多数情况是RK),对于我KMP就没啥用了...

最后贴代码.

/*
  确定性有限状态自动机(多模式串匹配); DFA
  - sqybi's code
  - 输入格式:
    第一行一个数n,代表母串长度;
    第二行一个字符串a,代表母串;
    第三行一个数m,代表模式串个数;
    接下来m行每行一个字符串b[i],表示每个模式串
*/
#include 
#include 
#include 
 
using namespace std;
 
const char chSt = 'a', chEd = 'z';
 //描述一个字符集,输入的串只能用此字符集
const int nn = 100000, mm = 1000, kk = 1000, cc = chEd - chSt + 1;
 //母串长度,模式串数量,模式串长度,字符集大小
 
struct trieNode
{
    int son[cc]; //trie的结点每条边指向的孩子编号,0为此边无孩子
    int pre; //前缀指针指向的结点编号
    bool visit; //该结点是否被访问
};
 
int n, m, now, tmp, trieNum, qs, qe;
 //不一一列举了...
string a; //母串
vector< string > b(mm); //模式串
int bLen[mm], stop[mm]; //模式串长度,模式串终止结点编号
trieNode trie[mm*kk+1]; //trie树
int q[mm*kk+1]; //BFS的队列
 
int main()
{
    ifstream fin("dfa.in");
    ofstream fout("dfa.out");
 
    //input
    fin >> n >> a;
    fin >> m;
    for (int i = 0; i != m; ++ i)
    {
        fin >> b[i];
        bLen[i] = b[i].size();
    }
 
    //build Trie
    //注意这里有一个0号结点,其实只是为了前缀指针构建比较方便.
    //如果一个结点没有前缀,那么它的前缀指针就会通过0指向1.
    trieNum = 1; //trie的结点数
    for (char ch = chSt; ch != chEd + 1; ++ ch)
    {
        trie[0].son[ch-chSt] = 1; //0号结点的所有孩子都指向1(注意这些边没有实际意义)
        trie[1].son[ch-chSt] = 0; //1号结点厨师没有孩子
    }
    for (int i = 0; i != m; ++ i) //对每一个模式串
    {
        now = 1; //从1号结点开始建边
        for (int j = 0; j != bLen[i]; ++ j) //每次向下伸展一个结点
        {
            if (trie[now].son[b[i][j]-chSt] == 0)
            {
                ++ trieNum;
                trie[now].son[b[i][j]-chSt] = trieNum;
            }
            now = trie[now].son[b[i][j]-chSt];
        }
        stop[i] = now; //记录第i个模式串的终止结点编号
    }
 
    //BFS (build pre)
    qs = 0; //队列首位置
    qe = 0; //队列尾位置
    q[qs] = 1; //开始队列只有一个1号结点
    trie[q[qs]].pre = 0; //它的前缀指针为0
    while (qs <= qe) //如果队列不为空
    {
        now = q[qs]; //处理当前结点
        for (char ch = chSt; ch != chEd + 1; ++ ch)
            if (trie[now].son[ch-chSt] != 0) //对于它的所有孩子
            {
                ++ qe;
                q[qe] = trie[now].son[ch-chSt]; //加入队列
                tmp = trie[now].pre;
                while (trie[tmp].son[ch-chSt] == 0) tmp = trie[tmp].pre;
                trie[q[qe]].pre = trie[tmp].son[ch-chSt]; //以上三句为建立pre的过程
            }
        ++ qs;
    }
 
    //main (run DFA)
    now = 1; //从1号结点开始跑DFA
    for (int i = 0; i != n; ++ i) //每次跑母串的一个字符
    {
        while (trie[now].son[a[i]-chSt] == 0) now = trie[now].pre;
         //如果当前结点没有这个孩子那么就顺着前缀指针跑并继续尝试
        now = trie[now].son[a[i]-chSt]; //向下移动到这个孩子
        tmp = now;
        while (tmp != 1 && (! trie[tmp].visit))
        {
            trie[tmp].visit = true;
            tmp = trie[tmp].pre;
        }
         //将这个孩子和它所有前缀指针和前缀指针的前缀指针指向的结点标记为已经访问
    }
 
    //output
    for (int i = 0; i != m; ++ i)
        fout << trie[stop[i]].visit << endl;
}

看了wincss的校内日志,觉得写的很不清楚...加上校内比较封闭...决定写一个详细些的放到这里.

首先,我们要做到的是,在窗口上画矩形.
鼠标按下并拖动的时候,矩形会跟着鼠标的移动变化大小;等到松开鼠标的时候,矩形就画上了.

首先想到的是在BitMap上绘画并放到PictureBox里,然后MouseMove触发重绘.但这样还要记录一个当前这次鼠标按下之前的图,然后重绘的时候需要在那个图的基础上重绘,比较麻烦,而且因为重绘次数很多,速度很慢.
有没有别的办法呢?

我们可以看一下PictureBox的Paint方法.
Paint方法在每次PictureBox需要重绘(Invalidate方法或Refresh方法被调用)的时候触发,用于重绘窗体.
BitMap不用写到Paint里就能被重绘是因为它会被自动重绘.而我们上面的那个重绘方式每次正是需要在原来图的基础上重绘.这样我们是不是可以在MouseUp之前不改变BitMap呢?
答案是肯定的,我们可以在PictureBox的Paint方法里调用e.Graphics.DrawRectangle方法进行重绘.这样重绘出来的东西会放在BitMap上面,相当于在ImageBox里的BitMap上新建了一个透明层...很神奇的.
然后等到MouseUp被触发,再将矩形绘制到BitMap里并重绘即可.

注意在Paint方法中调用了e.Graphics.DrawRectangle而不是pictureBox1.CreateGraphics().DrawRectangle,后者不可行,它画出的矩形会一闪即逝.

整个程序的代码点这里下载.
代码由wincss编写,本人做了些许更改(主要是从VS08的格式转到VS05,因为我没有08)并加了注释.在VC#2005下编译并运行测试通过.

感谢wincss对本人提供的帮助...
大概有了一个想法 和jl一起编一个有关追逐的游戏 但还不是很成熟 先不放出来了

彻彻底底被屠了.
challenged + challenged + unopened = 0 pts...

250pts,纯水,贪心就行.可我竟然忘记了处理-1的情况...然后Run System Test才发现两个-1的点TLE了.
这道题也花费了我太长的时间...C++用的本来就不熟悉,然后TopCoder的编程环境是那么的别扭(在Code::Blocks里写更别扭)...

然后500pts,据说可以分半DP,我写的搜索,可惜250费的时间太多,500到最后样例还是WA.就是一个V很大n很小(32)的01背包.

1000pts,比赛结束之后我才开了看.模糊记得以前似乎见到过一道这样的题目,是自动机上的DP吗?求大牛解答.

屠惨了...还剩1400多分.蓝了.
其实250如果过了的话应该还可以黄的...

今天效率还是蛮高的.

开始接触C#,在bw的怂恿下写了关于这样一个物理题的小程序来熟悉它:

猎狗追狐狸,刚开始狐狸的速度方向和猎狗的速度方向垂直,而猎狗的速度方向时时刻刻指向狐狸的位置.
求猎狗和狐狸行进的轨迹.

然后瞎写了个东西模拟了一下,肯定不准啦...
然后刚开始直接在Form_Load里面画,结果最大的问题是一启动就画完了,不能看到一点一点画出来的样子.
然后查了半天,才知道有Graphics这个东西.尝试了好久语法,终于可以在form上画出来了.可是重绘的问题没有办法解决,VB有一个窗体重绘的函数,而VC#没有.
于是baidu了一下,发现PictureBox可以完成这个任务.然后改成了new Image上画线,然后扔到PictureBox里.
但是bug来了,画线竟然只画了第一条,后面就没了...
找了半天,发现PictureBox有个Refresh函数.加上这个函数,搞定.

然后就是加了try-catch,加了更改速度的方法(三个textbox),改了颜色.

被我哥bs了...意料之中.我哥希望我拿C#干一些更高级的事情...但我现在却没有这个打算...所以bs就bs吧...
感觉C#的确很像VB,很容易上手.MSDN是个好东西,只不过有时候不够详细.不知道是不是因为我的VS是express?

附程序,仅供玩玩...一点技术也没有,所以如果你抱着要bs我的心态,还是别下载了,因为我不接受除了我哥以外任何人的bs.
需要.NET Framework支持,点击这里下载Microsoft .NET Framework 3.5(zh-cn).

点击这里下载程序.