SQYBI.com

前面一些文章都有一小撮 (别有用心的) 群众留言说看不懂, 为了避免这种囧事出现, 我决定以后多加一点知识性介绍…

小知识: 什么是 SCL?

SCL, 即 Standard Code Library. 虽然不是一个统一的叫法, 但是大多数人都这么称呼它. 所谓 Standard Code Library, 顾名思义就是标准代码库, 一般也称之为代码库.
对于 ACMer 来说, 有一个好的代码库是很重要的事情 — 毕竟 ACM 比赛是允许携带纸质资料入场的, 所以在比赛时带一个代码库可以省去了很多背代码的麻烦, 同时也避免了很多比赛时因为背代码导致的细微的错误.
但是要注意的一点是, 代码库并不能完全避免这些错误, 而且, 使用一个自己不熟悉的代码库反而会降低效率, 同时犯下更多这种小错误 (例如把 i 写成 j 之类的, 究其原因还是不理解别人代码库里的代码, 生搬硬套是不好使的). 这也是为什么一般 ACM 的队伍里都会有一套自己的代码库.

最近实在觉得自己太颓废了 (颓废到 blog 都懒得写), 于是决定干点什么.
本来是想搞个短期任务的, 但是听 oldherl 说队里在写 SCL, 想想自己一直在用别人写的 SCL, 干脆也开始写个 SCL 吧.

其实之前试图写过好几次了. 当初用 pascal 的时候, 就曾经总结过代码, 不过总结了几年也就是 Dinic 啊 Hungary 啊 quicksort 啊这类的东西, 代码也零零散散的, 没有任何可重用性.
后来保送了, 转了 C++, 觉得类这东西挺好用, 于是想搞一堆头文件把要用的代码都封装到类里. 结果一个代码都没搞完就发现工作量太大, 而且也不适合 ACM (代码量巨大, 从而导致拍起来太慢), 于是不了了之了. 似乎 shouhm 现在也想做这件事啊, 前车之鉴在这儿了, 要是你看到这篇文章的话自己考虑考虑吧…
接下来就是从 zmc 那儿拿到了一个代码库, 是交大的一个叫 Hao Yuan 的学长写的 (谁告诉我这人是谁…). 东西很全, 也是我这段时间一直在用的代码库. 然后当时就按照那个代码库里面的内容列了一个 list, 然后搞了个 ASLP (Algorithm Summary Library Project). 结果呢, ASLP 里到现在也只有一个最大匹配的代码, version 还是 0.0.1…
然后我又无聊地在 Google Docs 上搞了一个代码库, 还 share 了出去 (传送门). 结果还是我和 zmc 俩人一人贴了几小段代码, 然后就久久不更新了… 但是我对这个东西前面那段大致规范还是比较满意的, 虽然我自己做出来的这个代码库为了方便肯定不能完全参考这个规范吧, 不过以后如果真的要是几个人一起写一个代码库这个规范倒是可以直接拿出来改改的.

而这次写 SCL, 我可不想再半途而废了… 毕竟之前也就是玩玩, 这次可是要写一个以后或许会经常用到的东西. 所以给自己暂时定的目标是, 尽量每天都要更新. 先试试吧, 反正手里还有另一份 SCL 作辅助呢, 写起来容易得多. 刚刚封装了一个高精度的 class, 感觉还好. 测试代码库的问题不太好搞定, 所以先放放吧, 等写完了再统一测试.

代码库放在网上了, 下载地址如下:
点击下载代码库 pdf 版本
点击下载代码库 odt 版本
点击下载代码库 zip 版本
其中 zip 版本是原始的 cpp 代码的压缩包.
正如前面提到的那句话, 使用一个自己不熟悉的代码库反而会降低效率, 同时考虑版权问题 (当然我几乎无视它啦), 这个代码库还是仅仅作为一个参考的好, 自己写的才是王道.
上面几个地址一般来说会不断更新, 但是由于使用了 SJTU 的 FTP, 所以不一定啥时候就删掉了或者不更新了.

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

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

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

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

所谓平生第一套 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.交大这次除了一队, 队名都好诡异…

前几天 blog 挂掉了, 当时就想到了可能是 sql 数据库地址的问题. 但是 ftp 一直登不上, 我这儿上网又不是很方便, 昨天才把两个问题一并提交到客服, 然后虽然 ftp 的问题还没解决, 但是第一个问题确定了是 sql 数据库地址有问题, 客服也帮我在他那边改过了. 然后今天用速度有点慢的 webftp 装了个新的 wordpress 2.8, 折腾了一下午总算弄完了.

最近训练还好, 具体就不多说了. 然后已经得到了通知, 要 8 月 10 号左右才能回去, 到时候不知道还有多少人没玩腻…
过几天事情很多, ACM 班的面试, 提前入校的期末考试, ACM 队的训练, 加上现在还不知道要搬到哪个宿舍, 于是能预计到过几天的忙乱. 而原先定的 7 月回去一趟的目标, 估计是实现不了了.

这几天上海突然热起来了, 貌似 N 多人都是半夜两三点睡不着觉… 我今天也是凌晨 3 点才睡着的. 还好的是, 白天一直有 ACM 机房可以泡. 貌似大多数人都在泡图书馆, 不过 ACM 机房里有空调, 加上人比图书馆少, 所以还是这里好. 某人语: 早知道我就去考 ACM 队了…
电脑前几天显卡挂掉了, 跑到徐家汇去修. 然后第一天送过去修, 回来的时候淋了一身的雨, 第一次知道了啥叫落汤鸡= =||. 第二天去取, 中午去的, 然后第一次知道了啥叫热的要死… 回到宿舍之后喝了三四瓶水跟没喝一样… 不过还好电脑现在正常了, 花了 600 多块钱啊, 我电脑现在卖都不一定能卖这个价…

然后今天做了做 UVa, 换了个新 ID. 把那个推荐列表里整百的题都做了, 结果发现没有一道题不是水题, 晕死…

别的也没啥了, 最近貌似比较多愁善感, 不管怎样还是像我所说的, 你们真的不会明白我有多想你们的, 我也不会明白.
回去的时候还能不能去以前的教室看看呢…

题目很恶心,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多人晋级面试,唉…