SQYBI.com

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

2009年07月24日
by sqybi
23 Comments

SRM 445

赛前定下的目标就是, 保住黄色. 然后拖着疲惫的身躯打完整场比赛, 坚持到了 rating 更新再睡觉 (幸运的是 System Test 很快, 没让我等太久), 也见证了自己的 rating 第一次突破 1700. 可以说很令我满意了, 不过却一点也高兴不起来.

让我耿耿于怀的就是那个 250 (275?). 当时拍出了一个自己也不知道对不对的程序, 按照平常的习惯, 我是万万不敢 submit 的, 除非是比赛最后时刻. 但是当时翻了一下 Room Summary, 发现那道题还只有 zhuojie 一个人提交, 不知道怎么就点了 submit.
感觉那一刻的自己像极了灵山仙人洞里的景天, "只是想痛痛快快地打一场罢了".
当然了, 结果也很像. 不过如果每次都这样, 结果不像的那一天迟早会来临, 而且肯定不会迟...

其实之前并没有发现自己这么地依赖 ACM. 因为那种原因被 ACM 队踢掉真的十分不爽, 甚至不能用不爽来形容了 -- 可惜我找不到更合适的词. 也只有这几天跟久违的同学们在一起的时候, 我才能稍微忘掉这些放松放松.
可是, 这样下去也不是办法. 现在已经痛痛快快打了一场了, 也该是回归正轨的时候了.

下次 SRM 是8月, 还有时间.

2009年07月20日
by sqybi
10 Comments

终于基本搞定了生平第一套PHP应用程序

所谓平生第一套 PHP 应用程序, 也就是我搞的那个同学录的程序. 今天刚刚完成了留言板系统, 功能的开发也就告一段落了. 接下来要做的, 也就是各种 bug 的修复之类的事情了.
之前 PHP 的东西只给 Mgccl 开发过一个并查集的模块, 并没有太多接触. 这次是看 Nxun 在搞, 加上被 ACM 队踢掉了时间比较充裕, 所以就尝试搞了一下. 不得不说, 写这种东西和 ACM OI 差别还是很大的. 不过搞竞赛的时候攒下的一个优势, 体现的可是淋漓尽致了, 那就是代码能力.

php 这东西可真恶心, 本来刚开始还想尽量保持良好的代码结构, 后来发现完全是妄想... 不过还好, 程序结构本身并不复杂, 基本上还可以看懂自己写的代码. 真不知道应该怎么搞才能让代码看起来正常点...
另外我的模块化做的还是不够, 直接导致的后果就是, 做同样一件事情有两套逻辑顺序不同的代码来完成... 而且我这套系统关于 cookie 的处理也比较诡异, session 也是用 cookie 代替的. 但是无论如何, 安全性暂时没啥太大的问题了. 还要谢谢 Nxun 帮我找到一个注入漏洞.

整个程序搞完了, 中间遇到的问题也不少. 大概有这些:
SQL语句: 这个比较囧, 每次用到的时候都要去查. 不过现在大概能记住 "SELECT * FROM xxx WHERE yyy = zzz ORDER BY aaa, bbb" 这样的语句... 也差不多够用了.
字符串处理: 之前一直在用一个 SQL 的函数搞防注入, 后来发现可以用 addslashes 等几个函数... 不过最后还是没有搞 HTML 代码屏蔽, 这样除了管理员页面可能会有点危险以外, 别的地方还是不会有太大问题的.
include: 这个是比较悲剧的, 刚开始不知道 include_once 于是全篇 include... 系统还不是很大时没啥问题, 从系统做大开始, 就出现各种函数已经被定义的问题... 于是搜到了 include_once 和 require_once. 但是听说似乎最好用 require_once, 反正我是都用了 include, 应该问题不会太大.
CSS: 这个其实是比较复杂的一个部分, 也是在 Nxun 和 sofish 的帮助下才都搞定, 加一个 div 清除浮动以达到高度自适应简直太脑残了... 真不知道浏览器都怎么设计的. 到最后也懒得处理 IE 6 的 padding 和/或 margin 的问题, 所以 IE 6 访问的时候页面布局会有一点小问题, 但是还可以看.
大概就是这样, 别的问题肯定还有, 不过想不起来了.

