SQYBI.com

最近一直在瞎折腾, 不过也算是折腾了一些有用的事情.

首先是 TLE, 结果出来了, TESTGEN 那题竟然0分, 名次最终下降了两名, 不过还是可以接受了.
超过我们的那两个队伍中, 有一个是 TESTGEN 一题得分第一的队伍.

然后 Fedora 在前几天 update 的时候挂掉了, 据说原因是内核版本更新了, 而源里的驱动版本没跟上. 而且貌似 fedora-zh 上也有人有同样的问题. 本来想换个发行版, 结果一个偶然的机会不知怎么就进了 Fedora 了… 于是在 oldherl 和 WC_111191 的帮助下, 下载 nVIDIA 驱动, 编译安装 (这中间还出了点小问题), 成功. 看来 Fedora 还得用不少日子了, 如果过段时间换的话, 我准备在 Mint 和 Arch 中选一个.
不过不爽的是, iBus 在我编译完 Python 2.6.1 之后挂掉了, 也不知道和 Python 版本变化有没有关系. 现在暂时用 scim-python 了, 但是无论是 iBus 还是 scim-python, 都比 Windows 下的输入法烂得多… 啥时候 Google 拼音或者搜狗拼音能进驻 Linux 啊…

这几天大部分时间在 Fedora 下工作, 最大的一个好处就是这样基本不玩游戏了.
而这些时间里也熟悉了一下 Emacs, 感觉快捷键太凌乱了, 而且找不到一个太好的教程 (也是因为它的功能太多了). 所以准备学习 VIM, 至少不用按那么多 Ctrl / Alt (另外我是知道为啥用 Emacs 要把 Esc 绑定到 CapsLock 了).
同时筹划着安装 TeXLive 的事情, 不过的确对自己配置中文没有信心, 加之最近基本用不上, TeX 还是放放好了.

今天弄了本软件工程的书来看看, 结果发现真的很无聊… 果然我不会对付这种长篇大论的东西啊.
说到无聊, 货币战争也让我看得头昏脑胀的. 还好坚持下来了, 现在已经差不多快看完了. 总的观点就是, 这东西也就看看, 有点太夸大罗斯柴尔德家族了.

在这儿特别感谢一下 oldherl, 最近给了我很多帮助, 除了帮我折腾好了 Fedora (300多行的聊天记录啊), 还耐心地为我 (和crazygir1) 讲解了他的 Linux 经历 (“一个 Open Source 大牛的成长历程” — crazygir1 语) 以及 SVN 和 lowsars 开发的事情.

明天开始就要给 wjf 讲电脑操作的一些基本知识了… 还是要讲 Windows 的, 估计如果给他讲 Linux 然后出现我这种驱动挂掉的问题, 他得把我杀了… 何况作为老师经常要处理 doc 之类的文档… 不过我讲啥好呢…

打这篇文章的时候, 左 Alt 突然坏掉了… 很无奈. 过几天又要换键盘了…

在 Linux 和 Windows 下都禁用了 Firefox 的 TwitterFox 插件, 转 twhirl 了…

BTW, 和 Baiger 学姐讨论到的一个问题, xhy 说他已经收到 SJTU 的预录取通知书了, 为啥我还没收到呢…

昨天搞完了 Time Limit Exceeded, 现在还有一道题TESTGEN没有测试, 其余题目我们 YaohuaFree 的 Rank 是 41, 得分很诡异地竟然是 1234 分 (Rank List). 还算可以接受吧, 不过很可惜最后还是没有达成超过 lonelycorn 和搞掉 CLASS 这两个目标.
简单的说一下题目.

1. Key to C (KEY)
   这道题是我们第一道出的题目, 也是搞得最久的一道题目, 不过事实证明这道题根本拉不开分差 — 最高的 154 分, 而我们 126 分就 20 多名了. 和其他的题目的 rank 1 动辄上千分比起来, 这道题做了基本相当于没做.
   题目要求读入一些数, 判断它们的二进制表示是否回文. 评分标准和很多东西有关, 比如程序中关键字的个数 (这个权重最大), 比如空格个数, 比如代码长度… 总之这些东西都是越多得分越低. 然后代码回文会得到 extra bonus, 貌似是 4 倍多分数吧.
   基本的做法就是?:操作符加main递归, 貌似 rank 1 那个也就这么做的.
2. Play with Code (SHORTEN)
   给出一个代码要求缩短. 这道题最终也不知道那个代码到底啥意思, 只看懂了一段求素数. 而且那个代码在我们几个人的机器上跑貌似都 RE 掉了… 评分规则是代码长度越长分数越少.
   最终的做法是物理缩短… 也就是 define 一个 for 啊, 改一点变量名啊… 就这样子…
