SQYBI.com

Change is a part of life, and takes part in finding us who we are.

2008年10月09日
by sqybi
7 Comments

SRM 421

正如校内状态所说,每次SRM之后状态难道都要改成"被虐了"?! 这次碰到了winsty所说过的精度题(也就是实型下二分答案),在改了好长时间之后还是WA掉了,仅仅错在一个测试点. 实型二分答案以前从没写过,所以挂掉了也很正常了. 然后500pts果然恶心,过掉前两题基本可以进top 100了.做法更恶心,一个贪心.但是我没法证明正确性.这道题又像lamppost(FNOI的小盆友们应该有知道的吧)又像road(TJOI 2007 Day 3某题),而这两道题都用了二分答案.但实际上这道求最大差值最小的题目并不像以前的最大值最小的题目都用二分答案--它只是一个简单的贪心. 以前不知道最大值最小用二分害过我一次,这次知道了最大值最小用二分又害了我... 1000pts是不可做概率题,貌似整个div就7个人做了,还有2个人fail system test了.在这里膜拜ahyangyi神牛. 又一次暴0,于是郁闷掉.再这样下去,一两场就跌到div 2了. 这几天考虑开始一些训练,一直不做题果然不行. SRM 422,一定要涨回来!争取变黄~ Go go +U~

2008年09月12日
by sqybi
13 Comments

TopCoder SRM 417

继SRM 415暴0,SRM 416因为晚开了几分钟没注册成之后,SRM 417上,我又华丽地暴0了... 这套题目给OI(也就是可以开题看所有题)的话估计期望是做出两道题(250和1000). 题目很黑,250pts虽然一如既往地水,但是500pts竟然那么难,以至于很多人没开1000pts...我在最后几分钟开的,然后发现是一个裸的Floyd...囧掉.不过不知道为啥room里唯一做了1000的人fail掉system test了. 250挂的很无语.发现错误,然后已经改对了...刚要点submit就到时间了... 结果第一个被cha掉,意料之中的. 这次的算法: 250pts,暴力.刚开始估计错了text的子串数量,后来经winsty提醒才发现总共也就几千个... 500pts,人肉出11组本质不同的解,剩下的就是旋转翻转匹配.没了. 1000pts,暂且认为是Floyd.至少我没发现这道题有阴人的地方. 总结三点: 1.做250一定要坚决果断,一定要确定这就是暴力的题...TC!=OI... 2.没有保证250调过就不要开500. 3.想出来一个算法不要立刻实现,多花点时间分数低点无所谓... 果然做TC的经验要慢慢积累.现在还是OI的思路,根本没法刷rating(rating是浮云...浮云...),甚至没法保证得分...唉... 后面几次TC的目标是保住250,争取500,争取重回yellow...(其实掉到Div 2再回Yellow更容易些...) 另外250pts没submit的一个小客观原因:鼠标滚轮突然坏掉,只能自己拉滚动条...囧死了. 过两天还得买新鼠标去...

2008年08月29日
by sqybi
26 Comments

NOI 2008 summary

沉寂了快一个月了,终于想为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牛是长得最正常的... 还有啊...当时张老师找我借书看...于是我就把黑书借给了她...没想到...我忘记了自己把几百块钱夹在了里面... … Continue reading

2008年08月28日
by sqybi
9 Comments

确定性有限状态自动机(DFA)

确定性有限状态自动机,又称确定型有穷自动机,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 = … Continue reading

2008年08月27日
by sqybi
8 Comments

如何用好C#的Paint重绘

看了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一起编一个有关追逐的游戏 但还不是很成熟 先不放出来了