下一步除了维护这套系统, 还准备给自己写一套相册系统. 那个就不用考虑太多安全性问题了, 反正那种系统被注入了也没什么可以拿走的东西, 跟同学录可不一样. 估计写起来会方便很多.
最近也得找点比赛做了. 虽然大一应该是没有分区赛可打, 不过现在可是下定了决心大二要参加的. 所以这一年最重要的就是要保持状态, 不出意外的话会跟队训练, 同时自己平时也得多做题. 大家都要加油~
p.s.交大这次除了一队, 队名都好诡异...

2009年05月25日
by sqybi
11 Comments

交大ACM队机试结束

题目很恶心,7水+2难.结果就是N多人都是7道题,7道题主流啊...qujun这种做了7道题结果因为全场最水的G题看错题而排名靠后的就悲剧了...

A题,给出C个字母,要求输出由这些字母所有满足下列条件的字符串:所有字母升序排列,每个字母只用一次,长度为L(L<=15),单词里至少有一个元音两个辅音.
这道题因为刚开始状态不太好卡了一会儿,不过最后还是比较顺利的搞出来了.

B题,给一个01矩阵,问有几个连通块(只有上下左右连通才算).
简单的BFS.

C题,给一个5*5的数字矩阵,从任意一点开始每一次向上下左右的任意一个方向走一步,可以走重复的格子,经过6个格子之后会得到一个六位数.问总共可能得到多少个不同的六位数.
纯搜索.

D题,题目描述比较恶心,反正就是给你一堆矩形叠在一起的影子,问最少多少个矩形能够叠出这样的影子.所有矩形都是放在地面上的.
用链表维护一下就行,题目稍微长一些,但是很简单.第一次写写错了,写的算法和想的算法不是一个...走神了啊.不过还好,后来改对了.

E题,有N头牛,每头牛都有一个强壮指数和重量.现在把它们按照某个顺序叠起来,每头牛计算一个上面所有牛的重量之和(不包括自己)减去它的强壮指数,问如何所有牛的这个值的最大值尽量小,输出这个最小的最大值.
刚开始还以为是二分答案,后来想到了贪心是把重量和强壮指数加起来,大的放在底下,但是没法证明,第一次submit还错了.后来发现第一头牛的这个值应该是负的自己的强壮指数,改了再交就过了.但是没完整地证明出来(只证明了三头牛是正确的).

F题,给定函数f(a),计算方法是:把a的最后一位挪到第一位前面,然后平方,再把结果的第一位挪到最后一位后面.问第N个满足条件f(a)=a^2的a是多少.
写个暴力找下规律,就可以发现是1,2,3,21,221,2221,22221...于是直接输出就可以了.

G题,全场最水的一道题.就是给定N个点,两个点之间有个某某概率为1/sqrt((x1-x2)^2+(y1-y2)^2+(z1-z2)^2+1),问最后一个点和前面所有点分别算这个概率,最大的一个概率是多少.
只需要把最后一个点和前面所有点的概率分别算出来然后找个最大的就行了...很可惜,因为是个人赛,所以没办法刚开始就看完所有题...基本上每个人都是最后才做出这道题的.还有很多看错题,求了所有点对之间的...那些人很悲剧...

然后是两道不可做题.

H题,要求求出一个序列{a_n},满足sigma(i=1~n)a_i=x,sigma(i=1~n)a_i^p=y,而且sigma(i=1~n)a_i^q尽量小.输出这个最小值.
数论题,我是直接放掉了...

G题,给一个有向无环图,给四个点abcd,四个点的编号都不同,从a到c和从b到d可以找到一对不相交路径(就是没有公共点),问这样的路径对有多少种.
这道题写了个暴力交上去,然后眼睁睁的看着前面的judge拿我的程序跑,大概在第三个点TLE了...然后给我return了一个TLE...于是就再也没想出来...

大概就是这样,题还是很水的了.最后排在所有人的第13名,比笔试退后了两名...不过据说这次又会有N多人晋级面试,唉...

2009年03月15日
by sqybi
21 Comments

武汉大学百度杯比赛惨败

为了方便搜索引擎, 列出全名:
百度杯 第四节华中北区程序设计邀请赛
The 4th Baidu Cup Central China Invitational Programming Contest