3. Produce the Code (INPUT)
   给出一个输入文件和一个输出文件, 要求写一个程序, 对于这个输入文件能够输出给出的输出文件. 当然可以不理睬输入文件直接把输出文件打出来 (我的第一个 code 的确是这么干的), 不过这样代码长度会很长, 而这道题的评分规则也是代码长度越长分数越少…
   这道题由三个人合力完成… 先是来帮忙的 xhy 同学看出了替换规则 (我就是一直卡在这里), 然后我折腾出了乱序的规则, 最后是木木同学的 coding… 虽然 rank 不高不过做得很爽.
4. #ED (CODEHASH)
   给出一段代码, 给一个 hash 函数, 要求代码输出自身的 hash 值.
   貌似有人用 whitespace 来搞, 不过还是比较 orz 那个 rank 1 的, 就一句代码… 很强大.
   这题我们一点没动.
5. COMPILE ERROR (CLASS)
   我最想做出来的题, 但可惜最后也没做出来.
   要求写一个类 multiply, 里面包括一个函数 mult(int a, int b), 函数的功能是输出 a * b 的结果, a, b 都小于 10000. 变态就变态在不允许用空白字符…
   见到了两种解决方法, 一种是官方的 (之所以说官方因为这道题提示了要用 typedef, 如果认为题目描述的那个 "typedefine a class" 不足以说明问题, 那么自己去翻 forum), 另一种很诡异, 用一个不可见字符替代了空白字符还编译通过了… 据说那个字符是 \f, 从来没见过…
6. PRINT D PENGUIN (PENGUIN)
   给一个字符画, 是 Linux 那个企鹅. 要求输出这个东西.
   基本就是考压缩, 我因为怕编译器没法处理所以只压缩成了可见字符, 但是事实证明编译器是可以处理不可见字符的, 因为 rank 前几名的都用了不可见字符. 我很无奈, 不过可见字符范围的压缩我基本是搞到极限了, 还比较有成就感.
7. PRINT ME (PRINT)
   这道题是前来帮忙的 xhy 写的, 题目要求很简单, 输入一个数, 如果是偶数那么输出代码本身, 否则反转代码输出.
   xhy 写了一个回文的代码, 这样就不用管奇数偶数了, 而且根据题目还可以获得 200 pts 的加分.很不错.
   最后一天用了很短的时间完成的 code, 得分还不低 (貌似是所有题里 rank 最高的一个), 或许是性价比最高的一个 code 了.
8. P=NP (NP)
   这道题的题目描述讨论了半天也没明白, 最终放弃. 直接贴出英文题目描述, 做出来的神牛 (比如 oldherl) 来讲解一下…
   "Given an directed graph, find out the minimal set of vertex such that all vertex not in the set have atleast one edge in the set."
9. P!=NP (TESTGEN)
   这道题是为上一道题出测试数据 (想起 SRM 了), 以上一道题 submit 的代码跑的情况评分. 因为前一道题没看懂, 加上最后还有 10 分钟的时候才开写, 所以输出了一个基本是完全图的图草草了事. 这道题至今还没出成绩.
10. Arbit Code (ARBIT)
    此题做的比较爽. 给一段会 TLE 的代码 (实际测试证明还会 RE), 要求改成能够 AC 的代码. 不知道代码是干什么的, 只有数据范围.
    这道题我们的做法是, 把一个范围内 (刚开始是 1~20, 后来为了测试增加到了 1~50) 的所有输入全部打出来, 然后分析规律.
    刚开始的成果是, 求 f(a, b)的时候, 把 b 从 1 到 a 列出表格, 发现每到 a 的约数才发生变化.
    接下来我发现对于素数和素数的幂, 它们的 f 的变化规律是按照比它小的幂变化 (不太好描述, 想知道的话自己输出几个比如 a = 27 或者 16 就能发现了).
    然后木木又发现了 f(a, 1) = phi(a) (这里 phi 是欧拉函数).
    最后时刻木木大胆猜测:
    当 b = 1 时, f(a, b) = phi(a);
    当 b 不是 a 的约数 (a % b != 0) 时, f(a, b) = f(a, b – 1);
    当 b 是 a 的约数时, f(a, b) = f(a, b – 1) + f(a / b, 1).
    然后写了个 code submit 上去, 挂了.
    差点就认为这个推测不对, 但是本地测试 100 以内的数据发现和给出的程序输出完全匹配.
    最后偶然发现, 有一句要做 t * ((i – 1) / i) (不用说也知道是求欧拉函数时候写的), 我当初写的是 t * (i – 1) / i, 而 t * (i – 1) 会爆掉 int… 改成 t / i * (i – 1) 就 AC 了.
