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月, 还有时间.

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

真的好久没有更新了呢, 快一个月了吧.
这篇 blog 只说刚刚结束的 WF 的事情, 不会很长, 别的我要是不困再写一篇.

知道今天有 WF 也是下午回家之后的事, 然后立刻开 ranking 观战. 这时有人发来一个视频直播的链接, 打开看了, 很卡加上半懂不懂的英语解说, 我获得的信息基本还是来自 ranking 的.
当时一直关注着 SJTU 的尴尬的 2 题, 然后就发现 tsinghua 在前面也停滞不前了. 接下来就是眼睁睁的看着 tsinghua 被一次次的赶超.
然后 tsinghua 貌似出了一题, 但是很快就发现 ZJU 赶了上来… 这时 TJU 都跑到了 SJTU 的前面, 真的很尴尬. 直到 FROZEN 的时候, ZJU 是 rank 5, TSU 是 rank 6, 而 TJU 和 SJTU 都是 3 题 (似乎快封板了才搞出一题?), 排在好几十名, TJU 貌似更靠前.
然后 FROZEN, 接下来就是一边看亚冠一边期待…

刚刚看完亚冠回来的时候, 群里对比赛结果有 N 种说法… 最后在饮水思源上看到了 JinBin 的发言, 基本确定了 tsinghua 最后是第二, 似乎是最后时刻爆发了, 做出了9题 (封板的时候第一名是8题, 第二名6题, tsinghua 是第6), 不过还是因为罚时只拿到了第二… ACRush 教主竟然拿了两个第二, 真的不知道说什么好… 听说楼教主当时哭了, 其实我也想哭了…

可能记得不是很清楚, 有不对的地方, 但大致的进程就是这样…
ICPC 真的很刺激… 终于又一次发现了它的魅力… 团队协作的比赛, 还是比 TC 那种单打独斗更加令人痴迷, 令人陶醉.

就是这样. 最终圣彼得堡的一个什么学院拿了第一, 清华第二, 圣彼得堡大学第三. 浙大拿到了第六, 赞一个. 而交大最后是并列第13, 很无奈.

友情提示: 本文没有任何实用价值, 请自行决定是否观看本文, 或者直接拉到最后 (不过估计我写不了几行).

虽然说就要进大学了, 但是还没有个新的面貌啊.

Blog 已经两周一次更新了, 足以体现现在我有多么懒. 整天玩游戏, 上校内, 切题, 过得毫无感觉.
Boss 那儿给了不到 20 道二分图匹配的题, 竟然前两道题都没有 1Y, 我真弱智.

嗯还是说正题吧. 开始为 ACM 做准备了. 虽然听说了 SJTU 的 ACM 队很难进, 不过还是有一些憧憬的. 毕竟大一的同学里只有这些 OIer 在竞争, 虽然个个都是高手, 不过自己也不能就这么放弃.
然后呢, 现在很无聊, 于是想为以后的 ACM 准备个用户名. 主要是在各个 OJ 上的 sqybi 的刷题记录没办法清除, 所以换个用户好知道自己哪道题还没做过… 毕竟以前做的题现在不一定还会了.
现在在用 sqybicpp, 看着就难看. 所以自己准备了一些用户名, 欢迎留言告诉我哪个好, 或者有更好的创意也请告诉我…

ssjqtyu – sSjQtYu
sqeezey – SQeezeY
saqcym – SaQcYm
crapixo – cRaPiXo -> RPX -> (R+1)(P+1)(X+1) -> SQY
sterizy – sTeRiZy -> TRZ -> (T-1)(R-1)(Z-1) -> SQY

后面是解释.. 基本就围绕着 sqy, sjtu 和 acm. 貌似 crapixo 还比较好看… ssjqtyu 那个就很难看…

另外, 最近做题要顺手整理代码了, zmc 给我的那份代码库简直太强大了… 不过还是自己整理的代码用着舒服.