比赛也算是比较圆满的结束了 (如果不考虑比赛过程中不断的 HTTP 503 / 500 的话), 挂的也是够惨.
据说除了校内队伍取 40 支, 然后我们总排名第 54. 还有一丝希望晋级吧. 已经被淘汰了. 也好, 轻松了.

不想再发泄什么因为我晚到半小时导致比赛结束 10 min 才出 I 题的事情... 昨天发泄够了也在校内被 bs 够了. 当然当时没 bs 够的还可以接着来这篇文章底下留言 bs... 我现在心情至少比那时候好.

正式比赛里, gnocuil 牛领衔的 E.W.F. 队没有如愿拿到第一, 第一被 jby 神牛的 Gold Kylin 抢去了... 第三竟然是 cqf 神牛, 不知道做题的时候神牛有没有用到 SBT 呢... 第四不认识, 第五是 xt 神牛, 果然中学队伍比较强大.
然后强力的 wh 拿到了第 16, orz一个. 啊, 忘了说, 然牛貌似是第 12 啊. And, rank 13 是姜里羊神牛. 能认出来的貌似就这些.

比赛刚开始, 我就迟到了... 等我到的时候, 比赛已经开始了半小时, 貌似有很多队伍都出两三道题了. 而 zmc 也过掉了 G (似乎是水题, 我没看题).
到了之后我就鬼使神差地开始写 E (一个不是太恶心的枚举), 还鬼使神差的读错题了. 于是贡献了 4 个 WA 以后才 A 掉, 这也就导致我们在出 4 题 5 题的时候, 排名一直是最靠后的.
在我 submit E 的同时, zmc 也在做 J (据说是弱智DP). 然后我在 E 多次 submit 都 WA 的情况下, 最终开始搞 H (纯水题, 排序), 在使用了大量 STL 的情况下 (map, set, vector, pair, algorithm, 基本上 1/2 的程序行都有这些东西), 终于 2Y 掉. 而在 Y 掉 H 之前, zmc 和 Nxun 找到了 E 的问题, 就是读题读错了 (关于该黑棋还是白棋走的问题). 于是 E 题也过掉. 紧接着, zmc 也过掉了 J.
然后, Nxun 就开始折腾那道不太该折腾的题, F (根据化学式计算相对分子质量, 需要高精度). 这道题直到最后也没搞对, 最终确定是高精度写错了. 而我正好发现了 D 题 (Cipher 加密法) 是我曾经给 FNOI 的小朋友们出过的一道题 (瀑布汗! 我当时出的是解密, 这里要求加密), 于是赶快写, 1Y 掉. 这道题本该早写的, 但是当时看 AC 人数比较少所以都没看题...
接下来的时间就是每人一道题慢慢磨的时间了, zmc 是 C (恶心计算几何貌似?), Nxun 还是 F, 而我是 I (SCDP). 最终三道题一道也没出, 比赛结束 10min 后搞出了 I. 错的原因也在校内说过了, 数组开小了 1. Shoot.

这次败得够惨, 顺便膜拜搞出 A (双向宽搜) 的牛们.

顺便提一句, TCO Round 1 我就被淘汰了, 最近状态 ttm 差了...

2009年02月26日
by sqybi
21 Comments

游戏推荐: 韦诺之战 (Battle for Wesnoth)

貌似是 blog 上第一次专门写一篇文章推荐一款游戏啊. 不过 Battle for Wesnoth 的确是我见过的最好的一款开源游戏了.

Wesnoth 是战棋类游戏, 地图的每一个格子为正六边形, 对战模式的地图存储为文本文件 (也就是说只要了解了不同的字符代表的意义, 你可以用任意一个文本编辑器去编辑 / 制作地图, 不过战役模式则不同). 一个特点是, 所有的单位都只能够攻击相邻格子的单位, 而攻击却有两种, 近身和远程, 当攻击者用其中一种进行攻击的时候, 防御者也只能用对应的那种防御.

单位的种族有很多 (貌似六个?), 而战役 + 对战的模式使得 Wesnoth 变得十分好玩. 对战模式又分为网络对战和本机多人对战, 后者还可以有 AI 的参与, 每个 AI 都是一个 Python 代码, 你可以自己编写一个 AI.

如果想要玩一玩, 直接到官网下载程序和各种地图, 大部分 Linux 用户可以直接从源里安装, 或者你也可以从 SVN 下载并编译.