11. Give It a try (THINK)
    这道题是最有意思的, 要求破解三个密码, 没有任何提示.
    第一个密码很简单, 一篇文章, 把里面所有的大写字母挑出来拼在一起, 就是答案了.
    第二个密码是一个 32 * 241的 01 矩阵, 最后也不知道是啥意思, 只知道答案是 2.
    第三个密码, 刚开始一看就感觉是一个简单的 26 个字母的置换, 然后还推出了 p => e, 另外还找到了三个 p 连在一起的一个突破口. 但是无奈没有破解经验, 加上文章里竟然 26 个字母都是齐全的, 让我有点打退堂鼓, 所以没有一鼓作气破解出来, 很遗憾. 其实想想, 当初直接按照统计学的字母出现频率解密, 然后再做微调, 应该都可以把密码破出来了… 很无奈.

比赛基本就是这样, 最后的 1234 分真的不是有意为之… 运气比较好吧.

——————-我是爱情的分隔线——————-

今天情人节, 白天在家待了一天 (本来说要和 lxc, djs 去打台球, 一想今天人应该多就没去), 晚上去 FNOI (还迟到了), 就这么度过了情人节.

放一张图, 从 M67 那里看到的, 来源是 Abstruse Goose (来源页面).

祝各位情人节快乐, 估计我能在本科上完之前找到第一个 GF 就很不错咯… 光棍节还可以一直过下去, 很满足很满足…
p.s. 文章写完正好 0:00, 情人节过去了… 这篇文章的分类想了很久是 About Computer 还是 About
Life, 最终还是放在了前者里…

Time Limit Exceed, 官方网站点这里, Matrix67 神牛的介绍见这里.
大致说来就是一个题目各式各样千奇百怪的比赛… 评分标准可能和代码长度有关, 可能和空格个数有关, 和关键字个数有关… 或者综合起来, 反正很 bt 就是了.

今天晚上回家之后就和远在 TJU 集训的 jl 开始做, 结果还好. 截止到目前, 我们的队伍 YaohuaFree 排名 17, 和 oldherl 的 lonelycorn 队伍仅差 1 分.
先放出目前前 20 名队伍的积分.

1    DROP_DATABASE    CLASS / CODEHASH / INPOUT / KEY / PENGUIN / PRINT / SHORTEN / TESTGEN    1272
2    AnacondaTigers    INPOUT / KEY / PENGUIN    946
3    HyperHexagon    CLASS / INPOUT / KEY / PENGUIN    933
4    akuegel    INPOUT / KEY / SHORTEN    875
5    shinh    CLASS / CODEHASH / KEY / PRINT    826
6    UlmReds    CODEHASH / INPOUT    822
7    MrBu    INPOUT / KEY / SHORTEN    596
8    progheal    INPOUT / KEY / PENGUIN    571
9    time_limit    INPOUT / KEY / PENGUIN    550
10    GennadyTeam    CODEHASH / INPOUT    540
11    starforever    INPOUT / KEY / PENGUIN / SHORTEN    533
12    dota    INPOUT / KEY / PENGUIN / SHORTEN    494
13    dont_kill_me    INPOUT / KEY    449
14    mindjolt    INPOUT / KEY / PENGUIN    439
15    ziliang    INPOUT / KEY / SHORTEN    410
16    lonelycorn    INPOUT / PENGUIN / SHORTEN    398
17    YaohuaFree    INPOUT / KEY / PENGUIN / SHORTEN    397
18    Success    INPOUT / KEY    385
19    mcemil    INPOUT / KEY / PENGUIN / SHORTEN    378
20    incredible    INPOUT / KEY / PENGUIN / SHORTEN    358

比赛的过程也是比较曲折, 刚开始我一直在搞第一题 KEY, 那时还不知道 jl 也开始做了. 然后第一题一直十多分, 折腾折腾突然发现变成了 100 多分… 然后发现是因为 jl submit 了这道题. 于是立刻联系他, 搞到了他的 code, 考虑进一步优化. 很可惜因为输入数据最后的空行, 至今没有找到进一步优化的好办法, 几个细节优化也没有任何作用.
然后终于放弃 KEY, 我开始想 CLASS. 可惜始终想不到好的方法, 当然这 200pts 也不是那么好拿的.
这时 jl 貌似坐上了回家的公交车, 所以只有我一个人继续搞了. 先随便搞了下 PENGUIN, 拿了 15 分. 然后和 oldherl 聊天的时候他给了我一个非常关键的提示, 于是分数飙升至 118. 当然这还是我用 C++ 写而且没有优化的结果, 明天继续优化.
接下来就没啥可搞的了, 弄了 INPOUT 和 SHORTEN 骗分, 一个 27 一个 138, 这样就折腾到了 rank 17 了.

第一天的战况基本就这样, 自己还比较满意, 顺便 orz 一下 rank 1 的那队神牛, 9 题出 8 题 (虽然有一道题是 0 分).
剩下的题都不好搞, 估计接下来就是优化已经搞掉的题目了, 搞出新题很难.

p.s. 貌似真的很久没更新了… 两个多礼拜了呢.