战役和对战都玩了, 因为我玩的战役 (South Guard) 大部分都是控制人族单位的, 所以对人族了解稍微多一点, 给没玩过的朋友稍微介绍一下.
弓箭手, 这个我刚开始时大量招募的单位, 网上说很鸡肋. 我开始不太觉得, 但是打到 South Guard 的倒数第二关 (盗贼支线) 的时候终于发现很难用了 -- 即使升到了三级, 依然一打就死, 虽然远程近程都不弱, 但是血薄是它的致命弱点, 强烈不推荐. 不过打一些零星的类似人族重甲的血厚却没有远程攻击的单位还是有一些用处的 (不过基本也是一个甚至几个换一个).
矛兵, 最经济的单位. 刚开始看它的远程比较弱, 所以不喜欢招募, 后来发现它守城还是有很大用处的, 因为即使是防御的时候, 它也会率先攻击. 价格不是太贵, 升级之后也比较强, 加上血不是太薄, 多买些没坏处.
骑兵骑手, 两个移动极高的单位. 区别我也不太清楚, 貌似骑兵更适合侦查, 而骑手更适合打游击.
重甲步兵, 也就是前面提到的 "重甲". 血比较厚 (实际上和骑兵骑手一样), 近程攻击强 (单次攻击耗血量大), 移动速度慢. 实际使用中还是配合矛兵防守为好, 最好旁边有法师补血. 感觉这东西如果出就要攒够钱一下子出好几个, 不然一两个很快就会被对方的远程部队干掉. 还有, 我曾经试过在对战中用重甲加弓箭手拼AI的树人 (精灵族一个类似重甲但是攻击力更强一些的东西), 输得很惨.
法师, 血薄, 不过远程攻击是魔法攻击, 对任何单位都有 70% 的命中率. 而且能够给周围的单位补血. 如果足够有钱, 一个法师周围一圈重甲再外面几个骑兵矛兵扫荡, 比较爽... 当然能出这些兵的时候估计已经赢了...
剑术家, 生命不多, 攻击力不高, 有稍微高一些的闪避和速度. 如果是一个普通的单位, 貌似没有什么存在的价值 -- 不过它有一点却是无人能比的, 那就是无视控制区域. 在 Wesnoth 里, 如果前方有一个敌人, 那么那个敌人周围的几个格子是不能通行的 (也就是不能通过敌人身边的格子绕到敌人身后), 那些格子叫做敌人单位的控制区域. 而剑术家可以无视控制区域, 这表示如果敌人的 boss 在血不多的时候被几个敌人单位用控制区域围在了中间, 剑术家依然可以攻击到敌人的 boss 并完成致命一击. 当然, 招募多了也没啥用.
基本就是这些.

我在战役 South Guard 里卡在第 6 关了. 正如上面说过的, 我选择了和盗贼结盟的支线. 在第 5 关的时候, 已经和精灵结盟的你会面临一个支线选择, 如果选择和盗贼结盟, 精灵就会和你反目成仇, 你需要和盗贼一起打败不死族; 反之, 你需要和精灵联手打败不死族和盗贼. 从网上为数不多的评论看来, 精灵支线会比盗贼支线好打得多. 虽然精灵支线会导致必须一直打到第 9 关才能结束, 而盗贼支线貌似只有 7 关, 不过盗贼支线的第 6 关 (就是我在卡的那关) 十分困难. 这关里, 需要和盗贼一起 (实际上盗贼的单位都很弱, 基本没用, 而盗贼首领也很弱, 还需要保护它) 同时突破精灵和不死族的阻击从地图右下角到达左上角, 回合数也是少得可怜的 40 回合. 我即使到最后使用了大量的牺牲战术牺牲了很多个三级兵 (有大部分是弓箭手, 三级弓箭手仍然无法用来抗血), 还是回合用尽 (差一点就到了啊啊啊) 输掉了战役. 最关键的是, 大片森林地形对精灵和不死很有利, 我十分无奈...

说了这么多, 还是去玩玩吧... 至少应该不会让你失望的.

p.s. 为啥还没收到 SJTU 的预录取通知书... and, whu 的那个比赛, 问了一堆人, 想去的只有我, zmc, Nxun 和 xhy 四个人. 发现什么了没有? 我们四个都是 SJTU 的! 十分无语啊, SJTU 的人都这么喜欢比赛么...